103資訊學科培訓 圖論 - BFS & DFS & 應用 講者:林庭宇
前情提要 各位認識圖嗎?
基本概念 Yes No BFS & DFS 就是圖形的「搜索」 實作時分別需要用到 Queue & Stack 可求取距離、連通等基礎資料 應用極廣 知道Stack和Queue嗎? Yes No
BFS 廣度優先搜索(Breadth-first Search) 先搜索完叉路再往下走 由近而遠的搜索 把走過的路連起來會變成一棵tree You need a Queue
範例
DFS 深度優先搜索(Depth-first Search) 先搜索完整條路再去走叉路 把走過的路連起來也會變成一棵tree You need a Stack
範例again
BUT 要記得剪枝!!! 時間複雜度 看資料型態而定 Adjacency matrix -> O(V^2) Adjacency lists -> O(V+E) BUT 要記得剪枝!!! 記下走過的點,以免重覆走浪費時間
練習時間 ZJ a290 b224 a753 d908
OAO~~~ 讓我們繼續看下去 DFS延伸概念 判斷DAG(Direct Acylic Graph) 拓樸排序(Topological Sort) 連通分量(Connected Components) 關節點(割點,Cut Point) OAO~~~
DFS延伸概念 Discovery time Finishing time 1 5 7 6 2 4 3 2 4 1 8 7 6 8 5
DFS延伸2 Tree Edges: not yet discovered Back Edges: discovered but not yet finished Forward/Cross Edges: finished
DAG(Direct Acylic Graph) 有向無環圖 判斷方式:DFS 他沒有Back Edges!!!
拓樸排序 Topological Sort 將圖上的點進行排序 假如A -> B,則A要排在B之前 前提: 圖必須是一個DAG
做法: 1.先找出第一點 – 什麼點一定可以排在最前面? 2.進行拓樸排序 – 想想DFS延伸! => 1.任意一個沒有「入邊」的點 2.Finishing time!
拓樸範例 一個可行的拓樸排序: 9 2 0 5 6 3 7 8 1 4 Finishing time反排!!! 4 8 5 6 1 9 2 10 3
來個題目 ZJ a552 a454 d917
連通分量 連通關係(就有向圖來討論) 強連通>單向連通>弱連通 強連通-任兩點均有路來回 弱連通-化為無向圖後為相連圖形 單向連通-任兩點至少有單向路可走 強連通>單向連通>弱連通
強連通分量 strongly connected components(SCC) 用處:收縮圖形 怎麼找? -> 還是 DFS
關節點(割點,Cut Point) 無向圖中,少了就會使圖不連通的點
有圖有真相
怎麼找割點? -> DFS again!!! 用DFS tree來想
THE END P.S. 蒙地卡羅 is good!
補 - Stack 就像堆盤子一樣 遞迴就是一種Stack 陣列或STL
補 - Queue 就像排隊一樣(不考慮插隊) 陣列或STL Back