在研究拓?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é)合下圖來理解一些基本概念
- 前驅(qū)活動:有向邊起點的活動稱為終點的前驅(qū)活動奠支;例如B稱為C的前驅(qū)活動
- 只有當(dāng)一個活動的前驅(qū)全部完成后馋辈,這個活動才能進(jìn)行;例如E只有當(dāng)全部前驅(qū)B倍谜,C迈螟,D完成以后,才能進(jìn)行
- 后繼活動:有向邊終點的活動稱為起點的后繼活動尔崔;例如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é)果的列表
- 把所有入度為0的頂點放入L中,然后把這些頂點從圖中去掉
- 重復(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ù)渑判蛲瓿煞ㄑ稀A硗馊绻斜碇械脑貍€數(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)整堤尾。步驟是這樣的
- 首先創(chuàng)建一個List,用來存放排序后頂點的值
- 創(chuàng)建一個隊列迁客,用來存放當(dāng)前入度為0的頂點
- 創(chuàng)建一個表郭宝,備份所有頂點入度
- 將當(dāng)前入度為0的頂點入隊
- 將隊頭頂點出隊,遍歷當(dāng)前頂點的outEdges掷漱,然后將遍歷到的頂點粘室,將這些頂點的inEdges減一,如果此時發(fā)現(xiàn)有減為0的頂點卜范,則將該頂點入隊育特,直到將outEdges遍歷完為止。并將出隊頂點的值添加到List中
- 繼續(xù)將隊頭元素出隊先朦,重復(fù)步驟5
- 直到將隊列中的元素全部出隊為止缰冤,就完成了拓?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;
}
完!