그래프, 인접 행렬, 인접 리스트

Graph 그래프는 Vertices 정점과 이들을 연결하는 Edge 간선으로 이루어집니다.

 

 

정점 u, v를 연결하는 간선은 (u, v)로 표현됩니다.

정점은 Vertex, Node로 부를 수 있습니다.

 

무방향에서는 (u, v)와 (v, u)가 동일합니다.

 

• 두 정점을 가장 적은 수의 Edge로 연결하는 경로를 Shortest Path라고 합니다.
• 어떤 정점에서 시작하여 다시 자신에게 돌아오는 경로가 있을 경우 이를 Cycle이라고 합니다.
• 각 간선 Edge마다 가중치 Weight 가 존재하는 경우에는 가중 그래프 Weighted Graph라고 부릅니다.
• 가중 그래프에서는 가중치의 합이 가장 적은 경로를 Shortest Path라고 합니다.
• 방향이 있는 그래프는 방향 그래프 Directed Graph라고 합니다.
• 방향이 있는데 사이클이 없는 경우는 방향성 비순환 그래프 Directed Acyclic Graph, DAG라고 합니다.
• 또한 가중치가 있을 때는 가중 방향 그래프 Weighted Directed Graph라고 합니다.

 

그래프를 볼 때는 정점과 간선들을 묶어서 집합으로 생각하는 게 좋습니다.

 

정점 집합을 V, 간선 집합을 E로 나타냅니다.

 

표현 방법

Edge Lists 간선 리스트

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]

가중치가 있다면 3번째 요소를 추가할 수 있습니다.

 

간선 리스트는 간단하지만 그래프에 특정 간선이 있는지를 알기 위해서는 리스트를 모두 검색해야 합니다. 

 

 

 

인접 행렬

인접 행렬은 0과 1로 이루어진 V x V 행렬입니다.

 

간선 Edge ( i, j ) 가 있을 경우에만 ( i, j )의 값이 1이 됩니다.

가중치가 있다면 1이 아닌 가중치 값을 저장할 수 있습니다. 

 

Edge의 존재 여부를 일정 시간 내에 파악할 수 있지만, Edge의 수가 적은 희소 그래프일 경우 공간이 낭비됩니다.

그리고 어떤 정점이 다른 정점 i와 인접해 있는지 알기 위해서는 i 정점과 인접한 정점들의 수가 적더라도 i 행의 모든 V 항목을 찾아봐야 합니다.

 

무방향 그래프에서 인접 행렬은 대칭이기 때문에 ( i, j ) = ( j, i )입니다.

 

 

인접 리스트

인접 리스트는 인접 행렬과 간선 리스트가 합쳐진 형태입니다.

각 정점 i에 그 정점과 인접한 정점을 저장합니다. 총 V개의 배열을 가집니다.

정점을 저장할 때 순서대로 나열할 필요는 없지만 오름차순으로 나타내는 게 편리한 경우가 많습니다.

 

이러한 그래프는 탐색할 때 너비 우선 탐색 BFS, 깊이 우선 탐색 DFS, 다익스트라 Dijkstra, 플로이드 Floyd Washall 등의 기법을 사용할 수 있습니다.

 

BFS는 큐, DFS는 스택, 다익스트라는 최소 힙, 플로이드는 3중 for문으로 구현 가능합니다.