[Algorithm] Decomposition of graphs >> DFS

chapter 3 Decompositions of graphs

 

3.1 Why graphs?

- 그래프는 vertex(정점)과 edge(간선)들로 이루어 진다.

- undirected(무방향)일 경우 relation은 대칭이다.

- directed(방향)일 경우는 대칭이 아니다.

 

3.1.1 How is a graph represented?

① 인접 행령 (adjacency matrix)

vertex(정점)이 v1, v2, … ,vn 이고, n=|V|이면, n*n의 배열로 나타낼 수 있다.

    - aij = 1 ( vi에서 vj로의 간선(edge)가 있는 경우)

      aij = 0 ( vi에서 vj로의 간선(edge)이 없는 경우)

    undirected(무방향) 그래프일 경우 대칭이다.

    특정 edge(간선)의 존재를 가장 편리하게 찾을 수 있다. (constant time)

    matrix는 O(n^2)이며, edge(간선)의 수가 적으면, 낭비가 심하다.

② 인접 리스트 (adjacency list)

하나의 vertex(정점)당, |V|의 linked list로 구성되어 있다.

• 정점 u는 u에서 나가는 정점들과 연결되어있다.

directed(방향) 그래프라면 연결 리스트에 한번, undirected(무방향) 그래프라면 두번 나타난다.

• data structure는 O(|E|)이다. (|E|는 간선 개수)

특정 간선 (u,v)의 존재를 체크할 때, constant time이 아니다. (인접 리스트만 확인)

linked list에서, 반복되기가 쉽다.

• 이것이 DFS의 핵심이 될 예정.

---

3.2 Depth-first search in undirected graphs

 

3.2.1 Explorint mazes

DFS는 그래프에 관한 풍부한 정보들을 다목적 linear time 절차입니다.

What parts of the graph are reachable from a given vertex?

미로를 지나갈 때, 부주의한 선택으로 인해 순회하는 경우가 생길 수 있고, 접근 가능한 지점을 간과할 수도 있다.

•   탐색하는 동안, 중간 지점을 기록하는 것이 필수적이다.
•   컴퓨터에서는 Boolean으로 방문한 지점을 표현하는 것이 좋겠다.
•   스택에 새로운 정점을 넣고, 이전으로 돌아가기 위해 정점을 꺼낸다.
•   recursion을 예방할 수 있다.

 

procedure explore(G,v)

Input : G = (V, E) is a graph; v∈V

Output : visited(u) is set to true for all nodes u reachable from v

 

visited(v) = true

previsit(v)

for each edge (v,u) ∈ E:

           if not visited(u) : explore(u)

postvisit(v)

 

previsit과 postvisit은 선택사항으로, 처음 발견될 때와 마지막 떠날 때 작업이다. (**잠시 후)

 

explore 함수가 정확한지 확인하는 것이 우선이다.

explore 함수는 이웃 노드로만 이동한다.

절대 어떤 지역을 뛰어넘을 수 없다.

Example) v->z->w->u

           여기서, z는 방문했지만, w는 방문하지 않았다고 한다면, 이것은 모순이다.

           node z에서, explore는 이웃 노드인 w를 알아차리고 움직였을 것이다.

 

3.2.2 Depth-first search

위의 explore 함수는 시작 포인트에서, 그래프가 도달할 수 있는 부분만을 방문한다.

순회할 수 있는 모든 정점을 순회하는지 알아보기 위해 알고리즘을 세워본다.

 

procedure dfs(G)

for all v ∈ V:

           visited(v) = false

for all v ∈ V:

           if not visited(v): explore(v)

 

Running Time

①     고정된 작업 – visited 표기와 pre/postvisit -> O(|V|)

    -      각 정점마다 시간이 다르다. 따라서, 정점 전체의 시간을 생각해본다.

    -      쉽게 O(|V|)의 시간이 필요하다는 것을 알 수 있다.

②     인접 edge(간선)들을 확인하고, 새로운 정점으로 이동하는지 확인 -> O(|E|)

    -      각 간선 {x,y} ∈ E 에서, 정확하게 두번 검토된다.

    -      explore(x)와 explore(y)

