그래프 정의 및 구현 방식 (인접 행렬 & 인접 리스트)

그래프는 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 

정점을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조로

객체들의 상호 관계를 표현하기 위해 고안된 자료 구조입니다.

 

여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 

우리 주변에서 찾을 수 있는 연결 구조의 예라고 할 수 있습니다.

여러 객체들이 서로 연결되어 있다는 점에서 그래프는 트리와 별로 다를 것이 없습니다.

 

그래프 표현 

▶ 인접리스트와 인접행렬

메모리 or 시간 사용 특성이 굉장히 다르기 때문에, 적절한 표현 방식 선택

 

인접리스트(adjacency list)

- 각 정점마다 하나의 연결 리스트를 갖는 방식

  |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어 있으므로, 

  전체 O(| V | + | E |)의 공간만을 사용

- 정점이 연결되어 있는지를 알기 위해서 연결 리스트를 일일이 뒤져야 한다.

 

인접 행렬(adjacency matrix)

- 2차원 배열을 이용해 그래프의 간선 정보를 저장 (| V | × | V | 크기의 행렬)

  실제 간선의 개수와 관계없이 항상 O(V2) 크기의 공간을 사용해서 문제가 될 수 있음.

- 연결정보를 배열 인덱스를 통해서 인접리스트보다 효율적으로 확인 가능

 

사이클 없는 방향 그래프(directed acyclic graph)

줄여서 DAG라고 부르는 이 그래프는 방향 그래프인데, 

한 점에서 출발해 자기 자신으로 돌아오는 경로(사이클)가 존재하지 않는 경우

DAG는 여러 작업들 간의 상호 의존 관계등을 그래프로 표현할 때 흔하게 출현합니다. 

(간선의 방향을 무시할 경우 DAG에는 사이클이 존재할 수 있다.)

 

같이 보면 좋은 내용

- 그래프 표현 (인접 리스트 / 인접 행렬)

그래프 표현 (인접 리스트 / 인접 행렬)

- DFS (depth-first search, 깊이 우선 탐색)

깊이 우선 탐색(depth-first search, DFS)

- BFS (Breadth-First Search, 너비 우선 탐색)  

BFS (Breadth-First Search, 너비 우선 탐색)

 

- 다익스트라(Dijkstra)  

다익스트라 (Dijkstra)

- 벨만-포드 (Bellman-Ford)  

벨만-포드 (Bellman-Ford)

 

- 플로이드 와샬 (Floyd Warshall) 

플로이드 와샬 (Floyd Warshall)

- 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)