[理工] 105台大電機丙 資料結構

看板Grad-ProbAsk作者 (yellow)時間8年前 (2016/02/25 17:23), 8年前編輯推噓26(26推 0噓 26→)
留言52則, 11人參與, 最新討論串1/1
大家好，想跟大家討論一下最後一題， 題目大致是說undirected graph要求"strongly" connected components, 要求寫出及分析演算法。 我對於題目有些疑問，因為strongly connected應該是用來描述directed graph吧？ undirected graph就直接說(connected) components不是嗎（還是有人看過這個說法？） 為此我查了書上的定義， 1.Discrete and Combinatorial Mathematics: An Applied Introduction, 5e by Ralph P. Grimaldi p.351, Definition 7.15 A directed graph G on V is called strongly connected ... 2.Fundamentals of Data Structures in C, 2e by Horowitz p.270, A directed graph G is said to be strongly connected iff for every pair.... 所以我認為題目的敘述是有瑕疵的，若是要求undirected graph的components，可用 DFS/BFS來解； 但若是求directed graph的strongly connected components，就比較困難，沒看過 這個演算法應該很難自己想出來， Kosaraju's Algorithm http://www.csie.ntnu.edu.tw/~u91029/Component.html#5 各位的看法如何呢？謝謝。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.46.235.246 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1456392183.A.3B0.html
→
02/25 17:24, , 1F
我寫兩個 一個direct graph找SCC 另外一個一題意等於
02/25 17:24, 1F
兩個都寫最保險，佩服！
→
02/25 17:25, , 2F
undirect graph 上找component
02/25 17:25, 2F
→
02/25 17:27, , 3F
直接寫無向圖CC = SCC了
02/25 17:27, 3F
推
02/25 17:28, , 4F
我只寫undirected
02/25 17:28, 4F
→
02/25 17:28, , 5F
Kosaraju我沒搞懂過qq
02/25 17:28, 5F
推
02/25 17:28, , 6F
我也只寫無向 其實我覺得應該有人能寫出大概
02/25 17:28, 6F
→
02/25 17:29, , 7F
神手總是有的
02/25 17:29, 7F
→
02/25 17:30, , 8F
有向圖的情況, 用dfs找finish time,再把圖上邊都轉向,
02/25 17:30, 8F
→
02/25 17:30, , 9F
從finish time最晚的從新跑一次dfs
02/25 17:30, 9F
→
02/25 17:34, , 10F
某本algo名校秘笈上寫的那套,不曉得有無記錯
02/25 17:34, 10F
推
02/25 17:34, , 11F
欸欸想起來了 的確有這東西
02/25 17:34, 11F
→
02/25 17:35, , 12F
當下完全忘記 看來不是神手也能寫 只是我太廢QQ
02/25 17:35, 12F
推
02/25 17:35, , 13F
重點就那個轉向 要寫完整不知道要想多久
02/25 17:35, 13F
→
02/25 17:37, , 14F
記得是用adjacency matrix,把矩陣取轉置應該可吧
02/25 17:37, 14F
推
02/25 17:39, , 15F
應該可
02/25 17:39, 15F
→
02/25 17:40, , 16F
寫undirected就沒啥困難
02/25 17:40, 16F
那大家認為題目是否容易令人混淆呢？原意應該是考無向圖，但記得這題20%... ※ 編輯: InfiniteMan (114.46.235.246), 02/25/2016 17:45:36
推
02/25 17:45, , 17F
原來是考無向 我看成有向然後寫SCC的algo了!!!
02/25 17:45, 17F
→
02/25 17:47, , 18F
如果是無向 那G轉不轉G'根本沒差因為矩陣是對稱的
02/25 17:47, 18F
推
02/25 17:49, , 19F
我忘記scc是啥了所以XD
02/25 17:49, 19F
推
02/25 18:09, , 20F
我做的題目跟書上寫都是 direct scc .. 當下也傻眼
02/25 18:09, 20F
推
02/25 18:10, , 21F
我寫undirected 所以等價CC
02/25 18:10, 21F
→
02/25 18:14, , 22F
話說考成大好像很多人 還好我同學已經上榜 不搶名額0.0
02/25 18:14, 22F
推
02/25 18:16, , 23F
推文大概有一半正取 目測
02/25 18:16, 23F
→
02/25 18:17, , 24F
感覺只剩我要考了
02/25 18:17, 24F
推
02/25 18:29, , 25F
不過20分只考無向好像也怪怪的
02/25 18:29, 25F
→
02/25 18:33, , 26F
o大上了嗎
02/25 18:33, 26F
推
02/25 18:34, , 27F
假如手寫改的鬆 應該就靠選擇決勝負吧
02/25 18:34, 27F
→
02/25 18:34, , 28F
交大快出來了 大家集氣！
02/25 18:34, 28F
推
02/25 18:37, , 29F
交大出來啦 甲組爽辣!!!!!
02/25 18:37, 29F
推
02/25 18:38, , 30F
甲組上啦～
02/25 18:38, 30F
推
02/25 18:42, , 31F
甲組備2 乙組正取
02/25 18:42, 31F
→
02/25 18:43, , 32F
結果大家都不考成大了(?)
02/25 18:43, 32F
→
02/25 18:45, , 33F
可能喔XD
02/25 18:45, 33F
推
02/25 18:51, , 34F
我會去 有個同學目前只有中央 會去陪考
02/25 18:51, 34F
推
02/25 19:04, , 35F
...備3X 我數學到底多爛 交大掰QQ
02/25 19:04, 35F
→
02/25 19:04, , 36F
3x滿穩的吧
02/25 19:04, 36F
→
02/25 19:06, , 37F
甲組應該爆了吧 慘
02/25 19:06, 37F
推
02/25 19:10, , 38F
沒關係 有台大我讀台大 集氣 QQ
02/25 19:10, 38F
→
02/25 19:10, , 39F
拜託我也要台大QQ
02/25 19:10, 39F
→
02/25 19:13, , 40F
對阿也是有人台大正取其他miss 不怕 集氣 !
02/25 19:13, 40F
推
02/25 19:13, , 41F
幫g大集氣
02/25 19:13, 41F
推
02/25 19:19, , 42F
集氣!
02/25 19:19, 42F
推
02/25 19:19, , 43F
感謝兩位高手QQ
02/25 19:19, 43F
推
02/25 19:39, , 44F
g 大會備上拉 而且你台大也會
02/25 19:39, 44F
→
02/25 20:15, , 45F
g大我甲組也備3x誒 但現在在考慮去多工 有正取
02/25 20:15, 45F
推
02/25 21:47, , 46F
g大加油 在這版解那麼多題幫那麼多人了 會有好報的!
02/25 21:47, 46F
推
02/25 21:48, , 47F
g大OK的~好心有好報~!
02/25 21:48, 47F
→
02/25 21:50, , 48F
好心有好報
02/25 21:50, 48F
推
02/26 03:32, , 49F
幫g大集氣！
02/26 03:32, 49F
推
02/26 08:52, , 50F
感謝各位 希望能跟大家一起考上QQ
02/26 08:52, 50F
→
02/26 10:26, , 51F
g大很強 ok的！
02/26 10:26, 51F
→
12/13 21:37, , 52F
https://reurl.cc/Ylp2yL 這篇對DFS下去找SCC介紹的滿詳細的
12/13 21:37, 52F
‣ 更多 InfiniteMan 的文章
文章代碼(AID): #1MpiVtEm (Grad-ProbAsk)