神奇的圖論技巧(進階圖論)

動機

tarjan的dfs好強!!

Articulation point (tarjan的dfs)

祖先與每一棵子樹之間都有 back edge ，則此點不是關節點 祖先與其中一棵子樹之間缺少 back edge ，則此點就是關節點。

怎麼確認祖先關係? 用dfs走每一個點，給每個經過的點都標一個時間，祖先時間一定比較小

所以只要看每個child最遠可以到哪(earliest[child])，或是說透過back edge穿越時空，只要沒有超過祖先的時間那麼祖先一定是關節點

但根結點沒有祖先，怎麼判斷? 有沒有一個以上的child

接著就是怎麼找earliest earliest原定是每個child最遠可以到哪 那是怎麼走，怎麼到達下一個點? (因為這與計算最遠的定義有關) dfs，所以earliest是透過dfs遞迴定義，但還有back edge要處理

因為是用dfs，所以earliest要確認dfs能到的最遠距離

earliest[root] = min(earliest[root], earliest[child])

同時back edge能也走，所以要直接看他的時間，來更新earliest

earliest[root] = min(earliest[root], child.time)

同時這個earliest的演算法(tarjan)，還會再求scc看到

earliest = defaultdict(lambda x: float('inf'))
vis = defaultdict(bool)
timestamp = 1
ap = []
def setTime(root):
  root.time = earliest[root] = timestamp
  timestamp += 1

def dfs(root, fa):
  setTime(root)
  vis[root] = True
  cnt_of_child = sum(1 for child in root.chilren if not vis[child])
  for child in [child for child in root.chilren if child is not fa]:
    if vis[child]:
      # 不在當前的dfs路徑上(back edge)，所以取時間點就好
      earliest[root] = min(earliest[root], child.time)
    else:
      dfs(child, root)
      # 在當前的dfs路徑上，所以取越遠越好
      earliest[root] = min(earliest[root], earliest[child])
      if root.time <= earliest[child]:
        # child沒辦法飛超過祖先，祖先就是ap
        ap.append(root)
  if fa is None and cnt_of_child > 1:
    # root超過一個子樹
    ap.append(root)

def get_ap(graph):
  for root in graph.V():
    if not vis[root]:
      dfs(root, None)
  return ap

Bridge

基本與Articulation point一樣

但現在存的是邊，所以

不用看root是ap的case
依舊不能飛超過祖先，但是因為這是邊，所以要把剛好落在祖先的邊去掉

root.time <= earliest[child] => root.time < earliest[child]

earliest = defaultdict(lambda x: float('inf'))
vis = defaultdict(bool)
timestamp = 1
bri = []
def setTime(root):
  root.time = earliest[root] = timestamp
  timestamp += 1

def dfs(root, fa):
  setTime(root)
  vis[root] = True
  for child in [child for child in root.chilren if child is not fa]:
    if vis[child]:
      # 不在當前的dfs路徑上(back edge)，所以取時間點就好
      earliest[root] = min(earliest[root], child.time)
    else:
      dfs(child, root)
      # 在當前的dfs路徑上，所以取越遠越好
      earliest[root] = min(earliest[root], earliest[child])
      if root.time < earliest[child]:
        # ap在root下面
        bri.append((root,child))

def get_ap(graph):
  for root in graph.V():
    if not vis[root]:
      dfs(root, None)
  return

Connected Components

就是找相連起來的部分

vis = defaultdict(bool)
def dfs(root):
  ret = []
  if not vis[root]:
    vis[root] = True
    for child in root.children:
      ret += dfs(child)
  return ret

def cc(graph):
  for root in graph.V():
    if not vis[root]:
      print(dfs(root))

Strongly Connected Components

dfs走兩次，一次是順向，第二次是逆向

順便提一下，現在google到的作法都是分兩個dfs，一個收order，另一個收scc

但第一個dfs的order卻放在dfs最後才收，之後再reverse，去跑第二個dfs

但其實只要把order往前放就是順序去收order了，就不用再reverse

def dfs(root, vis, before):
  if not vis[root]:
    vis[root] = True
    before(root)
    [dfs(child, vis, before, after) for child in root.children]

def get_scc(graph):
  vis = [False] * len(graph.V())
  order = []
  for root in graph.V():
    if not vis[root]:
      dfs(root, vis, lambda root: order.append(root))
  
  # 把所有edge反向
  graph.reverse() # 又叫transpose
  
  vis = [False] * len(graph.V())
  for root in order:
    if not vis[root]:
      scc = []
      dfs(root, vis, lambda root: scc.append(root))
      print(scc)

另一個就是利用Articulation point的方法

題外話，Tarjan這個方法真的神

原本ap是看child有沒有飛過祖先來判定ap，這裡是要scc，所以只要這個點的最早就是自己，那從這點開始的都是scc

