지난 시간에 이어 그래프 순회에 대해 공부해보자.
What kind of BOX?
- Stack –> DFS (Depth-First Search)
- Queue –> BFS (Breadth-First Search)
- Priority Queue
- With edge weight –> Prim
- With distance from s –> Dijkstra
- Arbitrary Function –> A*
BFS는 다익스트라랑 거의 비슷하기 때문에 생략하고, 오늘은 DFS를 보자.
DFS
Recursive DFS
DFS를 재귀적으로 표현하는 것이 더 편할 때도 많다.
핵심 내용만 작성한 슈도코드는 다음과 같다:
RDFS(Node s)
Mark node s
Set pre(s)
For every adjacent node s
If t is not marked, RDFS(s)
Set post(s)
필요한 변수들을 보자.
- mark[N]: 노드들의 mark 여부를 관리. 해당 노드가 방문되었는가를 저장한다.
- pre[S]: preorder로 순회할 때, 해당 노드가 몇 번째로 방문되는지 저장. 1로 초기화한다.
- post[S]; postorder로 순회할 때, 해당 노드가 몇 번째로 방문되는지 저장. 1로 초기화한다.
- pre: preorder로 노드에 번호를 붙이기 위해 사용
- post: postorder로 노드에 번호를 붙이기 위해 사용
Simulate Recursive with Any-Order Traversal
RDFS를 스택을 사용해 구현해보자.
Start at node s
While stack is not empty:
Take a node p from stack
If p*, set post(p)
If p is not marked:
Mark p // set pre(p)
Do computation on p
// Put p* into stack
Put every adjacent node q into stack
(p*: 내가 push한 노드들이 다 pop되었다는 것을 알려주기 위한 특별한 노드)
DFS Tree
- DFS tree is the result of DFS
- We usually analyse DFS tree to get information
그럼 트리에 들어가지 못한 엣지들은?
Back Edges
- Edges of the input graph becomes tree or back edges of DFS tree
- cross, forward가 안 되기 때문에 백 엣지라 부름
다시 말하자면, 서로 조상 관계인데 부모 관계는 아닌 두 노드를 연결하는 엣지를 말한다. (자손에서 조상으로 나가는 방향만 가능하다.)
DFS하고 나면 트리가 만들어진다. 그런데 트리에 들어가지 못한 다른 엣지들도 표현해줘야 문제가 쉽게 풀리는 경우도 있기 때문에 백엣지도 표현.
Bipartite Graph Direction
백 엣지를 사용하면 주어진 그래프가 bipartite graph(이분 그래프)인지 판별할 수 있다. 이분 그래프란, 그래프 상의 노드들을 두 그룹으로 나눴을 때 모든 엣지가 서로 다른 그룹의 노드들을 연결하는 그래프를 말한다.
(출처는 위키피디아)
그럼 DFS로 생성된 트리가 이분그래프인지 판별해보자. 두 그룹 left와 right 중 root를 left에 넣고 시작한다. 그러면 root의 child는 right이다.
느꼈다시피 트리를 만들고 나면 이분그래프인지를 확인하는 것은 엄청나게 쉽다. 이제 백엣지가 같은 그룹의 노드들을 연결하는지만 확인하면 된다.
Cut Vertex
Definition
- Remove node s to make a graph disconnected
- Exists x and y such that all paths from x to y go through s
위 둘은 같은 말이다. 왜냐하면 s를 제거하면 그래프가 최소 두 덩어리로 나눠지는데, 이 때 x와 y를 각각 다른 덩어리에서 잡으면 x에서 y로 가는 path가 더이상 존재하지 않기 때문이다.
How to find cut vertex of a graph?
One possible idea: For each node s, remove G and run connected components
그래프 내의 모든 노드에 대해 connected component를 돌려보면 되지만 시간이 너무 오래 걸린다. Connected component가 O(m + n) 시간이 걸리는데 이걸 n번 하므로 전체 시간복잡도는 O(mn + n^2)이 된다.
Root of DFS tree is a cut vertex iff it has more than one child.
DFS 트리에서 1)루트가 cut vertex이면 두 개 이상의 child를 가지고, 2)child가 두 개 이상이라면 루트는 cut vertex이다.
2)부터 증명해보자.
그림을 보고 직관적으로 알 수 있듯이 루트가 없으면 왼쪽, 오른쪽 서브트리의 노드들이 서로 연결될 수 없을 것 같아보인다. 그런데 백엣지들도 고려해야 하지 않을까?
그림과 같은 백엣지가 존재할 경우 문제가 된다. 그러나 조금 전에 우리는 cross나 forward인 백엣지는 없다는 것을 보았다. 다시 말해 저런 백엣지들은 존재하지도 않으며 서브트리 내부나 루트까지만 백엣지들이 존재한다는 것이다.
따라서 루트를 거치치 않고서는 x에서 y로 가는 path가 존재하지 않고, child가 두 개일 때 루트는 무조건 cut vertex라는 것을 증명할 수 있다.
이번에는 1)을 증명해보자. 직접 증명하는 대신
child가 두 개 미만이라면 루트는 cut vertex가 아니다라는 대우명제를 증명할 것이다.
루트노드의 child가 하나인 경우는
루트를 제외한 나머지 모든 노드가 서브트리 내에 있고, 백엣지를 고려하지 않더라도 서브트리 내의 모든 노드들이 연결돼있다 (트리는 connected graph니까). 그래서 루트를 지워도 나머지 노드들은 모두 연결돼있다.
Another possible idea: For each node s, run DFS from s (to make it the root) and check if it is a cut vertex
그러나 각 노드를 루트로 잡아 DFS를 돌리는 거니까 시간복잡도는 여전히 O(mn + n^2)이다.
DFS를 한 번만 수행해 트리를 만들고, 루트가 아닌 노드들에 대해서만 cut vertex인지 아닌지를 체크할 방법이 있다면 시간을 줄일 수 있지 않을까?
- Root of DFS is a cut vertex iff has more than one child
- What about non-root node t?
- For each t compute l(t), which is the minimum of
- pre(t) // 위에서 아래로 내려갈수록 preorder가 커진다는 성질 사용
- Min of pre(s) where (t, s) is a back edge
- min of l(u) for all children of t
- t is a cut vertex iff exists a child u of t such that l(u) >= pre(t)
pre(t)는 자기 자신이고, min of pre(s) where (t, s) is a back edge는 t에서 백엣지를 타고 직접 갈 수 있는 가장 높은 곳을 의미한다. min of l(u) for all children of t는 t를 루트로 하는 서브트리에서 백엣지를 한 번 타고 올라갈 수 있는 가장 높은 곳을 의미한다.
이 계산이 끝난 후 t의 preorder보다 큰 child의 l(u)가 하나라도 있으면 t는 cut vertex이다.
Proof
l(u) >= pre(t)라 가정해보자. u를 루트로 하는 서브트리에서 올라갈 수 있는 가장 높은 데가 t라는 것이다.
그럼 서브트리 내의 임의의 노드를 x, t 위의 임의의 노드를 y로 잡으면
x에서 y로 가기 위해서는 무조건 t를 거쳐야 한다.
다음 시간에는 DFS로 풀 수 있는 조금 더 어려운 문제를 볼 예정