討論串[問題] 在O(|V|)的時間內找到non-cut點
共 7 篇文章
內容預覽:
我在研究所考題裡面看到這個問題。. http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_102_01.pdf. 內的第五題. 給定一個無向連通圖，此圖必存在至少一non-cut點，使得移除此點之後圖仍然連通。. 設計一演算法在O(|V|)的時間內找出n
(還有80個字)
內容預覽:
嗯.. 其實這是 BFS 啦,. 只是你需要一點技巧來分析.. Non-cut point -> leaf in a tree.. 注意這個地方, 你只要找到 "一個" leaf 就行了,. 而且這個圖是 uni-directional.. The rough algorithm is... 1.
(還有295個字)
內容預覽:
技巧就是說破了不值一毛錢的小東西.. 舉個簡單的例子, 4 Node graph, as a ring.. The neighboring matrix is. 0 1 0 1 ;. 1 0 1 0 ;. 0 1 0 1 ;. 1 0 1 0 ;. So.. if you start from th
(還有384個字)
內容預覽:
這樣是O(|V|)嗎?. 如果你只是把逆邊砍掉的話這樣還是O(|V|+|E|)啊. 因為你只是把遍歷的的時間 sum(deg(v))變成 sum(deg(v))/2. 所以原本sum(deg(v)) = 2|E| 而現在是sum(deg(v))/2 = |E|. 現在假設有一張4階完全圖. 0 1
(還有213個字)
內容預覽:
我分成兩篇寫了.. 在第一篇有提到說 I don't go throught the edges in {V_1, V_{k}}.. Because I am generating a spanning tree,. so no need for circule.. Yes, and now the
(還有226個字)