拓?fù)渑判蛟?/h2>

1.點(diǎn)睛

一個(gè)無環(huán)的有向圖被稱為有向無環(huán)圖。有向無環(huán)圖是描述一個(gè)工程、計(jì)劃、生產(chǎn)、系統(tǒng)等流程的有效工具。一個(gè)大工程可分為若干子工程（活動(dòng)），活動(dòng)之間通常有一定的約束，例如先做什么活動(dòng)，有什么活動(dòng)完成后才可以開始下一個(gè)活動(dòng)。

用節(jié)點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系的有向圖，被稱為 AOV 網(wǎng)。

在 AOV 網(wǎng)中，若從節(jié)點(diǎn) i 到節(jié)點(diǎn) j 存在一條有向路徑，則稱節(jié)點(diǎn) i 是節(jié)點(diǎn) j 的前驅(qū)，或者稱節(jié)點(diǎn) j 是節(jié)點(diǎn) i 的后繼。若<i,j>是圖中的弧，則稱節(jié)點(diǎn) i 是節(jié)點(diǎn) j 的直接前驅(qū)，節(jié)點(diǎn) j 是節(jié)點(diǎn) i 的直接后繼。

在 AOV 網(wǎng)中弧表示了活動(dòng)之間存在的制約關(guān)系。例如，計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)。學(xué)生按照怎樣的順序來學(xué)習(xí)這些課程呢？

課程的名稱與相應(yīng)編號如下表所示。

如果用節(jié)點(diǎn)表示課程，用弧表示先修關(guān)系，若課程 i 是課程 j 的先修課程，則用弧<i,j>表示，課程之間的關(guān)系如下圖所示。

在 AOV 中不允許有環(huán)，否則會(huì)出現(xiàn)自己是自己的前驅(qū)情況，陷入死循環(huán)。怎么判斷在 AOV 網(wǎng)中是否有環(huán)呢？一種檢測的辦法就是對有向圖中的節(jié)點(diǎn)進(jìn)行拓?fù)渑判?。如?nbsp;AOV 網(wǎng)中的所有節(jié)點(diǎn)都在拓?fù)湫蛄兄?，則在 AOV 網(wǎng)中必定無環(huán)。

2.拓?fù)渑判?/h3>

拓?fù)渑判蛑笇?nbsp;AOV 網(wǎng)中的節(jié)點(diǎn)排成一個(gè)線性序列，該序列必須滿足：若從節(jié)點(diǎn) i 到節(jié)點(diǎn) j 有一條路徑，則在該序列中節(jié)點(diǎn) i 一定在節(jié)點(diǎn) j 之前。

拓?fù)渑判虻幕舅枷耄?/p>

1 選擇一個(gè)無前驅(qū)的節(jié)點(diǎn)并輸出。

2 從圖中刪除該節(jié)點(diǎn)和該節(jié)點(diǎn)所有發(fā)出邊。

3 重復(fù)步驟1、2,直到不存在無前驅(qū)的節(jié)點(diǎn)。

4 如果輸出的節(jié)點(diǎn)數(shù)少于 AOV 網(wǎng)中節(jié)點(diǎn)數(shù)，則說網(wǎng)中有環(huán)，否則輸出的序列即拓?fù)湫蛄小?/p>

拓?fù)渑判虿⒉皇俏ㄒ坏模缟蠄D中，節(jié)點(diǎn) C0 和 C5 都無前驅(qū)，先輸出哪一個(gè)都可以。

下面圖解是其中一種刪除順序。

拓?fù)湫蛄袨椋篊0、C5、C3、C2、C1、C4

在上述過程中有刪除節(jié)點(diǎn)和邊的操作，實(shí)際上，沒必要真的刪除節(jié)點(diǎn)和邊?？梢詫]有前驅(qū)的節(jié)點(diǎn)（入度為0）暫存到棧中，輸出時(shí)出棧即表示刪除。進(jìn)行邊的刪除時(shí)將其鄰接點(diǎn)的入度減1即可。例如下圖中刪除 C0 的所有發(fā)出邊，相對于 C3、C2、C1 節(jié)點(diǎn)入度減1。

3.算法步驟

1 求各節(jié)點(diǎn)的入度，將其存入數(shù)組 indegree[] 中，并將入度為 0 的節(jié)點(diǎn)入棧 S。

2 如果棧不空，則重復(fù)執(zhí)行以下操作：將棧頂元素 i 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中；將節(jié)點(diǎn) i 的所有鄰節(jié)點(diǎn)入度都減 1，如果減 1 后入度為 0，則立即入棧 S。

3 如果輸出的節(jié)點(diǎn)數(shù)少于 AOV 網(wǎng)中的節(jié)點(diǎn)數(shù)，則說明網(wǎng)中有環(huán)，否則輸出拓?fù)湫蛄小?/p>

4.圖解

AOV 網(wǎng)如下圖所示。

1 輸入邊時(shí)，累加節(jié)點(diǎn)入度并保存到數(shù)組 indegree[] 中，將入度為0 的節(jié)點(diǎn)入棧 S。

2 將棧頂元素 5 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中。將節(jié)點(diǎn) 5 的所有鄰接點(diǎn)(C3、C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

3  將棧頂元素 0 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中。將節(jié)點(diǎn) 0 的所有鄰接點(diǎn)(C1、C2、C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

4 將棧頂元素 3 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中。將節(jié)點(diǎn) 3 的所有鄰接點(diǎn)(C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

5 將棧頂元素 2 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中。將節(jié)點(diǎn) 2 的所有鄰接點(diǎn)(C1、C4)入度都減1，如果減1后，入度為0，則立即入棧 S。

6 將棧頂元素 4 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中。節(jié)點(diǎn) 4 沒有鄰接點(diǎn)。

7 將棧頂元素 1 出棧并保存到拓?fù)湫蛄袛?shù)組 topo[] 中。節(jié)點(diǎn) 1 沒有鄰接點(diǎn)。

8 ?？?，算法停止。輸出拓?fù)渑判蛐蛄小?/p>

拓?fù)渑判蛩惴▽?shí)現(xiàn)

1.拓?fù)鋱D

2.實(shí)現(xiàn)代碼

package graph.topoSort;
 
import java.util.Scanner;
import java.util.Stack;
 
public class TopoSort {
    static final int maxn = 105;
    static int map[][] = new int[maxn][maxn];
    static int indegree[] = new int[maxn];
    static int topo[] = new int[maxn];
    static int n, m;
    static Stack<Integer> s = new Stack<>();
 
    static boolean TopoSort() { // 拓?fù)渑判?
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0)
                s.push(i);
        while (!s.empty()) {
            int u = s.peek();
            s.pop();
            topo[cnt++] = u;
            for (int j = 0; j < n; j++)
                if (map[u][j] == 1)
                    if (--indegree[j] == 0)
                        s.push(j);
        }
        if (cnt < n) {
            return false;
        }
        return true;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
 
        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            map[u][v] = 1;
            indegree[v]++;
        }
        TopoSort();
        for (int i = 0; i < n - 1; i++)
            System.out.print(topo[i] + " ");
        System.out.println(topo[n - 1]);
    }
}

3.測試

以上就是Java實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ氖纠a的詳細(xì)內(nèi)容，更多關(guān)于Java拓?fù)渑判蛩惴ǖ馁Y料請關(guān)注腳本之家其它相關(guān)文章！

最新評論