30. graph traversal [12 1주차]

30. Graph Traversal [12-1주차]

2024년 1월 14일 일요일

오후 2:38

<Graph Traversal의 정의>

Graph Traversal이란 그래프의 노드를 특정한 순서로 방문하는 것이다.

방문하는 과정에서 노드에 대한 연산이 이루어진다.

 

방문이 끝나면 그 결과로 유용한 정보가 담긴 자료(보통 트리 구조)가 산출되기도 한다.

 

 

<Any-Order Traversal>

어떤 노드 s에서 시작. 먼저 s를 상자에 넣는다.

상자가 비어 있지 않은 동안

• 상자에서 노드 하나를 꺼낸다.
• 노드에 마킹이 되어 있지 않으면

• 노드에 마킹을 한다.
• 노드에 대한 연산을 한다. (어떤 연산을 할지는 문제마다 다르다)
• 모든 인접 노드를 상자에 넣는다. (-> 한 노드가 여러 번 상자에 들어갈 수 있다.)

 

마킹 : 해당 노드에 대한 작업이 끝났다는 것을 표시하는 역할.

 

 

<Any-Order Traversal의 시간복잡도>

노드 개수를 V, 간선 개수를 E라 하자.

 

어떤 노드 s에서 시작. 먼저 s를 상자에 넣는다. -> O(1)

상자가 비어 있지 않은 동안 -> 2E 번 반복

• 상자에서 노드 하나를 꺼낸다. -> 2E*? (다익스트라 : 2E*O(logN))
• 노드에 마킹이 되어 있지 않으면

• 노드에 마킹을 한다. -> V*O(1)
• 노드에 대한 연산을 한다. -> V*O(1)
• 모든 인접 노드를 상자에 넣는다. -> 2E*O(1)

 

 

상자에 노드를 넣는 연산과 꺼내는 연산은 각각 총 2E번 이루어진다. 왜 그런가?

• 노드 u와 v를 잇는 간선 (u, v)에 대해, 노드 u가 마킹이 안 되어 있다고 하자.

u가 상자에서 나오면 마킹이 되며, 인접한 노드 v를 상자에 넣게 된다.

u가 마킹이 된 이후에는 u는 v를 상자에 넣지 않는다.

또한 v가 마킹이 되기 전, v가 상자에서 나오면 v가 마킹이 되면서 u를 상자에 한 번 넣게 된다.

이렇게 한 간선에 대해 두 개의 노드를 한 번씩 상자에 넣게 된다.

 

 

<Reachability 문제>

노드 s로부터 t까지의 경로가 존재하는지를 판단하는 문제이다.

 

Any-Order Traversal을 이용하여 Reachability 문제를 풀 수 있다.

s에서 시작하여 Traversal이 끝났을 때 t가 마킹이 되어 있으면 경로가 존재하고, 마킹이 안 되어 있으면 경로가 존재하지 않는다.

 

증명

• s로부터 t까지의 경로 {s(=a0) -> a1 -> a2 -> … -> t(=an) }가 존재한다고 하자.

s가 마킹이 되는 것은 자명하다.

노드 ak가 마킹이 되어 있다면 인접 노드를 상자에 넣으므로 a(k+1)도 마킹이 된다.

따라서 t도 마킹이 된다.

• t가 마킹이 되어있다고 가정한다. t를 상자에 넣은 노드를 a(n-1), a(n-1)을 상자에 넣은 노드를 a(n-2), …, a1을 상자에 넣은 노드를 s라 한다.

노드 ak가 노드 a(k+1)을 상자에 넣었다는 것은 ak와 a(k+1)이 인접한 노드라는 뜻이다. 따라서 s->a1->a2->…->a(n-1)->t라는 경로가 존재한다.

 

Any-Order Traversal을 이용하여 Reachability 문제를 푸는 데 총 O(V+E)시간이 걸린다. 상자에서 노드 하나를 꺼내는 데 O(1)시간만 걸리기 때문이다.

 

 

<Connected Component 문제>

연결된 노드들의 집합을 모두 찾는 문제. 각 집합 내의 노드들이 연결되어 있다는 조건 하에서, 한 집합에 최대한 많은 노드가 들어 있어야 한다.

 

아무 노드에서 Any-Order Traversal을 한다. 연결된 노드들은 전부 마킹이 되어 하나의 집합이 구해진다. 아직 마킹이 안 된 노드들에 대해 다시 Any-Order Traversal을 한다. 또 다른 집합이 구해진다. 이 과정을 반복한다.

 

 

 

 

 

<Bipartite Graph Detection>

노드들을 두 집합으로 나눈다.

이때, 노드가 한 집합 내부에서는 간선으로 직접 연결되지 않고, 서로 다른 집합에 있는 노드끼리만 연결되도록 해야 한다. 이런 규칙을 만족하도록 노드들을 두 집합으로 나눌 수 있는 그래프를 Bipartite Graph라고 한다.

 

간선이 하나도 없는 경우도 Bipartite라 한다.

 

<DFS를 이용한 Bipartite Graph Detection 풀이>

먼저 DFS트리를 구한다.

그래프가 Bipartite 라고 가정하고, 노드 집합 A와 B로 Bipartite 규칙을 만족하도록 나누어진다고 하자. 루트 노드가 A에 속한다고 하면, 루트 노드는 모든 아래 층의 노드와 연결되어 있으므로, 아래 층의 노드는 모두 B에 속해야 한다. 마찬가지 이유로 깊이 2의 노드들은 모두 A에 속해야 하고, 깊이 3의 노드들은 모두 B에 속해야 한다. 이렇게 층마다 A에 속하는 노드, B에 속하는 노드가 번갈아 나타난다.

 

다음으로 back edge들을 조사하여, back edge중 A의 노드끼리 연결하거나 B의 노드끼리 연결하는 것이 하나라도 있는지 확인한다. 그런 back edge가 하나도 없어야만 Bipartite 그래프이다.