Graph Traversal

○Depth-First Search (DFS)

 ▷G의 모든 Vertices, Edges를 탐색

 ▷G가 Conncted graph인지 확인

 ▷G의 Connected components를 계산

 ▷G의 Spannng forest를 계산

 

 ▷O(e + v) - 각 vertex/edge가 2번씩 마킹됨. (UNEXPLORED, VISITED/BACK)

 

 ▶Algorithm

  ▷모든 U, V를 UNEXPLORED로 마킹

 

  ▶모든 Vertices에 대해 DFS(G, v)를 적용

   ▷해당 vertex를 VISITED로 마킹 

   ▶vertex의 모든 incident edges에 대해

    ▷만약 UNEXPLORED라면, edge의 opposite를 받아옴.

     ▷opposite이 UNEXPLORED라면,  edge를 DISCOVERY로 마킹하고, opposite에 대해 DFS(G,v)

     ▷opposite이 UNEXPLORED가 아니라면 edge를 BACK으로 마킹

 

 

 ▶특성

  ▷모든 Vertices, Edges를 방문

  ▷DISCOVERY edges로 Spanning Tree를 만들 수 있다.

 

 

 ▶Path finding

  ▷원래 알고리즘에서 Stack추가 (목적지에 도달하면 Stack 반환)

  ▷방문시 push, 나갈시 pop.

 

 ▶Cycle finding

  ▷back edge (v, w)를 만나면 w까지의 stack을 반환

 

 

○Breadth-First Search (BFS)

 ▷G의 모든 Vertices, Edges를 탐색

 ▷G가 Conncted graph인지 확인

 ▷G의 Connected components를 계산

 ▷G의 Spannng forest를 계산

 

 ▷O(e + v) - 각 vertex/edge가 2번씩 마킹됨. (UNEXPLORED, VISITED/CROSS)

 

 ▶Algorithm

  ▷모든 U, V를 UNEXPLORED로 마킹

 

  ▶모든 Vertices에 대해 BFS(G, v)를 적용

   ▷해당 vertex를 VISITED로 마킹

   ▷새로운 Sequence (L_0)를 만들고 해당 Vertex를 insertBack

   ▷i = 0

   ▶L_i가 empty할 때 까지

    ▷새로운 Sequence (L_i+1) 생성

     ▶모든 L_i element에 대해

      ▶모든 incidend edges에 대해

      ▷만약 UNEXPLORED라면, edge의 opposite를 받아옴.

       ▷opposite이 UNEXPLORED라면,

        ▷edge를 DISCOVERY로 마킹

        ▷opposite을 VISITED로 마킹후, L_i+1에 insertBack

       ▷opposite이 UNEXPLORED가 아니라면 edge를 CROSS으로 마킹

    ▷i++

 

 

 ▶특성

  ▷모든 Vertices, Edges를 방문

  ▷DISCOVERY edges로 Spanning Tree를 만들 수 있다.

  ▷L_0을 root로 한 Tree로 봤을 때, 각 Level은 root에서 도달하는데 필요한 최소 edge 수이다.

 

 

※DFS vs BFS