基于鄰接表結(jié)構(gòu)的拓?fù)渑判虻娜蛄兴惴ㄑ芯?/h1>
2016-09-06 08:55:59薛春艷
現(xiàn)代計算機 2016年19期
薛春艷
（廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門 361000）
基于鄰接表結(jié)構(gòu)的拓?fù)渑判虻娜蛄兴惴ㄑ芯?/p>
薛春艷
（廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門 361000）
拓?fù)渑判蚴怯邢驘o環(huán)圖的用來描述各活動間的先后關(guān)系的重要應(yīng)用。利用拓?fù)渑判蛩惴艿玫綀D中的各活動的線性序列，同時這個序列滿足各活動在圖中體現(xiàn)的先后關(guān)系，即拓?fù)湫蛄?。常用的求解拓?fù)渑判蚍椒ㄊ乔蟮靡粋€拓?fù)湫蛄屑纯伞榱嗽鰪娝惴ǖ膶嵱脙r值，給出求解有向無環(huán)圖的所有拓?fù)湫蛄械姆椒?，并討論算法的原理及代碼實現(xiàn)，驗證全拓?fù)渑判蛩惴ǖ膶嵱眯院驼_性。
拓?fù)渑判颍蝗蛄?；鄰接?/p>
0 引言
有向無環(huán)圖在實際應(yīng)用中經(jīng)常用來描述工程或者系統(tǒng)的進(jìn)行過程。如工程施工圖、學(xué)生選課關(guān)系圖等。在圖中，用頂點表示活動，用有向邊表示活動間的先后關(guān)系，這種有向圖稱為AOV網(wǎng)(Activity On Vertex Network)。將AOV網(wǎng)中的各個頂點排成一個線性序列，使各頂點在序列中保持其在圖中體現(xiàn)出來的先后關(guān)系，這個過程稱為拓?fù)渑判颉Ｓ纱说玫降木€性序列稱為拓?fù)湫蛄衃1]。
求有向無環(huán)圖的拓?fù)湫蛄械囊饬x在于可以根據(jù)拓?fù)湫蛄袑D中活動進(jìn)行串行地安排，從而提高活動安排的效率。如學(xué)生課程間的安排、生產(chǎn)控制過程的優(yōu)化、工程施工的過程管理等[2]。
有向無環(huán)圖的拓?fù)湫蛄型ǔＧ闆r下是不唯一的，常用的拓?fù)渑判蚍椒ó?dāng)?shù)玫揭粋€拓?fù)湫蛄泻缶徒Y(jié)束了；在很多應(yīng)用中，只求出一個拓?fù)湫蛄惺遣粔虻?，需要得到的該圖的全部可能的拓?fù)湫蛄?，再根?jù)相關(guān)的要求選出最佳的拓?fù)湫蛄小?/p>
1 拓?fù)渑判蛩惴ǖ拇鎯Y(jié)構(gòu)
在計算機中實現(xiàn)時，有向無環(huán)圖采用了鄰接表作為存儲結(jié)構(gòu)。同時在基本的鄰接表的基礎(chǔ)上進(jìn)行了改進(jìn)，為了實現(xiàn)算法的方便，在頂點結(jié)構(gòu)中加了一項，用來存放該頂點入度的值。通過這個入度的值可以進(jìn)行下面兩操作：
（1）判斷當(dāng)前頂點是否是無前驅(qū)的頂點：即判斷其入度是否為0；
（2）輸出頂點后，需要刪除該頂點和所有以它為尾的弧的操作：即將以該頂點為弧尾的另一端的弧頭頂點的入度減1。
同時，需要設(shè)一個棧結(jié)構(gòu)來存放拓?fù)渑判蜻^程中所有入度為零的頂點[3]。改進(jìn)后的有向無環(huán)圖的存儲結(jié)構(gòu)如下：
以圖1為例，圖2是圖1的鄰接表結(jié)構(gòu)示意圖。
圖1 無向圖G
圖2 無向圖G的鄰接表示意圖
2 拓?fù)渑判虻乃惴ㄋ枷?/h2>
拓?fù)渑判虻乃惴ㄋ枷胧牵?/p>
（1）在有向無環(huán)圖中任選一個沒有前驅(qū)的頂點（無前驅(qū)的頂點可能有多個）并且輸出。
（2）刪除該頂點以及所有由該頂點發(fā)出的弧。
重復(fù)上述兩步，直到圖中所有頂點全部輸出為止。
其偽代碼如下：
（1）棧S初始化；
（2）掃描頂點表，將所有無前驅(qū)的頂點入棧；
（3）當(dāng)棧S非空時循環(huán)
棧頂元素vj出棧；輸出vj；
頂點vj的各個鄰接點的入度減1，若間后入度為0，則將該頂點入棧S。
若所有的頂點都已輸出，就表明所輸出的序列即為所求的該有向無環(huán)圖的拓?fù)湫蛄小?/p>
3 全拓?fù)渑判蛩惴ǖ脑砼c實現(xiàn)[3]
全拓?fù)渑判虿捎昧肃徑颖碜鳛閳D的存儲結(jié)構(gòu)，通過深度優(yōu)先搜索獲得序列，利用棧結(jié)構(gòu)存儲無前驅(qū)的頂點，利用隊列結(jié)構(gòu)存儲所有可能的待檢測的序列，利用窮舉法來判斷是否符合拓?fù)渑判虻囊螅罱K求出所有符合要求的解。
（1）統(tǒng)計所有入度為0的頂點，窮舉出由這些頂點開始所能構(gòu)造的所有可能的頂點序列；
（2）判斷當(dāng)前序列是否是合法的拓?fù)渑判颍绻?，則輸出該序列，轉(zhuǎn)（1）。
（3）否則轉(zhuǎn)（2），直到所有可能序列都完成檢測為止。
全拓?fù)渑判蚝瘮?shù)代碼如下：
4 程序運行結(jié)果
根據(jù)圖1收入邊數(shù)：6和9條邊的信息（以“起點編號 重點編號”格式輸入），最終求得圖G的全拓?fù)湫蛄袨?個，具體情況如圖3所示。見圖3：
圖3 圖G的全拓?fù)湫蛄星蠼饨Y(jié)果
5 結(jié)語
本文給出了全拓?fù)湫蛄兴惴ǖ幕舅枷牒途唧w編程實現(xiàn)過程。全拓?fù)渑判蛩惴ㄋ枷牒唵蚊髁?，時間復(fù)雜度和空間復(fù)雜度適當(dāng)。求解全拓?fù)渑判蚰康氖菫榱饲蠼馓厥鈼l件下的最佳的拓?fù)湫蛄小Ｒ虼?，若在獲得備選序列的過程中加上貪心規(guī)則，算法的性能還能得到進(jìn)一步提高。
[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997.
[2]王瓊.拓?fù)渑判蛩惴ǖ耐卣寡芯縖J].計算機工程與應(yīng)用，2006-24.
[3]朱立華，王汝傳.AOV網(wǎng)中全拓?fù)渑判蛩惴ǖ脑O(shè)計及應(yīng)用[J].微機發(fā)展，2004-14.
Topology Sorting;All Sort;Adjacency List
Research on the Algorithm for all Topology Sorting Based on Adjacency List Structure
XUE Chun-yan
（College of Information Science and Technology,Xiamen University Tan Kah Kee College,Xiamen 361000）
Topology sort is an important application of a Directed Acyclic Graph for the relations between activities which in the DAG.Topology sort algorithm can get a linear sequence of each activity in this DAG,this sequence of activities meets all embodied relationship in the DAG, namely topological sequence.Usually,the topological sorting method obtains a topological sequence.In order to enhance the practical value of the algorithm,presents a method to get all the topology sequence of the DAG,and discusses the principle and the code algorithm, verifies the correctness and practicality of the full topological sorting algorithm.
1007-1423（2016）19-0074-03
10.3969/j.issn.1007-1423.2016.19.018
薛春艷（1976-），女，吉林遼源人，碩士研究生，副教授，研究方向為數(shù)字圖像處理、算法設(shè)計與分析、數(shù)據(jù)庫
2016-04-14
2016-07-02
猜你喜歡
排序不等式中學(xué)生數(shù)理化·七年級數(shù)學(xué)人教版(2022年11期)2022-02-14 07:14:12 過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應(yīng)用(下)中等數(shù)學(xué)(2021年9期)2021-11-22 08:06:58 恐怖排序科普童話·學(xué)霸日記(2020年1期)2020-05-08 16:45:11 節(jié)日排序小天使·一年級語數(shù)英綜合(2019年2期)2019-01-10 11:57:30 關(guān)于頂點染色的一個猜想山東科學(xué)(2018年6期)2018-12-20 11:08:58 刻舟求劍兒童繪本(2018年5期)2018-04-12 16:45:32 SiBNC陶瓷纖維前驅(qū)體的結(jié)構(gòu)及流變性能材料科學(xué)與工程學(xué)報(2016年1期)2017-01-15 13:33:52 可溶性前驅(qū)體法制備ZrC粉末的研究進(jìn)展當(dāng)代化工研究(2016年7期)2016-03-20 16:21:54 前驅(qū)體磷酸鐵中磷含量測定的不確定度評定電源技術(shù)(2015年9期)2015-06-05 09:36:06 溶膠-凝膠微波加熱合成PbZr0.52Ti0.48O3前驅(qū)體應(yīng)用化工(2014年11期)2014-08-16 15:59:13
薛春艷
（廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門 361000）
基于鄰接表結(jié)構(gòu)的拓?fù)渑判虻娜蛄兴惴ㄑ芯?/p>
薛春艷
（廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門 361000）
拓?fù)渑判蚴怯邢驘o環(huán)圖的用來描述各活動間的先后關(guān)系的重要應(yīng)用。利用拓?fù)渑判蛩惴艿玫綀D中的各活動的線性序列，同時這個序列滿足各活動在圖中體現(xiàn)的先后關(guān)系，即拓?fù)湫蛄?。常用的求解拓?fù)渑判蚍椒ㄊ乔蟮靡粋€拓?fù)湫蛄屑纯伞榱嗽鰪娝惴ǖ膶嵱脙r值，給出求解有向無環(huán)圖的所有拓?fù)湫蛄械姆椒?，并討論算法的原理及代碼實現(xiàn)，驗證全拓?fù)渑判蛩惴ǖ膶嵱眯院驼_性。
拓?fù)渑判颍蝗蛄?；鄰接?/p>
0 引言
有向無環(huán)圖在實際應(yīng)用中經(jīng)常用來描述工程或者系統(tǒng)的進(jìn)行過程。如工程施工圖、學(xué)生選課關(guān)系圖等。在圖中，用頂點表示活動，用有向邊表示活動間的先后關(guān)系，這種有向圖稱為AOV網(wǎng)(Activity On Vertex Network)。將AOV網(wǎng)中的各個頂點排成一個線性序列，使各頂點在序列中保持其在圖中體現(xiàn)出來的先后關(guān)系，這個過程稱為拓?fù)渑判颉Ｓ纱说玫降木€性序列稱為拓?fù)湫蛄衃1]。
求有向無環(huán)圖的拓?fù)湫蛄械囊饬x在于可以根據(jù)拓?fù)湫蛄袑D中活動進(jìn)行串行地安排，從而提高活動安排的效率。如學(xué)生課程間的安排、生產(chǎn)控制過程的優(yōu)化、工程施工的過程管理等[2]。
有向無環(huán)圖的拓?fù)湫蛄型ǔＧ闆r下是不唯一的，常用的拓?fù)渑判蚍椒ó?dāng)?shù)玫揭粋€拓?fù)湫蛄泻缶徒Y(jié)束了；在很多應(yīng)用中，只求出一個拓?fù)湫蛄惺遣粔虻?，需要得到的該圖的全部可能的拓?fù)湫蛄?，再根?jù)相關(guān)的要求選出最佳的拓?fù)湫蛄小?/p>
1 拓?fù)渑判蛩惴ǖ拇鎯Y(jié)構(gòu)
在計算機中實現(xiàn)時，有向無環(huán)圖采用了鄰接表作為存儲結(jié)構(gòu)。同時在基本的鄰接表的基礎(chǔ)上進(jìn)行了改進(jìn)，為了實現(xiàn)算法的方便，在頂點結(jié)構(gòu)中加了一項，用來存放該頂點入度的值。通過這個入度的值可以進(jìn)行下面兩操作：
（1）判斷當(dāng)前頂點是否是無前驅(qū)的頂點：即判斷其入度是否為0；
（2）輸出頂點后，需要刪除該頂點和所有以它為尾的弧的操作：即將以該頂點為弧尾的另一端的弧頭頂點的入度減1。
同時，需要設(shè)一個棧結(jié)構(gòu)來存放拓?fù)渑判蜻^程中所有入度為零的頂點[3]。改進(jìn)后的有向無環(huán)圖的存儲結(jié)構(gòu)如下：
以圖1為例，圖2是圖1的鄰接表結(jié)構(gòu)示意圖。
圖1 無向圖G
圖2 無向圖G的鄰接表示意圖
2 拓?fù)渑判虻乃惴ㄋ枷?/h2>
拓?fù)渑判虻乃惴ㄋ枷胧牵?/p>
（1）在有向無環(huán)圖中任選一個沒有前驅(qū)的頂點（無前驅(qū)的頂點可能有多個）并且輸出。
（2）刪除該頂點以及所有由該頂點發(fā)出的弧。
重復(fù)上述兩步，直到圖中所有頂點全部輸出為止。
其偽代碼如下：
（1）棧S初始化；
（2）掃描頂點表，將所有無前驅(qū)的頂點入棧；
（3）當(dāng)棧S非空時循環(huán)
棧頂元素vj出棧；輸出vj；
頂點vj的各個鄰接點的入度減1，若間后入度為0，則將該頂點入棧S。
若所有的頂點都已輸出，就表明所輸出的序列即為所求的該有向無環(huán)圖的拓?fù)湫蛄小?/p>
3 全拓?fù)渑判蛩惴ǖ脑砼c實現(xiàn)[3]
全拓?fù)渑判虿捎昧肃徑颖碜鳛閳D的存儲結(jié)構(gòu)，通過深度優(yōu)先搜索獲得序列，利用棧結(jié)構(gòu)存儲無前驅(qū)的頂點，利用隊列結(jié)構(gòu)存儲所有可能的待檢測的序列，利用窮舉法來判斷是否符合拓?fù)渑判虻囊螅罱K求出所有符合要求的解。
（1）統(tǒng)計所有入度為0的頂點，窮舉出由這些頂點開始所能構(gòu)造的所有可能的頂點序列；
（2）判斷當(dāng)前序列是否是合法的拓?fù)渑判颍绻?，則輸出該序列，轉(zhuǎn)（1）。
（3）否則轉(zhuǎn)（2），直到所有可能序列都完成檢測為止。
全拓?fù)渑判蚝瘮?shù)代碼如下：
4 程序運行結(jié)果
根據(jù)圖1收入邊數(shù)：6和9條邊的信息（以“起點編號 重點編號”格式輸入），最終求得圖G的全拓?fù)湫蛄袨?個，具體情況如圖3所示。見圖3：
圖3 圖G的全拓?fù)湫蛄星蠼饨Y(jié)果
5 結(jié)語
本文給出了全拓?fù)湫蛄兴惴ǖ幕舅枷牒途唧w編程實現(xiàn)過程。全拓?fù)渑判蛩惴ㄋ枷牒唵蚊髁?，時間復(fù)雜度和空間復(fù)雜度適當(dāng)。求解全拓?fù)渑判蚰康氖菫榱饲蠼馓厥鈼l件下的最佳的拓?fù)湫蛄小Ｒ虼?，若在獲得備選序列的過程中加上貪心規(guī)則，算法的性能還能得到進(jìn)一步提高。
[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997.
[2]王瓊.拓?fù)渑判蛩惴ǖ耐卣寡芯縖J].計算機工程與應(yīng)用，2006-24.
[3]朱立華，王汝傳.AOV網(wǎng)中全拓?fù)渑判蛩惴ǖ脑O(shè)計及應(yīng)用[J].微機發(fā)展，2004-14.
Topology Sorting;All Sort;Adjacency List
Research on the Algorithm for all Topology Sorting Based on Adjacency List Structure
XUE Chun-yan
（College of Information Science and Technology,Xiamen University Tan Kah Kee College,Xiamen 361000）
Topology sort is an important application of a Directed Acyclic Graph for the relations between activities which in the DAG.Topology sort algorithm can get a linear sequence of each activity in this DAG,this sequence of activities meets all embodied relationship in the DAG, namely topological sequence.Usually,the topological sorting method obtains a topological sequence.In order to enhance the practical value of the algorithm,presents a method to get all the topology sequence of the DAG,and discusses the principle and the code algorithm, verifies the correctness and practicality of the full topological sorting algorithm.
1007-1423（2016）19-0074-03
10.3969/j.issn.1007-1423.2016.19.018
薛春艷（1976-），女，吉林遼源人，碩士研究生，副教授，研究方向為數(shù)字圖像處理、算法設(shè)計與分析、數(shù)據(jù)庫
2016-04-14
2016-07-02
猜你喜歡
中學(xué)生數(shù)理化·七年級數(shù)學(xué)人教版(2022年11期)2022-02-14 07:14:12
中等數(shù)學(xué)(2021年9期)2021-11-22 08:06:58
科普童話·學(xué)霸日記(2020年1期)2020-05-08 16:45:11
小天使·一年級語數(shù)英綜合(2019年2期)2019-01-10 11:57:30
山東科學(xué)(2018年6期)2018-12-20 11:08:58
兒童繪本(2018年5期)2018-04-12 16:45:32
材料科學(xué)與工程學(xué)報(2016年1期)2017-01-15 13:33:52
當(dāng)代化工研究(2016年7期)2016-03-20 16:21:54
電源技術(shù)(2015年9期)2015-06-05 09:36:06
應(yīng)用化工(2014年11期)2014-08-16 15:59:13
