103資訊學科培訓圖論 - BFS & DFS & 應用講者:林庭宇.

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

Presentation on theme: "103資訊學科培訓圖論 - BFS & DFS & 應用講者:林庭宇."— Presentation transcript: