[그래프] Cycle detection

백준 Dijkstra 기본 문제를 풀다가 만든 TC

https://www.acmicpc.net/problem/1916

 

1에서 출발해서 2와 3을 거쳐 1로 다시 되돌아오는 최단 경로를 찾고 싶다면?

3
3
1 2 5
2 3 3
3 1 1
1
1

답 9

 

기본 Dijkstra는 시작 지점에서 다른 지점까지의 최단거리만 찾아줌.

근데, 시작 지점의 최단 거리는 처음에 0으로 초기화 해준다는 점을 이용해서, 

relaxation 코드에서 시작 지점까지의 최단 거리만 따로 업데이트 하게 만들어 줄 수 있음

(directed graph라서 가능한 것. undirected graph에서 하면 시작 지점 바로 옆 지점간에 사이클 생김)

// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (d[next_node] == 0 || cost < d[next_node]) { // d[next_node] == 0 for start_node update
  d[next_node] = cost;
  pq.push({ cost, next_node });
}

 

이걸 보고, 한 지점에서 다시 제 자리로 돌아오는 최단 cycle 문제가 생각났다.

최단 cycle은 어떻게 찾을 수 있을까?

https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/

 

 

---

우선 Cycle detection 개념 부터 알아야겠다.

보통 다음과 같이 정리된다

주어진 그래프	사용 알고리즘
Undirected	Disjoint set (Union-Find)
Directed	DFS

1. Undirected graph

Union-Find

새 간선을 추가할 때, 간선 양쪽의 정점이 같은 컴포넌트에 있으면 이미 연결되어있다는 뜻이므로 사이클 생김

 

2. Directed graph

DFS

역방향 간선 찾기

- 종만북 간선 구분 (p.853)

- CLRS 3-color 

https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

gray : visited, not finished
black : visited, finished

current node -> white : new visit (트리 간선)
current node -> gray : back edge (역방향 간선)
current node -> black : forward or cross edge (순방향 혹은 교차 간선)