scc = []
vis = defaultdict(bool)
earliest = defaultdict(int)
def dfs(root):
  if not vis[root]:
    nodes = [root]
    vis[root] = True
    for child in root.children:
      if vis[child]:
        earliest[root] = min(earliest[root], child.time)
      else:
        nodes += dfs(child, nodes + [child])
        earliest[root] = min(earliest[root], earliest[child])
    
    if earliest[root] == root.time:
      scc.append(nodes)
      return []
    else:
      return nodes

def tarjan_scc(graph):
  for v in graph.V():
    dfs(v)
  return scc

Cycle

一般的cycle，用3個狀態表示沒碰過、還在dfs、處理完了之後就是dfs

# 0: unhandled, 1: processing, 2: done
vis = defaultdict(int)

def dfs(root):
  if vis[root] == 0:
    vis[root] = 1
    for child in root.children:
      if vis[root] == 1:
        raise ['cycle', root]
      else:
        dfs(child)

def cycle(graph):
  try:
    for root in graph.V():
      if vis[root] == 0:
        dfs(root)
  except e:
    print('cycle exist')

負環:

Bellman-Ford algorithm
- V個點，把E個邊，對應到的終點用邊去延伸
  - 如果有負環，就會有到最後還可以縮小路徑的點，就會有環
Floyd-Warshall algorithm
- V個點 * V個點，再列舉V個點做中間點
  - 只要有一個距離是扣到變成負的，就會有環

Bipartite

把點分成兩邊，每一點只能連到另一邊

用bfs，去allocate所有連到的點到另一邊，之後有兩個case

child沒分配過

就給另一邊

child分配過了

side = defaultdict(lambda x: -1)

def check_Bipartite(graph):
  q = deque()
  for root in graph.V():
    if side[root] == -1:
      side[root] = 0
      q.append(root)
      while q:
        child = q.popLeft()
        if side[child] == -1
          side[child] = side[root] ^ 1
        elif side[root] == side[child]:
          return False
  return True

Maximum Bipartite Matching

Maximum Bipartite Matching: 讓最多點被match掉

match: 湊成一對，每個點不是在某一對，就是沒有在任何一對

證明、相關概念很複雜，反正就是有得match就match，或是看他能不try到別的match(argument path)，直到無法match 詳細說明看這裡

所以可以直接用dfs一直match，每個點都try一遍

used = defaultdict(bool)
match = defaultdict(lambda x: None)
def try_kuhn(root):
  if used[root]:
    return False
  else:
    used[root] = True
    for child in root.children:
      if not match[child] or try_kuhn(child):
        match[child] = root
        return True
    return False

def lets_match(bipartile):
  for v in bipartile.V():
    try_kuhn(v)
  return match

因為只是一直塞match，所以可以先做一些明顯的match

def lets_match(bipartile):
  for v in bipartile.V():
    for child in v.children:
      if not match[child]:
        match[child] = root
        used[root] = True
        break
  
  for v in bipartile.V():
    try_kuhn(v)
  return match

2-SAT

原本SAT是任意個變數or，再and 但2-SAT是只有2個變數or(item)，再and

這樣每個item都可以用imply(a or not b)，與交換率生出兩個imply 之後構成一個imply graph

之後就是求scc，看scc中有沒有x與not x同時在，有就是not sat

整個時間都是在找scc，所以時間複雜度是O(V+E)

2 - SAT

Eulerian path

歐拉路徑的條件是

degree為奇數的點只能是0或是2
- 他們就是起、終點
剩下的degree都只能是偶數

degree就是每個點有多少edge

所以確定圖符合條件，剩下就是隨便走出一條路，之後把所有路合併起來 (為什麼要合併? 因為可能是cycle)

實作就是用dfs在最後塞就好，自然就把所有路合併起來了

path = []
vis = defaultdict(bool)
def dfs(root):
  if not vis[root]:
    vis[root] = True
    for child in root.children:
      dfs(child)
    path.append(root)

tree的同構

tree hash是為了判斷tree的同構，但是python可以直接用string做hash，所以可以用任何一種序的string當成key

trees = defaultdict(int)

def post(root):
    if not root:
        return ''
    else:
        tree = f'{post(root.left)},{root.val},{post(root,right)}'
        trees[tree] += 1
        return tree

post(root)
[print(tree) for tree,val in trees.items() if val > 1]

Ref

Finding articulation points in a graph in O(N+M) Finding bridges in a graph in O(N+M) Search for connected components in a graph Checking a graph for acyclicity and finding a cycle in O(M) (M就是E) Finding a negative cycle in the graph Check whether a graph is bipartite Finding strongly connected components Building condensation graph Kuhn’s Algorithm for Maximum Bipartite Matching 强连通分量 Finding the Eulerian path in O(M)

動機#

Articulation point (tarjan的dfs)#

Bridge#

Connected Components#

Strongly Connected Components#

Cycle#

Bipartite#

Maximum Bipartite Matching#

2-SAT#

Eulerian path#

tree的同構#

Ref#

動機