③     따라서, 입력 크기가 linear 일 때, DFS의 전체 수행 시간은 O(|V|+|E|)

 

3.2.4 Connectivity in undirected graphs

 

▲    연결되지 않은 그래프 ( A – K 의 edge가 존재하지 않음, 세개의 분리된 연결 영역)

각각의 영역은 연결된 요소들로 구성된다.

특정 정점에서 explore함수가 시작되었을 때, 각 영역의 연결된 요소들만 방문한다.

 

procedure previsit(v)

ccnum[v]=cc

따라서, 깊이 우선 검색은 그래프가 연결되어 있는지 확인하고, 각 노드 v에 연결된 구성요소를 식별하는 정수 ccnum[v]를 할당하도록 간단하게 조정된다.

cc가 0으로 초기화되고, DFS 프로시저가 explore함수를 호출할 때마다 증가한다.

 

3.2.4 previsit and postvisit orderings

선형시간동안 무방향 그래프의 연결구조를 알아보았고, previsit과 postvisit에 대해 알아보자

▲    각 노드에 붙어있는 숫자들을 보면, 24개의 이벤트가 발생했다.

       5번째는 I, 21번째는 D이다.

pre와 post 배열은 간단하게 1부터 시작하는 clock counter로 정의할 수 있다.

 

procedure previsit(v)

pre[v] = clock

clock = clock + 1

 

procedure postvisit(v)

post[v] = clock

clock = clock + 1

 

Property 임의의 두 노드 u 및 v에 대하여 두개의 간격 [pre(u),post(v)]와 [pre(v),post(v)]는 분리되거나, 하나가 다른 하나에 포함된다.

Why? [pre(u),post(v)]는 u가 스택에 머무는 시간이다.

---

 

3.3 Depth – first search in directed graphs

3.3.1 types of edges

A는 root 이고, 나머지는 모두 자손이다.

E는 F, H, G가 자손이며, 조상은 3개 있다.

C는 D의 부모이다. D는 C의 자식이다.

 

무방향 그래프에서, tree edges와 nontree edges는 구분된다.

Tree edge들은 DFS forest의 부분이다.

   - Forward edge들은 자식이 아닌 자손 노드와 연결된다.

   - Back edge들은 DFS 트리에서 조상과 연결된다.

   - Cross edge들은 자손과 조상 둘다 연결되지 않는다. 따라서, 완전히 탐색된 노드로 이어진다. (**이미 방문한 노드)

 

조상과 자손 관계는 간선 타입들만큼 pre로부터 post number들을 읽을 수 있다.

   - 깊이 우선 탐색 전략으로 인해, 정점 u는 u가 먼저 발견되고, v가 explore(u) 중에 발견되는 경우 정점 v의 조상이다.

     pre(u) < pre(v) < post(v) < post(u)

     [   [    ]   ]

     u  v   v   u

    이 경우, u가 v의 자손인 경우, v가 u의 조상이므로, 대칭이다.

    그리고 edge 카테고리는 전적으로 조상-자손 관계이기 때문에, pre, post번호에서도 읽을 수 있다.

 

 

3.2.4 Directed acyclic graphs

방향그래프의 순환은 v0->v1->v2-> … ->vk->v0 의 순환 경로이다.

Property 방향 그래프는 DFS에서 back edge가 나타나는 경우에만 순환한다.

Proof  만약 (u,v)가 back edge라면, 검색 트리에는 v에서 u까지의 경로와 함께 순환으로 구성된다. 역으로, 그래프가 순환을 가진다면, 순환의 첫번째 노드를 볼 수 있다. (이 노드의 pre number는 가장 낮을 것). 이것이 vi라고 가정하자. 사이클의 모든 vj는 cycle에서 도달할 수 있으므로, 검색 트리에서 하위항목이 됩니다. 특히 vi-1->vi(or vk->v0 if i=0)은 어떤 노드로부터 조상으로 이어지고, back edge의 정의이다.

 

방향 비순환 그래프(DAG, Directed Acyclic Graph)는 항상 나타난다.

    - 인과 관계와 계층구조, 시간적 의존성과 같은 관계를 모델링 하기 좋다.

