在研究拓?fù)渑判蛑埃葋砹私庖粋€概念。

AOV網(wǎng)（Activity On Vertex Network）

什么叫AOV網(wǎng)呢椅挣？在生活中經(jīng)常有這種情況遂庄，一項大的工程寥院，常常被分為多個小的子工程，然后小的子工程中之間可能存在一定的先后順序涛目，即某些子工程必須在其他一些子工程完成后才能開始秸谢。

在現(xiàn)代化管理中，人們常常用有向圖來描述和分析一項工程的計劃和實施過程霹肝，其中子工程被稱為活動（Activity）

• 頂點表示活動估蹄，有向邊表示活動之間的先后關(guān)系，這樣的圖沫换，簡稱AOV網(wǎng)

例如：下圖就表示一個AOV網(wǎng)

圖中的每一個頂點就代表一個子工程（Activity）臭蚁，有向邊代表活動之間的先后順序與依賴關(guān)系，例如箭頭A→B，就表示需要先完成活動A才能開始活動B垮兑，所以B完成以后才能開始活動C和活動D冷尉，只有活動C，活動B系枪，活動D都完成以后雀哨，才能開始活動E，活動E完成以后私爷，才能開始活動F雾棺。所以上圖AOV網(wǎng)中活動之間的依賴關(guān)系如下

• B依賴于A
• C依賴于B
• D依賴于B
• E依賴于B，C衬浑，D
• F依賴于E

通過這個依賴關(guān)系垢村，可以觀察到，一個 頂點的依賴嚎卫，是由該頂點的inEdges（入度）決定的嘉栓。即有多少條邊進(jìn)入該頂點，如果該頂點有3條邊進(jìn)入拓诸，則說明該頂點有3個依賴

一個標(biāo)準(zhǔn)的AOV網(wǎng)需要滿足的條件：必須是一個有向無環(huán)圖（Directed Acyclic Graph侵佃，簡稱DAG）

拓?fù)渑判颍═opological Sort）

什么叫拓?fù)渑判颍紫冉Y(jié)合下圖來理解一些基本概念

1. 前驅(qū)活動：有向邊起點的活動稱為終點的前驅(qū)活動奠支；例如B稱為C的前驅(qū)活動
   • 只有當(dāng)一個活動的前驅(qū)全部完成后馋辈，這個活動才能進(jìn)行；例如E只有當(dāng)全部前驅(qū)B倍谜，C迈螟，D完成以后，才能進(jìn)行
2. 后繼活動：有向邊終點的活動稱為起點的后繼活動尔崔；例如E稱為C的后繼活動

什么叫拓?fù)渑判颍?/p>

• 將AOV網(wǎng)中所有的活動答毫，排成一個序列，使得每一個活動的前驅(qū)活動都排在該活動的前面季春；也就是說拓?fù)渑判驅(qū)⑺械幕顒优藕眯蚝笙绰В鶕?jù)這個順序，恰好能將所有的活動都執(zhí)行完

所以载弄，上圖的AOV網(wǎng)耘拇，如果要進(jìn)行拓?fù)渑判颍罱K排序的結(jié)果如下

• A→B→C→D→E→F 或者
• A→B→D→C→E→F

結(jié)果并不一定是唯一的宇攻。

那應(yīng)該如何實現(xiàn)拓?fù)渑判蚰兀?/p>

實現(xiàn)思路

實現(xiàn)拓?fù)渑判虮古眩梢岳每ǘ魉惴ǎ↘ahn與1962年提出）完成拓?fù)渑判?/p>

• 假設(shè)L是存放拓?fù)渑判蚪Y(jié)果的列表
  1. 把所有入度為0的頂點放入L中，然后把這些頂點從圖中去掉
  2. 重復(fù)操作1逞刷，直到找不到入度為0的頂點

根據(jù)這種思路嘉涌，假設(shè)對下圖進(jìn)行拓?fù)渑判?/p>

首先將度為0的頂點放入列表中

然后將這些頂點從圖中刪除妻熊，最終刪除后的結(jié)果如下

基礎(chǔ)將入度為0的頂點放入列表中

然后將A從圖中刪除，最終刪除后的結(jié)果如下

繼續(xù)將入度為0的頂點放入列表中

將B洛心，D從圖中刪除，最終只剩下頂點F

現(xiàn)在F的入度為0题篷，所以現(xiàn)在又將F放入列表中

最終词身，所有頂點都加入到了列表中，沒有剩下入度為0的頂點番枚，說明拓?fù)渑判蛲瓿煞ㄑ稀Ａ硗馊绻斜碇械脑貍€數(shù)與頂點的總數(shù)相同，也說明拓?fù)渑判蛲瓿伞?/p>

但是葫笼，如果已經(jīng)找不到入度為0的頂點深啤，但是列表中的元素個數(shù)少于頂點總數(shù)，則說明原圖中存在環(huán)路星，無法進(jìn)行拓?fù)渑判颉?/p>

由于卡恩算法的實現(xiàn)溯街，是將度為0的頂點加入列表后，將這些頂點從圖中刪除洋丐，如果按照這種方法進(jìn)行操作呈昔，會破壞原有的數(shù)據(jù)，所以在實現(xiàn)拓?fù)渑判驎r友绝，會結(jié)合卡恩算法進(jìn)行適當(dāng)?shù)恼{(diào)整堤尾。步驟是這樣的

1. 首先創(chuàng)建一個List，用來存放排序后頂點的值
2. 創(chuàng)建一個隊列迁客，用來存放當(dāng)前入度為0的頂點
3. 創(chuàng)建一個表郭宝，備份所有頂點入度
4. 將當(dāng)前入度為0的頂點入隊
5. 將隊頭頂點出隊，遍歷當(dāng)前頂點的outEdges掷漱，然后將遍歷到的頂點粘室，將這些頂點的inEdges減一，如果此時發(fā)現(xiàn)有減為0的頂點卜范，則將該頂點入隊育特，直到將outEdges遍歷完為止。并將出隊頂點的值添加到List中
6. 繼續(xù)將隊頭元素出隊先朦，重復(fù)步驟5
7. 直到將隊列中的元素全部出隊為止缰冤，就完成了拓?fù)渑判颉?/li>

根據(jù)上面的分析，最終轉(zhuǎn)換為代碼的結(jié)果如下

public List<V> toplogicalSort() {
    List<V> list = new ArrayList<>();
    Queue<Vertex<V,E>> queue = new LinkedList<>();
    Map<Vertex<V,E>,Integer> map = new HashMap<>();
    //將度為0的節(jié)點喳魏，都放入隊列中
    vertices.forEach((V v,Vertex<V,E> vertex)->{
        if (vertex.inEdges.size() == 0) {
            queue.offer(vertex);
        } else {
            map.put(vertex,vertex.inEdges.size());
        }
    });
    while (!queue.isEmpty()) {
        Vertex<V,E> vertex = queue.poll();
        list.add(vertex.value);//將頂點的值棉浸，放入返回結(jié)果中
        for (Edge<V,E> edge: vertex.outEdges ) {
            int toIn = map.get(edge.to) - 1;
            if (toIn == 0) {
                queue.offer(edge.to);
            } else {
                map.put(edge.to,toIn);
            }
        }
    }
    return list;
}

demo下載地址

完！