Graph Vertex(Node)와 Edge(Arc)로 구성 인접(adjacent): 두 점이 연결되어 있음을 뜻함

• Complete graph: edge on every pair
• Sparse: edge=O(n)
• Dense: edge=Theta(n^2)
• Directd: 방향성
• Weighted: 가중치
• Cyclic: cycle(path of length 3+ starts ends at same node)
• Acyclic: no cycle
• Strongly connected: (directed) all nodes are reachable →cyclic
• weakly connected: (undirected) all nodes are reachable
• Tree=connected acyclic graph

Subgraph : 점 선택후 그 사이의 선들 아무거나 선택 Induced subgraph : 점 선택 후 그 안의 모든 선들 선택

Implementation

1. Adjacency Matrix(인접 행렬)

   

2. Adjacency List Array-Based: list Linked chain Single Array Multi Array

   

• DFS Stack, Recursive, Preorder

  • Adj-list: O(n+e)
  • Adj-Mat: O(n^2)

  Using DFS

  • Use n-1 edge→spanning tree
  • Connected 판별: can visit all nodes from any node?
  • Finde path from v to w
    1. Start DFS at v
    2. Terminate when w is visited / no more unvisited nodes
  • Strongly-Connected Components 찾기(Directed)
    1. Do DFS of G, 방문한 순서를 기록해놓음(처음 방문→높은 점수)
    2. reverse all directions
    3. 1)의 priority를 기준으로 DFS를 순서대로 시작한다. 다음 노드를 고를 때에는 priority가 높은 노드를 고른다. →distinguish components

• BFS Queue, Iterative

• Topological Sort

  • DFS-Based Topological sort
    1. Start DFS
    2. if visited→skip
    3. recursion ends→print
    4. reverse printed sequence

  

Shortest Path In weighted digraph find minimum cost path

• Single pair (single src, single dst) / A* search
• Single-src (single src, all dst) / Greedy, Bellman-fold
• Single-dst (all src, single dst)→reduced to single source by reversing
• All-pairs (all src, all dst) / Greedy*n, Floyd, Johnson

1. Greedy(Dijkstra’s Algorithm) Dynamic programming

   • Complexity

     • Scanning: O(n^2) All node→all dst: O(n^2) all edges: O(e)
     • MinHeap: O(elogn) n Deletemin: O(nlogn) e PriorityUptade: O(elogn)

     →nlogn in sparse graph, n^2logn in dense graph

     

     S is final answer; shortest path

     

2. All pairs - Greedy n time for sparse O(n^2logn) for dense O(n^3logn) →not efficient

3. All pairs - Floyd’s Algorithm Djikstra for all pairs O(n^3) works even with negative cost, non-negative cycle

• Prim’s Algorithm

  1. Start with any node
  2. add CHEAPEST edge

  use Priority Queue, D[k]: shortest distance from Tree to node k Adj-Matrix→O(n^2); better with dense graph Adj-List&MinHeap→O(elogn); better with sparse(e=n) graph

  *Why Prim’s Algorithm Works? MST property: it satisfies Greedy-Choice property

  

  

• Kruskal’s Algorithm

  1. Start with no edge
  2. sort edges (eloge)
  3. add minimum edge (loge), union/find(loge)
  4. if cycle→skip

  →O(eloge); Sparse

  *Union-Find problem By adding edges, they form several different components, and we should prevent making cycle →if edge connects two different component, insert →if edge’s two nodes are in same component, skip→Acyclic

Applications of MST clustering →routing networks, web search, sky objects configuration Single Link clustering: Maximize distance between closest clusters : Equal to Kruskal’s Algorithm; stop at N components Sollin’s Algorithm

1. start with n-vertex forest
2. each component select least-cost edge to connect with other
3. eliminate cycle

complexity: O(ElogV)