다른 특정 작업이 완료될 때까지 시작할 수 없다고 가정한다면, ‘작업을 수행할 올바른 순서가 무엇인가?’ 하는 것이 가장 큰 문제이다.

    - u가 v의 선행작업이라면, 방향 그래프로 쉽게 나타낼 수 있다.

      즉, 작업을 수행하기 전, 해당 작업을 향하는 모든 작업은 완료되어야 한다.

      이때, 순환이 있어서는 안된다. (**순환이 생기면, 순서를 생성할 수 없기 때문)

DAG는 이전 vertex에서 이어지는 vertex로 각 간선을 연결하므로, linear(선형화)할 수 있다.

B, A, D, C, E, F 순서이다.

 

그렇다면, 어떤 유형의 DAG를 선형화 할 수 있을까?

모두 가능하다.

     - post number가 감소하도록 수행하면 된다.

     - post(u) < post(v)인 간선 (u,v)만이 역방향 간선이 되고, DAG는 역방향 간선을 가질 수 없다.

 

Property DAG에서 모든 간선은 더 낮은 post 숫자를 지닌 정점에 다다른다.

     - DAG의 노드를 순서화하는 알고리즘은 선형 시간이 걸린다.

 

이러한 특성을 통해 다르게 보이는 특성 (acyclicity(순환성), linearizability(선형화), and the absence of back edge(역방향 간선의 부재))이 사실 하나이며, 같다는 것을 알 수 있다.

**DAG는 post 숫자를 감소시켜 선형화하므로, 가장 작은 post 숫자를 지닌 정점이 선형화의 마지막에 위치한다. 그리고 이 정점은 연결된 새로운 간선이 없으므로, sink(끝점)이다. **

 

Property 모든 DAG는 적어도 하나의 source(출처)와 하나의 sink(끝점)을 가진다.

     - 반드시 source가 존재하기 떄문에, linearization에 대해 다른 방법으로 접근할 수 있다.

•   source를 찾아서 출력하고, 그래프에서 source를 지운다.
•   그래프가 빌 때까지 이 과정을 반복한다.

##Question

이 방법으로 모든 DAG를 유효한 방법으로 linearization할 수 있을까?

그래프에 순환이 있다면 어떻게 될까?

이 알고리즘을 어떻게 선형 시간으로 구현할 수 있을까?

 

---

 

3.4 Strongly connected components

3.4.1 Defining connectivity for directed graphs

이전에 보았듯이, undirected 그래프에서 연결성은 분명하다. 연결이 되지 않은 그래프는 몇몇 연결된 성분으로 분해할 수 있다.

directed 그래프에서는 연결성이 조금 더 세밀하다.

해당 그래프는 연결된 것처럼 보이고, 간선을 떼어낼 수 없을 것 같다.

BUT 이 그래프는 연결되지 않았다.

     - G에서 B로 이동, F에서 A로 이동할 수 없다.

directed 그래프는 두 노드 u와 v는 서로의 경로가 있을 때 연결한다. -> 강한 연결 성분(strongly connected component) 집합으로 나눈다.

     - 점선으로 표기

       강한 연결 성분을 하나의 메타 노드로 줄인다. -> 이 결과 역시 DAG

        여러 개의 강한 연결 성분을 포함한 cycle은 강한 연결 성분들을 하나로 병합하기 때문.

 

Property 모든 directed 그래프는 그것의 강한 연결 성분의 DAG이다.

    - directed 그래프의 연결 구조는 두 계층으로 이루어져 있다.

    - 최상위 단계의 DAG는 간단한 구조(linearization).

    - 더 자세한 부분은 최상위 단계의 DAG 노드 하나를 자세히 들여다보면, 그 안의 full-fledged(완전한) 강한 연결

    성분을 검사할 수 있다.

 

 

3.4.2 An efficient algorithm

Property 1 만약 explore 서브 루틴이 노드 u에서 시작되었다면, u로부터 다다를 수 있는 모든 노드가 방문되어야 서브루틴이 종료된다.

    - 강한 연결 성분의 끝점에 놓인 노드에서 explore를 호출하면, 해당 노드의 값을 추출.   

      강한 연결 성분 sink가 두 개 있다.

    - 노드 K에서 explore를 시작하면, 노드 K가 속한 강한 연결 성분 전체를 순회하고 멈춘다.

 

 

