그래프

그래프의 정의

 

그래프의 기본구조

 

그래프 - 정점과 간선으로 이루어진 자료구조

두 노드가 간선으로 연결되어 있으면 '인접하다'라고 표현한다.

그래프는 꼭 연결되어 있을 필요도 없고, 또 두 정점 사이의 간선이 반드시 1개 이하일 필요도, 또 간선이 반드시 서로 다른 두 정점을 연결해야 할 필요도 없다.

루프(loop) - 한 정점에서 시작해 같은 정점으로 들어오는 간선

그래프의 차수(Degree) - 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수

 

순환 그래프(Cyclic graph) : 그래프 안에 사이클이 하나라도 있다.

비순환 그래프(Acyclic graph) : 사이클이 하나도 없다.

완전 그래프(Complete Graph)  : 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프

연결 그래프(Connected Graph) : 그리고 임의의 두 정점 사이에 경로가 항상 존재하는 그래프

단순 그래프(Simple Graph) : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

 

그래프의 표현 방식

• 인접 행렬

2차원 리스트로 구현

1 혹은 0으로만 나타내는 표현법

만약 단순 그래프가 아니라고 한다면 1 혹은 0으로만 나타내지 말고 간선이 3개면 3을 쓰고, 4개면 4를 쓰고 이런 식으로 변형

 

인접 행렬로 그래프를 나타내면 정점이 V개이고 간선이 E개일 때 어떤 두 점이 연결되어 있는지를 O(1)에 알 수 있다.

가로와 세로가 각각 V인 2차원 배열이 필요하니 O(V2)의 공간을 필요.

어떤 점에 연결되어 있는 모든 정점의 목록을 알아내고 싶을 때, 개수와 무관하게 시간복잡도가 O(V)

 

• 인접 리스트( 연결 리스트로 구현 )

파이썬에서는 리스트 자료형이 append()와 메소드를 제공하므로 연결 리스트를 2차원 리스트로 구현

간선이 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식, 경우에 따라 인접 행렬로는 절대 저장이 불가능해 인접 리스트를 써야만 하는 상황이 종종 있다.