算法 1 用 BFS 進(jìn)行拓?fù)渑判?/div>
為了解決本問題，下面讓我來探究一下拓?fù)湫虻囊恍┬再|(zhì)。以
圖 1 為例，節(jié)點(diǎn) 0 毫無疑問排在最后。除了節(jié)點(diǎn) 0 以外，有三條互相平行的路徑：
6 →
4 →
1、
3→
9 →
2 和
5 →
7 →
8。一條路徑上的各個節(jié)點(diǎn)的先后關(guān)系都是不能改變的，比如路徑
6 →
4 →
1 上的三個節(jié)點(diǎn)在拓?fù)湫蛑校欢ㄊ?nbsp;
6 在最前，
1 在最后。但是，互相平行的各條路徑，在總的拓?fù)湫蛑?strong style="line-height: normal; ">任意交錯都是合法的。比如，以下都是
圖 1 的合法拓?fù)湫颍?br style="line-height: normal; ">
6 4 1 3 9 2 5 7 8 0、
3 6 9 4 5 1 7 8 2 0、
5 6 4 7 3 8 1 9 2 0、
3 5 6 4 1 7 9 2 8 0、
6 5 7 8 4 3 9 2 1 0。
怎么才能找出題目要求的拓?fù)湫蚰兀吭谶@里，我想用
字典序最先的拓?fù)湫騺硪鲞@個算法。
算法 2 可以求出字典序最先的拓?fù)湫颉?br style="line-height: normal; ">
1. 把所有入度為 0 的節(jié)點(diǎn)放進(jìn)優(yōu)先隊(duì)列 PQ
2. WHILE： PQ 不是空隊(duì)列
3. 從 PQ 中取出編號最小的元素 a，把 a 添加到答案的尾部。
4. FOR：所有從 a 出發(fā)的邊 a → b
5. 把 b 的入度減 1。如果 b 的入度變?yōu)?0，則把 b 放進(jìn)優(yōu)先隊(duì)列 PQ。 |
算法 2 求出字典序最先的拓?fù)湫?/div>
可見，
算法 2 和
算法 1 基本一樣，只是把隊(duì)列改成了優(yōu)先隊(duì)列。用它求出的
圖 1 的字典序最先的拓?fù)湫驗(yàn)椋?font color="#339900" style="line-height: normal; ">
3 5 6 4 1 7 8 9 2 0。但是這顯然不是本題要求的答案，因?yàn)楣?jié)點(diǎn) 1 的位置還不夠靠前。
算法 2 可以算是一個貪心算法，每一步都找編號最小的節(jié)點(diǎn)。但是對于
圖 1 中的三條路徑，頭的編號比較小的，不一定要先出隊(duì)列。正確的步驟應(yīng)該如下：
- 節(jié)點(diǎn) 0 的位置是鐵定在最后的，不用考慮。只考慮剩下的三條路徑。
- 先找編號最小的，節(jié)點(diǎn) 1。把它和它所在的路徑中位于它前面的節(jié)點(diǎn)全部拿出來。目前的答案是 6 4 1，這樣， 節(jié)點(diǎn) 1 就盡量靠前了。
- 再找剩下的節(jié)點(diǎn)中編號最小的，節(jié)點(diǎn) 2。把它和它所在的路徑中位于它前面的節(jié)點(diǎn)全部拿出來。目前的答案是 6 4 1 3 9 2 ，這樣，節(jié)點(diǎn) 2 就盡量靠前了。
- 只剩下一條路徑了，只能依次把其中的節(jié)點(diǎn)拿出來。最后答案就是 6 4 1 3 9 2 5 7 8 0。
顯然，
算法 2 的貪心策略對于這個問題是不可行的。不能著眼于每條路徑的頭，而是要找編號最小的節(jié)點(diǎn)在哪條路徑上，優(yōu)先把這條路徑拿出來。但問題在于，在 BFS 的過程中，我們只能看到每條路徑的頭，看不到后面的節(jié)點(diǎn)，這該怎么辦呢？
讓我們換個角度想一想，節(jié)點(diǎn) 3 和 6，應(yīng)該是 6 先出隊(duì)列，因?yàn)楣?jié)點(diǎn) 1 在 6 的后面。這和節(jié)點(diǎn) 3 和 6 的編號大小沒有任何關(guān)系。但是，再看另外兩條路徑的尾部，節(jié)點(diǎn) 2 和 8，可以肯定地說，2
一定先出隊(duì)列，因?yàn)樗鼈兒竺娑紱]有別的節(jié)點(diǎn)了，這個時候完全以這兩個節(jié)點(diǎn)本身的編號大小決定順序。歸納起來就是說，對于若干條平行的路徑，
小的頭部不一定排在前面，但是
大的尾部一定排在后面。于是，就有了
算法 3。
1. 把所有出度為 0 的節(jié)點(diǎn)放進(jìn)優(yōu)先隊(duì)列 PQ
2. WHILE： PQ 不是空隊(duì)列
3. 從 PQ 中取出編號最大的元素 a，把 a 添加到答案的頭部。
4. FOR：所有指向 a 的邊 b → a
5. 把 b 的出度減 1。如果 b 的出度變?yōu)?0，則把 b 放進(jìn)優(yōu)先隊(duì)列 PQ。 |
算法 3 求出本題目要求的拓?fù)湫?/div>
我覺得這道題目確實(shí)挺奧妙的，我搞了很久才想通
算法 3 為什么是正確的，特地在此寫一下。