[理工] [演算法]-今天台大考的

看板Grad-ProbAsk作者 (1up)時間16年前 (2010/02/27 23:35), 編輯推噓2(2推 0噓 8→)
留言10則, 5人參與, 最新討論串1/1
設計一個演算法 要在O(V)的時間內判斷ㄧ個圖是否為acyclic 圖以adjancy list實作 還有不要說是用DFS............... DFS是O(V+E)，除非你能說他不用看所有的邊..... 回家一直想還是想不出來 拜託了... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.115.26.67
→
02/27 23:48, , 1F
我的想法是紀錄每個點的顏色 首先全部都是白色
02/27 23:48, 1F
→
02/27 23:48, , 2F
起點是黑色 接下來把起點連到的所有點都標為黑色
02/27 23:48, 2F
→
02/27 23:49, , 3F
並且把所有點連回起點的路徑刪掉
02/27 23:49, 3F
→
02/27 23:49, , 4F
最後若遇到下一個點是黑色的 則表示有cycle
02/27 23:49, 4F
→
02/27 23:50, , 5F
不知道這樣對不對= =
02/27 23:50, 5F
→
02/28 00:02, , 6F
利用back edge,其他大同小異
02/28 00:02, 6F
推
02/28 08:17, , 7F
用一般的DFS就可以了, 發現back edge立刻終止程式
02/28 08:17, 7F
推
02/28 08:19, , 8F
應該是無向圖吧 -> acyclic圖的邊數 < |V| -> DFS修改一下.
02/28 08:19, 8F
→
02/28 08:20, , 9F
|E|的檢查個數不會超過|V|, cost=O(|V|+|V|)=O(V)
02/28 08:20, 9F
→
02/28 11:12, , 10F
好像是耶......那時候想太多了 慘~~~~~
02/28 11:12, 10F
‣ 更多 hungyanbin 的文章
文章代碼(AID): #1BYJkf2G (Grad-ProbAsk)