Topological Sorting

• Condition
  • 사이클이 없는 Directed Graph
• Topological order
  • x로 부터 y로 가는 edge가 있다면 vertex x가 y보다 선행하는 vertices의 오더를 가짐
  • 일반적으로 directed 그래프는 많은 토폴로지컬 오더를 가진다.
  • Θ(|V|+|E|)

       

  • 
  • Order를 순서를 정하는 방법
    • Successor가 없는 vertex를 선택하여 sorting container에 넣음
    • 해당 vertex와 edge를 삭제하고 다시 Successor가 없는 vertex를 선택하는 과정을 반복
    • Graph의 원소가 없어질 때 까지 반복함.
    • 결과적으로 sorting container는 topological order를 가지게 됨.
    • 
  • Pseudo code.
    • TopologicalSort(v)

      loop v := [0, v.size)

      v.visit := False        // init

      loop v := [0, v.size)

      if v.visit = False

      DFS-TS(v)

         

      //

      //        successor가 없는 노드 까지 내려 가서 list header부터

      // 차곡차곡 채워 올라오는 알고리즘.

      //

      DFS-TS(v)

      v.visit := True

      loop x := v.adjacent

      if x.visit = False

      DFS-TS(x)

      list.insertheader(v)                // 연결 리스트 맨앞에 넣음

  • 

       

  • 

       

  • 

Spanning Trees

• 그래프 G의 모든 vertex를 다 담고 있는 subgraph로서의 트리
  • Tree
    • 사이클이 없는 Connected graph
    • n개의 vertices를 가지고 있다면 edge는 항상 n - 1임.
  • 단, 그래프 G는 Undirected connected graph
  • 

MST, Minimum Spanning Tree

• 모든 edge의 weight의 합이 최소인 Spanning Tree
  • 단, 그래프 G는 Weighted connected graph임
• Create Algorithms
  • Prim
    • Minimum spanning tree를 찾는 Greedy algol.
    • G = (V,E)

      T = (V,F)

      F = {x | F is subset of E}

      Y = {y | Y is subset of V}, Minimum spanning tree를 구성하는 edge로 promising 하다고 이야기 함.

         

      loop Y=V

      V-Y로 가는 edge중 가장 cost가 작은 edge를 선택.

      선택된 egde의 vertex는 Y에 삽입.

      edge는 F로 삽입.

      - complexity

      • O(E*V)
      • O(E*lnV), 힙을 사용할 경우.
  • 다시 말해서 MST가 되는 Promising set에 포함되지 않은 unvisited vertex중에서 가장 작은 weight를 가지는 edge랑 vertex를 선택하여 promising group에 넣는 과정을 반복.
  • 

       

  • 

       

  • 

       

  • 

Shortest Paths

• Condition
  • Weighted Graph
  • Undirected 그래프의 경우 양방향성을 가진 것으로 생각 하여 생각 할 수 있음.
• edge의 weight 합이 최소가 되는 path
• Dijkstra Algorithms
  • Promising Group의 Starting vertex로 부터 unvisited vertex로 가는 distance가 가장 작은 것을 선택하여 Promising group에 넣음
  • Promising group외부에 unvisited vertex가 없을 때 까지 반복
  • Prim과 다른 것은 distance를 relaxation 하는 단계가 있다는 것임.
  • 

       

  • 

Euler Circuit

• 오일러 경로
  • 그래프의 모든 edge를 한번씩만 통과하는 path를 이야기 함.
  • 필요 충분 조건
    • 두 개의 vertex만이 홀수개의 degree를 가진 Connected 그래프이어야 함.
• 오일러 회로
  • 오일러 경로 중에서 시작 vertex와 끝이 나는 vertex가 동일한 path
• 오일러 그래프
  • 오일러 회로를 가지고 있는 그래프.