spanning-tree

많은 그래프 문제들이 dfs와 bfs를 사용한다. 어떤건 둘다 사용가능하고(ex: flood fill), 어떤건 하나만 사용가능하다(최단거리=bfs, ??=dfs). 이러한 차이가 생기는건 두 알고리즘이 그래프를 완전탐색하는 알고리즘인건 동일하지만, 방문순서같은 그 세부적인 특징이 다르기 때문이다. 그리고 이러한 차이점을 잘 분석하고 이해하려면 각 알고리즘이 만들어내는 spanning tree와 그로 인해 가능한 간선분류를 알아야 한다. 그걸 하면 뭐가 좋은가? 각 탐색방법에 기반한 여러가지 심화 알고리즘들(tarjan scc, bi-connected component, cycle space 등)을 이해할 기초를 닦을 수 있다. 여담으로 본인은 이걸 dfs tree, bfs tree라고 종종 불렀었는데, 그러면 tree에서 dfs/bfs하는것밖에 안나와서 dfs/bfs spanning tree라고 풀 네임을 부르는게 바람직할 것 같다. 다만, 본문에서는 표기의 간략함을 위해 dfs/bfs tree로 줄여부르겠다. dfs tree는 종만북에 잘 나와있고, 그것을 통해 간선분류를 하면

추가적으로, 가중치가 있는 그래프에서는 bfs tree대신 dijkstra tree를 생각해볼 수 있다. 이렇게 일반화하면 어떤 그래프 탐색방법에 대해 처음 방문하는 노드로만 간선을 확장하면서 그에 대응하는 spanning tree를 construct할 수 있겠다.

back-edge들을 전부 제거하면 사이클이 없지만, tree edge이외에 남아있는 cross-edge때문에 tree가 아니게 된다. 이는 DAG이고, Dijkstra DAG를 활용하는 문제로 (https://www.acmicpc.net/problem/24888)를 출제한적이 있으니 관심있으면 한 번 풀어보자.

bfs tree를 활용하는 문제: https://www.acmicpc.net/problem/10691 인줄 알았으나 방향그래프라서 시간초과에, 그냥 n^3/64 커팅이라고 함 우웩. 뭐가 있을까? 아직은 모르겠다.

tarjan scc같은 경우에 방향그래프도 dfs tree로 간선분류하긴 하는데, 방향그래프의 spanning tree는 훨씬 까다로운 문제다. directed MST도 그렇고 위에 Fegla도 거리체크하는 bfs했다가 시간초과나고..