[알고리즘] 그래프 (1) - 그래프 정의, 구현, 순회, 응용

그래프(graph)

연결할 객체를 나타내는 정점(vertex)의 집합과 정점을 연결하는 간선(edge)의 집합으로 구성된 비선형 자료구조

그래프 G=(V, E) → 연결할 객체는 나타내는 정점의 집합 V와 정점을 연결하는 간선의 집합 E의 집합
 - 종류 → 무방향 그래프 vs 방향 그래프, 가중 그래프
 - 주요 용어 → 인접, 부수, 부분 그래프, 경로, 경로의 길이, 차수(진입차수, 진출차수), 단순 경로, 사이클, 루프, 연결, 강하게 연결, 약하게 연결

 

그래프의 구현 방법

정점들의 관계를 나타내는 간선의 집합 E를 표현하는 것

인접 행렬(adjacency matrix)
- 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 2차원 배열 A=(n×n)으로 표현하는 방법

- |V|*|V| 행렬 사용

- 조밀한(dense) 그래프에 적합
인접 리스트(adjacency list)
- 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 n개의 연결 리스트로 표현하는 방법으로, 각 연결 리스트는 임의의 정점 u에 대해서 인접한 모든 정점을 표현함

성긴(sparse) 그래프 표현에 적합

그래프 순회(graph traversal)

그래프의 모든 정점을 체계적으로 한 번씩 방문하는 방법

깊이 우선 탐색(depth first search)
- 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색하는 방법
- 최근의 주변 정점을 우선으로 탐색하는 방법
 - 스택 구조를 통해 구현
 - 인접 리스트 O(|V|+|E|), 인접 행렬 O(|V|2)

너비 우선 탐색(breadth first search)
- 시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법
- 주변 정점 중에서 가장 오래된 것부터 우선 방문하는 방법
 - 큐를 통해 구현
 - 인접 리스트 O(|V|+|E|), 인접 행렬 O(|V|2)

 

응용

위상 정렬(topological sort)
- 무사이클 방향 그래프에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것

- 깊이 우선 탐색 활용 → 탐색을 수행하다가 더 이상 주변 정점이 없어서 되돌아갈 때, 즉 스택에서 탑이 삭제될 때 그 제거한 정점을 역순으로 나열하면 됨

연결 성분(connected component)
- 주어진 무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프

- 탐색을 수행하다가 큐/스택이 비게 되면 그때까지 탐색한 정점들을 하나의 연결 성분으로 구성하며, 이 과정을 탐색하지 않은 정점이 남아 있지 않을 때까지 반복

강연결 성분(strongly connected component)
- 주어진 방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래

 - 깊이 우선 탐색을 적용하여 정점의 방문 완료 순서(방문 순서의 역순)를 구하고, G=(V, E)에 대해 ER={< v,u >|<u,v>∈E}를 사용한 GR=(V, ER)을 구하고, GR에 대해서 방문 완료 번호가 큰 것부터 DFS를 수행하여 갈 수 있는 정점들의 각 리스트가 강연결 성분이 됨</u,v>