15-拓?fù)渑判颍═opological Sort)

在研究拓?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ù)渑判蛲瓿煞ㄑ稀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)整堤尾。步驟是這樣的

  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下載地址

完!

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末刺彩,一起剝皮案震驚了整個濱河市迷郑,隨后出現(xiàn)的幾起案子枝恋,更是在濱河造成了極大的恐慌,老刑警劉巖嗡害,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件焚碌,死亡現(xiàn)場離奇詭異,居然都是意外死亡霸妹,警方通過查閱死者的電腦和手機十电,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來叹螟,“玉大人鹃骂,你說我怎么就攤上這事“照溃” “怎么了畏线?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長良价。 經(jīng)常有香客問我寝殴,道長,這世上最難降的妖魔是什么明垢? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任杯矩,我火速辦了婚禮,結(jié)果婚禮上袖外,老公的妹妹穿的比我還像新娘史隆。我一直安慰自己,他們只是感情好曼验,可當(dāng)我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布泌射。 她就那樣靜靜地躺著,像睡著了一般鬓照。 火紅的嫁衣襯著肌膚如雪熔酷。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天豺裆,我揣著相機與錄音拒秘,去河邊找鬼。 笑死臭猜,一個胖子當(dāng)著我的面吹牛躺酒,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播蔑歌,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼羹应,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了次屠?” 一聲冷哼從身側(cè)響起园匹,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤雳刺,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后裸违,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體掖桦,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年供汛,在試婚紗的時候發(fā)現(xiàn)自己被綠了枪汪。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡紊馏,死狀恐怖料饥,靈堂內(nèi)的尸體忽然破棺而出蒲犬,到底是詐尸還是另有隱情朱监,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布原叮,位于F島的核電站赫编,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏奋隶。R本人自食惡果不足惜擂送,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望唯欣。 院中可真熱鬧嘹吨,春花似錦、人聲如沸境氢。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽萍聊。三九已至问芬,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間寿桨,已是汗流浹背此衅。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留亭螟,地道東北人挡鞍。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像预烙,于是被迫代替她去往敵國和親匕累。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內(nèi)容