19 Jan 2020

Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그, Heee님의 블로그를 참고하였다.

1. Graph(그래프)

노드(정점)와 엣지(간선)의 집합으로 구성된 자료구조

그림으로 나타내면 다음과 같다. 노드의 집합을 $V$, 간선의 집합을 $E$라고 표기한다.
또, 노드 $x$와 $y$의 간선을 $e = $ {$x, y$}라고 표기한다.

2. Graph(그래프) 용어 정리

• Vertex(정점) : 위치 = node

• Edge(간선) : 위치 간의 관계

• Degree(차수) : 임의의 노드에 연결된 엣지의 수

• Adjecent(인접) : 임의의 두 노드가 하나의 엣지로 연결된 경우 이 노드들은 인접해있다.

• Incident(부속) : 임의의 두 노드가 하나의 엣지로 연결된 경우 이 엣지는 두 노드에 부속한다.

• loop : 한 엣지가 임의의 노드에서 빠져나와 다시 그 노드로 향하는 경우

  

• Isolated vertex : 엣지가 없는 노드

• cycle(사이클) : 시작 정점과 종료 정점이 동일한 경로

• Path(경로) : 인접한 노드들로 구성된 시퀀스

• Path length(경로 길이) : 경로를 구성하는 간선의 수

• Simple path(단순 경로) : 반복되는 노드가 없는 경로

• Subgraph

  임의의 그래프 $G = (V, E)$에서 임의의 노드와 엣지를 빼내었을 때, 이 노드와 엣지가 원래 그래프 G의 $V, E$의 부분집합에 해당하는 그래프

3. Graph(그래프)의 종류

3-1. Sparse / Dense graph

노드의 개수 $\vert V \vert$, 간선의 개수 $\vert E \vert$에 대하여

• Sparse graph : 노드가 간선보다 많은 그래프. $\vert V \vert$ > $\vert E \vert$　(아래 왼쪽 그림)

• Dense graph : 간선이 노드보다 많은 그래프. $\vert V \vert$ < $\vert E \vert$, 　$\vert E \vert \approx \vert V^2 \vert$　(아래 오른쪽 그림)

  

3-2. Directed / Undirected graph

• Directed graph(방향 그래프) : 엣지가 방향성을 갖는 그래프
• Undirected graph(무방향 그래프) : 엣지가 방향성을 갖지 않는 그래프

3-3. Weighted graph

Weighted graph(가중치 그래프) : 간선에 비용(가중치)이 할당된 그래프. 네트워크라고도 한다.

3-4. Connected / Disconnected graph

• Connected graph(연결 그래프) : 무방향 그래프에 있는 모든 정점간에 경로가 존재하는 경우. ex) 트리
• Disconnected graph(비연결 그래프) : 무방향 그래프에서 모든 정점간에 경로가 존재하지 않는 경우

3-5. Cyclic / Acyclic graph

• Cyclic graph : 사이클이 있는 그래프
• Acyclic graph : 사이클이 없는 그래프

3-6. 기타

• Complete graph : 모든 노드들이 엣지로 연결된 그래프　(아래 왼쪽 그림)

• multi graph : 노드 사이를 잇는 엣지가 하나 이상인 그래프　(아래 오른쪽 그림)

  

• Clique(클리크) : 모든 노드들이 엣지로 연결된 Subgraph

4. Graph(그래프)의 특징

Tree와 비교하여 Graph의 특징을 나타내면 다음과 같다.

5. Graph(그래프)의 구현

그래프의 구현방식으로는 인접리스트와 인접행렬이 있다.

• 인접리스트(Adjacency List) : 각각의 정점에 인접한 정점들을 리스트료 표시한 것. 배열, 연결리스트 등을 이용해 표현할 수 있다.

  • 방향그래프

    

  • 무방향그래프

    

• 인접행렬(Adjacency Matrix) : n x n Boolean matrix로써 행과 열을 각각 노드로 표현하여 간선의 유무(가중치)를 나타낸 행렬. 방향그래프에서 인접행렬의 값은 간선이 있으면 가중치 값, 없으면 무한대이고, 무방향그래프에서 인접행렬의 값은 간선이 있으면 1, 없으면 0이다.

  • 방향그래프

    

  • 무방향그래프

    

보통 효율적인 측면에서 인접 리스트(Adjecency List)가 많이 사용되고 있다. 인접 행렬에서 각각 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야하기 때문이다.

• Sparse graph : 노드가 더 많다. 따라서 인접 리스트 주로 사용
• Dense graph : 간선이 더 많다. 따라서 노드 순회할 필요 없으므로 인접 행렬 주로 사용

6. Graph(그래프)의 시간복잡도

전체 노드 수가 $V$개, 엣지 수가 $E$개라고 하자. 그래프에서 시간복잡도를 다루는 기준은 임의의 두 노드가 서로 인접해있는지 여부를 아는 것과 임의의 노드로부터 인접해있는 노드를 찾는 것이다.

• 인접리스트(Adjacency List)

  • 임의의 두 노드가 인접해있는지 여부 : $i$번째 버킷 내에 $j$가 있는지 따져야 함. $i$번째 노드의 차수(연결된 경로의 수)가 $d$라고 한다면 시간복잡도는 $O(d)$

  • 임의의 노드로부터 인접한 노드 찾기 : $i$번째 버킷에 속한 모든 요소를 순회. 따라서 위와 마찬가지로 $O(d)$

• 인접행렬(Adjacency Matrix)

  • 임의의 두 노드가 인접해있는지 여부 : $i$번째 행과 $j$번째 열을 한범나 참조하면 되므로 $O(1)$

  • 임의의 노드로부터 인접한 노드 찾기 : $i$번째 행 전체를 조사하면 됨. 노드 전체를 따져봐야하므로 $O(\left\vert V \right\vert)$