2016/11/25 Algorithm

今天上22.3~22.4


22.3
DFS有四種edge類型, 分別是Tree,Back,Forward,Cross edge四種, 它有其priority

灰: 已有起始時間, 沒有結束時間(已起始, 未結束)
黑: 已結束
白: 未走到

當你由灰看到白, 那是tree edge
當你由灰看到灰, 是Back edge (其祖先尚未結束)
當你由灰看到黑, 可能是 Forward edge 或 Cross edge
比較起始時間, 較晚是Forward edge, 較早是Cross edge

以上是對有向圖而言,
對無向圖, 只有Tree,Back edge兩種

因為Back edge基本等同於Forward edge, 定義為Back edge
Cross edge不會存在, (這需要proof)
因為假若Cross edge存在, 表示這兩點在最一開始就是連通的,(因為無向)
那麼怎麼可能之前在拜訪黑點時, 沒有找到現在的這個灰點呢?
by contradiction 得證


22.4
Topological sort是一種排程方法, 描述一種"滿足等待關係"
其方法很簡單, 在做DFS時maintain一個stack, 對每一個結束的node,  當記錄結束時間時, 將此node丟進stack中, 再依序pop出來即是答案(i.e. 結束時間的相反順序)