그래프(Graph) | 위상 정렬 | 연결 성분

🟩 연결되어 있는 원소 간의 관계를 표현한 자료구조

몇 개의 정점(Vertext)이 간선(Edge)으로 연결된 것

그래프 G = (V,E)

 

 

🟩 그래프 탐색

특정 정점에서 출발해 간선을 통해 이동해가며 대상 정점을 찾는 것

탐색 순서에 따라 깊이 우선 탐색, 너비 우선 탐색

 

🟩 그래프 용어

인접 : 두 정점이 연결되어 있을 때 cf. 정점들은 부속되어 있다 한다.

 

차수 : 정점에 부속되어 있는 간선의 수

경로 : 정점 a에서 b까지 간선으로 연결된 정점을 순서대로 나열한 리스트

단순 경로 : 모두 다른 정점으로 구성된 경로

👉 진입 차수, 진출 차

 

경로 길이 : 경로를 구성하는 간선의 수

사이클 : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

 

🟩 구현 방법

인접 행렬, 인접 리스트

 

🌟 무방향/방향 그래프

가중치 부여 가능

간선에 방향이 없는 경우, '무방향 그래프'

 

무방향 그래프 👉 (1,2) = (2,1)

방향 그래프  👉<1,2>, <2,5>

 

트리

V(G) = {1, 2, 3, 4, 5, 6}

E(G) = {(1,2), (1,3), (2,4), (3,4), (3,5), (4,5), (4,6)}

 

 🌟 가중 그래프

간선에 부여된 값을 간선의 '가중치' or '코스트'

간선에 가중치가 없을 때는 2개의 정점은 '연결돼 있거나', '연결돼 있지 않거나' 둘 중 하나이지만, 가중치가 있을 때는 '연결(관계)의 정도'를 표현 가능하다.

 

 👉 최단 경로 문제

두 정점을 연결하는 경로 중 간선의 가중치 합계가 가장 작은 것을 찾는 문제

---

🟩 그래프 순회

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

👉 그래프 탐색 방법  (깊이 우선 탐색, 너비 우선 탐색)

 

🌟 위상 정렬

순서가 정해져 있는 작업을 차례로 수행해야 할 때 사용할 수 있는 알고리즘

사이클이 없는 방향 그래프(DAG)의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열'

시작점이 존재해야 한다.

 

🟩 방법

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌 때까지 다음의 과정을 반복한다.

- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

- 새롭게 진입차수가 0이 된 노드를 큐에 삽입

 

👉 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과

1. 진입차수가 0인 모든 노드를 큐에 삽입. 현재 1번 노드의 진입차수만 0이므로 큐에 1번 노드만 삽입하게 된다.

 

2. 큐에 있는 1번 노드를 꺼낸다. 이후 1번 노드와 연결되어 있는 간선들을 제거한다. 그러면 2번, 5번 노드의 진입차수가 0이 되고, 큐에 삽입된다.

3. 큐에 있는 2번 노드를 꺼낸다. 2번 노드와 연결되어 있는 간선들을 제거한다. 그러면 3번 노드의 진입차수가 0이 되므로 3번 노드를 큐에 삽입한다.

 

4. 큐에 있는 5번 노드를 꺼낸다. 5번 노드완 연결되어 있는 간선들을 제거한다. 그러면 6번 노드의 진입차수가 0이 되므로, 6번 노드를 큐에 삽입한다.

 

5. 계속해서 반복하면 다음과 같은 결과를 얻을 수 있다.

 

👉 위상 정렬은 답안이 여러가지가 될 수 있다.

1 -> 5 -> 2 -> 3 -> 6 -> 4 -> 7 도 하나의 답이 될 수 있다.

 

cf. 스택으로 표현하는 방법

stack에 시작 정점을 push. 주변 정점을 선택하여 stack에 push. 주변 정점이 없으면 pop.

이전으로 돌아가서 체크 및 push/pop 반복하여 가장 마지막에 pop한 것이 앞으로 오도록 배치한다.

 

🟩 시간복잡도 O(V+E)

모든 노드를 확인 O(V), 해당 노드에서 출발하는 간선을 차례대로 제거 O(E) 해야 한다.

따라서 노드와 간선을 모두 확인하는 것을 고려하여 O(V) + O(E) = O(V+E)의 시간이 소요된다.

---

🟩 그래프의 연결성

정점 간의 연결 관계를 다루는 것

 

🌟 연결 성분

무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프

DFS/BFS를 활용하여 구한다.

while(아직 탐색하지 않은 정점이 존재)
탐색을 수행하다가 큐/스택이 비게 되면 그 때까지 탐색한 정점들을 하나의 연결 성분으로 구성

 

🌟 강연결 성분

방향 그래프에서 임의의 두 정점 사이에 양방향 경로가 존재하는 최대 부분 그래프