[Data Structure] Graph

Definition

Undirected Graph

G = (V, E)

V : Vertices 頂點

E : Edges 邊 := (u, v)

Adjacent Vertexs

A vertex u is adjacent to vertex v ⇔ (u, v) ∈ E

Directed Graph｜Digraph

G = (V, A)

E : Arcs 邊 := (x, y);

x → y

• x: tail
• y: head

 Loop := (x, x)

Walk := (v₁, v₂, v₃, …, v_n), ∀ v_i, v_{i + 1} ∈ Walk ⇒ (v_i, v_{i + 1}) ∈ E

if v₁ != v_n ⇒ (v₁, v₂, v₃, …, v_n) is a open walk

Trail := (v₁, v₂, v₃, …, v_n) is a Walk ∧ if i != j ⇒ (v_i, v_{i + 1}) != (v_j, v_{j + 1}) (No Repeated Edge in the Trail.)

Path := (v₁, v₂, v₃, …, v_n) is a Walk ∧ if i != j ⇒ v_i != v_j (No Repeated Vertex in the Path.)

Circuit := (v₁, v₂, v₃, …, v₁) is a Closed Walk

Cycle / Simple Circuit

(v1, v2, v3, …, vn) is a cycle ⇔ vi == vj ∧ i < j iff i == 1 ∧ j == n

Degree

在 undirected graph 中，degree(v) := v 的 edges 數

Indegree

在 directed graph 中，indegree(v) := 起始於 v 的 edges 數

Outdegree

在 directed graph 中，indegree(v) := 終止於 v 的 edges 數

Internal Vertex / External Vertex / Branch Vertex

• internal vertex / inner vertex) := a vertex of degree at least 2
• external vertex / outer vertex / terminal vertex / leaf (in a tree) := a vertex of degree 1
• branch vertex (in a tree) := vertex of degree at least 3

Connected Component

Strongly Connected Component 強連通元件

指「每一個 vertex 都能由任意 vertex 抵達」的 directed graph
※ 只有一個 vertex 的 graph 也是 SCC

Kosaraju’s Algorithm

⭐️ Tarjan’s Strongly Connected Components Algorithm

Time Complexity: Tarjan’s SCC Algorithm ≅ Path-Based SC Algorithm ≥ Kosaraju’s Algorithm

• v.index 依其被遍歷順序的流水編號 
• v.low_link := min([w. index for w in scc(v)])

1. 還沒走過的路徑就持續呼叫遞迴函式 strong_connect()
   strong_connect() 的開頭會創建 v.index 和 v.low_link
2. 當走到了先前走過的 v_i
   由於先前走過的 v_i 預設的 v_i.low_link == v_i.index 比較小
   藉此更新走到 v_i 前的最後一個 v_j.low_link ← v_i.index
3. 之後遞迴函式 strong_connect() 會開始逐層的結束
   結束之後會把相應的 v_k.low_link 更新為 v_j.low_link == v_i.index
4. 回到 v_i 時，會從 stack 中將 v_i ~ v_k pop 出來作為新的 SCC
5. 不符合上述行為的 vertex 會自己作為一個新的 SCC

以
Ｄ → Ａ → Ｂ
↑ ↙︎
Ｃ
為例：

1. Ａ – 新增 Ａ(0, 0)
   → Ｂ – 新增 Ｂ(1, 1)
   → Ｃ – 新增 Ｃ(2, 2)
   ⇒ Ａ – Ａ 在 stack 中 ⇒ 修正 Ｃ(2, 20)
   ⇒ 以 Ｃ 的 low_link 修正 Ｂ(1, 10)
   ⇒ Ａ 的 index == low_link ⇒ 新增 SCC₁ {Ａ, Ｂ, Ｃ}
   
2. Ｂ – 略過 (已存在且已歸類為 SCC₁ 不在 stack 中)
3. Ｃ – 略過
4. Ｄ – 新增 Ｄ(3, 3)
   ⇒ Ａ – 略過
   ⇒ Ｄ 的 index == low_link ⇒ 新增 SCC₂ {Ｄ}

def tarjan(vertexes, edges):
  """
  Args:
    vertexes := [v_1, v_2, ...]
    edges    := {v_1: [w_11, w_12, ...], v_2: [w_21, w_22, ...], ...}
    
  """
  index = -1
  s = [] # stack
  vertexes = {v: {"index": None, 
                  "low_link": None, # low_link := the minimum index in scc
                  "on_stack": False} for v in vertexes}
  sccs = set()
  
  def strong_connect(v):
    nonlocal index, s, vertexes, sccs
    vertexes[v]["index"] = vertexes[v]["low_link"] = (index := index + 1)
    s.append(v)
    vertexes[v]["on_stack"] = True

    # compute v.low_link
    for w in edges[v]:
      if vertexes[w]["index"] is None: # not traversed yet
        strong_connect(w)
        vertexes[v]["low_link"] = min(vertexes[v]["low_link"], 
                                      vertexes[w]["low_link"])
      elif vertexes[w]["on_stack"]: # still in the stack, not categorized into scc yet
        vertexes[v]["low_link"] = min(vertexes[v]["low_link"], 
                                      vertexes[w]["index"])

    if vertexes[v]["index"] == vertexes[v]["low_link"]:
      scc = []
      while s:
        w = s.pop()
        vertexes[w]["on_stack"] = False
        scc.append(w)
        if w == v: break
      sccs.add(frozenset(scc))
  
  for v in vertexes:
    if vertexes[v]["index"] is None:
      strong_connect(v)
    
  return sccs

Path-Based Strong Component Algorithm (Gabow’s Algorithm)

Problems

• Leetcode # 210. Course Schedule II
• Leetcode # 1615. Maximal Network Rank
• Leetcode # 2846. Minimum Edge Weight Equilibrium Queries in a Tree

Last Updated on 2023/10/04 by A1go