[理工] 離散 拓撲排序演算法

看板Grad-ProbAsk作者 (Magic)時間8年前 (2015/11/04 14:16), 編輯推噓1(1推 0噓 13→)
留言14則, 3人參與, 最新討論串1/1
板上各位高手大大好~ 這邊想請教一下，課本講的這個拓撲排序演算法的step2有點看不太懂，它說在Hk中選一個點Vk使得在Hk中無邊{x,Vk},其中x在Vk的下方，這是什麼意思，x指的是在圖中與Vk沒有相連的點嗎？？我看它旁邊的處理過程好像是選A,可是A的下方沒有點啊？那x又是那一個點？另外一個問題是我可以一開始選C或D嗎？ 麻煩各位幫忙看一下感謝！ http://i.imgur.com/9ilYkDn.jpg
http://i.imgur.com/k9lKTjL.jpg
手機排版請見諒！！ ----- Sent from JPTT on my Samsung SCH-I939. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.64.230.205 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1446617769.A.84D.html
→
11/04 18:05, , 1F
我的想法是x為任意點，而x為Vk下方的點。
11/04 18:05, 1F
→
11/04 18:05, , 2F
以k=1為例，一開始的漢斯圖為H1，所以要找一點來作為V1
11/04 18:05, 2F
→
11/04 18:05, , 3F
，那要找哪一點呢？按照step2，V1與V1下方的點沒有邊。
11/04 18:05, 3F
→
11/04 18:05, , 4F
B的下方有ACDE，D的下方有AE，C的下方有A，E的下方有A
11/04 18:05, 4F
→
11/04 18:05, , 5F
，而BDCE的下方除了有點也有與他們相連的邊。另外，只
11/04 18:05, 5F
→
11/04 18:05, , 6F
剩A沒有下方的點，所以理所當然的沒有與下方點相連的
11/04 18:05, 6F
→
11/04 18:06, , 7F
邊。
11/04 18:06, 7F
→
11/04 18:06, , 8F
因此，A必定等於V1。接著按照step3去掉與A相連的邊後，
11/04 18:06, 8F
→
11/04 18:06, , 9F
就成為H2圖。
11/04 18:06, 9F
→
11/04 18:06, , 10F
同理可推，由H2圖知道下一個V2可以選擇C或E。
11/04 18:06, 10F
→
11/04 18:06, , 11F
希望幫到你。
11/04 18:06, 11F
→
11/04 22:52, , 12F
原來是這樣想的，有點懂了！，感謝ling大大詳細的解說^^ 真
11/04 22:52, 12F
→
11/04 22:52, , 13F
的感恩！！
11/04 22:52, 13F
推
11/05 10:31, , 14F
謝謝L大，終於搞懂了!
11/05 10:31, 14F
‣ 更多 dslin 的文章
文章代碼(AID): #1MEQAfXD (Grad-ProbAsk)