[자료구조 및 알고리즘] Graph Traversal

Traversal

 

Visit Nodes of a Graph in SOME order

• May go through a node several time
• While doing calculation

 

Any order traversal

• Start at a node s (put s into BOX)
• while BOX is not empty:
  • Take one node from BOX
  • If node not Marked:
    • Mark node
    • Do computation on node
    • put Every Adjacent node

 

This solves Reachability

• Solution: start at s, check if t was visited with any order traversal

 

Proof (귀류법)

 

위에서 제시한 any order traversal알고리즘을 이용하면 s → t 인 path가 있는 경우 반드시 s에서 시작해서 해당 알고리즘을 통해 t를 찾을 수 있다.

 

만약, path가 있지만 t까지 가지 않는 경우가 있다고하자. 그렇다면 t는 unmarked이다.

s → t의 path중 임의의 인접한 노드 i와 j에 대해 i는 marked, j는 unmarked인 경우가 반드시 있다. (i는 s쪽, j는 t쪽)

하지만, adjacent node인 i와 j에 대해서 알고리즘에서 j만을 unmarking할 코드가 없다.

 

따라서 위 주장은 맞다.

 

prob. Connected Component

 

연결되어있는 graph들을 찾는 문제

 

Solution: Repeat any-order traversal with unmarked nodes

 

prob. s → t인 path들 중 weight의 최대값이 가장 작은 path를 찾는 문제

 

Solution1: parametric search, 정답을 가지고 binary search

 

모든 가능한 정답 list에서 이진 정렬을 수행하며, 정답과 가까워지는 방법

만약 모든 가능한 정답이 2, 3, 4, 6, 8 이라고 했을때,

 

처음에는 4를 검사한다.

즉, weight의 최대값이 4인 경우는 edge의 weight가 4보다 작은 edge들만을 이용해서 path를 만들 수 있는지 확인한다.

만약, 가능하다면 3을 검사한다.

 

이런식으로 이진으로 탐색하면 된다.

시간복잡도는 Reachability하는데에 m+n, 이진탐색하는데에 logm

 

Solution2: kind of kruskal

 

정답을 2라고 했을때, weight이 2인 edge만 남기고, union-find를 수행하면된다.

만약 가능하다면 정답을 3으로 늘려서 다시 확인한다.

 

Event Queue

 

prob. Infection spreads!

 

what kind of Box?

 

• stack(DFS)
• queue(BFS)
• priority queue
  • with edge weight → Prim
  • with distance from s → Dijksra
  • arbitrary function → A*

 

Recursice DFS or DFS with Stack

 

DFS Tree

• DFS Tree is the result of DFS
• usually analysis DFS Tree to get Information

 

DFS Tree에 존재하는 tree edge는 전진하는 edge, tree edge가 아닌 보이지 않는 edge,

즉 DFS과정중에서 방문하지 않은 edge인 back edge가 있다.

 

DFS Tree에서 back edge를 추가한다면,

아무렇게나 추가할 수 있는 것이 아니라,

본인과 자신의 직계 부모, 자식 노드와만 back edge를 추가할 수 있다.

 

왜냐하면, 자신의 직계 부모, 자식노드와 연결하지 않고,

다른 노드와 연결되어있었다면,

그 노드들은 서로 직접적으로 연결되어있어야한다.

 

하지만, graph가 directed라면 가능할 수도 있다.

 

Back Edges

 

Edges of input Graph becomes Tree or Back edges of DFS tree

 

Bipartite Graph Detection

: 모든 노드가 2가지 종류의 노드 쌍으로 분류가능하다면 Bipartite graph라고 할 수 있다.

 

Solution: 일단 임의의 노드에서 시작하는 DFS Tree를 만든다. 그리고 난 후 back edge를 추가했을때, L과 L끼리 연결할 수 있다면 bipartite graph가 아니다. 그리고 애초에 DFS Tree에서 L, R이 안된다면 bipartite graph가 아니다.

 

Cut vertex

 

Def: Exist x and y s.t., all paths from x to y goes through s

 

Solution1: For each node s, remove s from graph g and run connected components, Time() → n(select s) * (n + m)(connected component)

 

Solution2: Run DFS, Build DFS Tree, Root of DFS Tree is a cut vertex iff it has more than 1 child

 

Proof.

case1. Root child #1 → root is not vertex

 

root를 제거해도, root의 자식 노드들끼리 subtree로 모두 연결할 수 있다. 즉, root를 제거해도 모든 노드들이 연결되기 때문에 root는 cut vertex가 아닌것이다.

 

case2. Root child # is more than 1 → root is vertex

 

root를 제거한다면, root의 자식 subtree가 최소 두 개가되고, 각각의 subtree를 a, b, c, ...라고 하자.

각각 a와 b의 임의의 노드 na, nb가 있을때, na와 nb는 우선 tree edge로 연결할 수는 없다.

 

그렇다면 back edge로는 가능한가?

불가능하다.

 

back edge는 직계 부모, 자식 노드가 아니면 back edge를 연결할 수 없다.

a, b는 부모 자식 subtree관계가 아니기 때문에 na와 nb는 back edge로도 연결할 수 없다.

 

But, Time() → n(select root) * (n + m)(DFS)

 

Solution3. For each t compute l(t), which is the minimum of pre(t) → pre(t)는 전진할때, 전진하는 노드에 붙이는 번호, 반대로 post(t)는 뒤로 물러갈때, 원래 있었던 노드에 붙이는 번호이다. pre()는 tree에서 위에 위치할 수록 번호가 낮기 때문에, 높이라고 해석할 수도 있다.

 

• Min of pre(s) where (t,s) is a back edge → 노드 t에서 연결되는 back edge에 인접한 노드 s에 대해서, pre(s)의 최솟값. 즉, 현재 노드 t에서 back edge를 타고 가장 높게 올라갈 수 있는 높이
• Min of l(u) for all children of t → t의 모든 자식 노드들에 대해서 l(u)의 최소값. 즉, t의 모든 임의의 자식노드들에서 가장 back edge를 통해 올라갈 수 있는 높이

 

이때, l(u) > pre(t)이면 t는 cut vertex가 아니다.

 

임의의 자식 노드 u에 대해서,

l(u)가 pre(t)보다 크다면,

 

u의 subtree와 t보다 위에 있는 graph와 back edge로 연결할 수 있다는 의미이다.

즉, node t가 없더라도 u의 subtree와 node t위에 있는 graph와 연결될 수 있다 → node t는 cut vertex가 아니다.

 

반대로 l(u)가 pre(t)보다 같거나 작다면,

 

node t의 subtree와 node t위에 있는 graph와 연결할 수 있는 back edge가 없다 → node t는 cut vertex다.

 

cut edge

 

cut edge가 의심되는 edge 가운데에 node를 하나 만들고 그 노드에 대해서,

cut vertex를 실행하면 된다.