##남은 문제

(A)   강한 연결 성분 끝점에 있는 노드를 어떻게 정확히 찾을 것인가?

(B)   첫 번째 성분이 발견되고 나면 어떻게 계속 진행하는가?

 

##남은 문제를 해결해보자.

(A)는 강한 연결 성분 끝점에 놓인다고 보장할 수 있는 노드를 고르는 쉽고 직접적인 방법은 없다.

하지만, 강한 연결 성분 source에 있는 노드를 얻는 방법은 있다.

 

Property 2 DFS에서 가장 높은 post 숫자를 갖는 노드는 반드시 강한 연결 성분의 source에 있어야한다. -> (**general한 속성이다)

     -  강한 연결 성분 source에 있는 노드를 찾는데 도움이 된다.

     - 하지만, 우리가 필요한 건, source가 아닌 sink를 찾는 일이다. 우리가 해온 일의 정반대의 일처럼 보인다.

해당 그래프(G’)는, 위에서의 그래프(G)와 정확히 정반대의 그래프이다.

하지만, G’와 G는 같은 강항 연결 성분을 가지고 있다.

따라서, G’에서 DFS를 수행하면, 가장 높은 post 숫자를 지닌 노드가 G’의 강한 연결 성분 source로부터 나오게 된다.

  -> 이 성분이 G의 강한 연결 선분의 sink이다.

 

Property 3 만약 C와 C’가 강한 연결 성분이고, C안의 노드로부터 C’안의 노드로 edge가 있다면, C 안에서 가장 높은 post 숫자는 C’안에 있는 가장 높은 post 숫자보다 크다.

Proof 두가지 경우를 고려할 수 있다.

• 만약, DFS가 C’ 전에 C를 방문한다면, 명백하게 C와 C’ 모두를 프로시저가 멈추기 전에 순회한다. (property 1) 따라서 C에서 방문한 첫 번째 노드가 C’의 어떤 노드보다도 더 높은 post숫자를 지닌다.
• 반대로, C’를 처음 방문하면, DFS는  C’의 모든 노드를 살피고 나서, C의 아무것도 살펴보지 않고 멈추게 될 것이다.

 

즉, property 3은 강한 연결 성분의 가장 높은 post 숫자를 감소시키는 순서로 배열하면, 강한 연결 성분들을 linearization할 수 있다는 것이다. (DAG에서 각 노드는 강한 연결 성분의 singleton(단위집합)이다)

     -> 이 과정을 통해 (A) 문제를 풀었다.

 

 

(B)문제를 풀어보자. (**포인트 : property 3)

첫번째 sink를 찾은 후에, 그래프에서 이를 지우면, 남은 노드 중에서 가장 높은 post 숫자를 지닌 노드는 G에서 남은 강한 연결 성분 끝점에 속한다. 따라서, G’에 대해 첫번째 DFS로부터 두번째 강한 연결 성분 등을 출력하는데 까지 post 숫자를 계속 사용할 수 있다.

     1. G’에 대해 깊이 우선 탐색을 실행한다.

     2. G에 대해 undirected 연결 성분 알고리즘을 실행하고, DFS 동안에 앞선 1단계부터 post 숫자가 감소하는 순서로 

      node를 처리한다.

      =>  해당 알고리즘은 선형 시간이고, linear term의 constant는 올바른 DFS의 두배이다.

 

##Question

선형 시간에 G’의 인접 리스트 표현을 어떻게 구축할 수 있나?

선형 시간에 어떻게 post값을 감소시키면서 G의 node들을 linearization할 수 있을까?

 

 

G에 대해 최종 알고리즘을 실행해보면, (G’의 DFS 탐색에서 감소하는 post 숫자)에 대해 설정한 ordering은 G, I, J, L, K, H, D, C, F, B, E, A가 된다. 2단계에서는 {G, H, I, J, K, L}, {D}, {C, F}, {B, E}, {A}와 같은 순서로 성분을 나타낼 수 있다.