基于鄰接表結(jié)構(gòu)的拓?fù)渑判虻娜蛄兴惴ㄑ芯?/h1>
2016-09-06 08:55:59薛春艷
現(xiàn)代計(jì)算機(jī) 2016年19期
薛春艷
（廈門(mén)大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門(mén) 361000）
基于鄰接表結(jié)構(gòu)的拓?fù)渑判虻娜蛄兴惴ㄑ芯?/p>
薛春艷
（廈門(mén)大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門(mén) 361000）
拓?fù)渑判蚴怯邢驘o(wú)環(huán)圖的用來(lái)描述各活動(dòng)間的先后關(guān)系的重要應(yīng)用。利用拓?fù)渑判蛩惴艿玫綀D中的各活動(dòng)的線(xiàn)性序列，同時(shí)這個(gè)序列滿(mǎn)足各活動(dòng)在圖中體現(xiàn)的先后關(guān)系，即拓?fù)湫蛄?。常用的求解拓?fù)渑判蚍椒ㄊ乔蟮靡粋€(gè)拓?fù)湫蛄屑纯?。為了增?qiáng)算法的實(shí)用價(jià)值，給出求解有向無(wú)環(huán)圖的所有拓?fù)湫蛄械姆椒?，并討論算法的原理及代碼實(shí)現(xiàn)，驗(yàn)證全拓?fù)渑判蛩惴ǖ膶?shí)用性和正確性。
拓?fù)渑判?；全序列；鄰接?/p>
0 引言
有向無(wú)環(huán)圖在實(shí)際應(yīng)用中經(jīng)常用來(lái)描述工程或者系統(tǒng)的進(jìn)行過(guò)程。如工程施工圖、學(xué)生選課關(guān)系圖等。在圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)間的先后關(guān)系，這種有向圖稱(chēng)為AOV網(wǎng)(Activity On Vertex Network)。將AOV網(wǎng)中的各個(gè)頂點(diǎn)排成一個(gè)線(xiàn)性序列，使各頂點(diǎn)在序列中保持其在圖中體現(xiàn)出來(lái)的先后關(guān)系，這個(gè)過(guò)程稱(chēng)為拓?fù)渑判?。由此得到的線(xiàn)性序列稱(chēng)為拓?fù)湫蛄衃1]。
求有向無(wú)環(huán)圖的拓?fù)湫蛄械囊饬x在于可以根據(jù)拓?fù)湫蛄袑?duì)圖中活動(dòng)進(jìn)行串行地安排，從而提高活動(dòng)安排的效率。如學(xué)生課程間的安排、生產(chǎn)控制過(guò)程的優(yōu)化、工程施工的過(guò)程管理等[2]。
有向無(wú)環(huán)圖的拓?fù)湫蛄型ǔＧ闆r下是不唯一的，常用的拓?fù)渑判蚍椒ó?dāng)?shù)玫揭粋€(gè)拓?fù)湫蛄泻缶徒Y(jié)束了；在很多應(yīng)用中，只求出一個(gè)拓?fù)湫蛄惺遣粔虻?，需要得到的該圖的全部可能的拓?fù)湫蛄?，再根?jù)相關(guān)的要求選出最佳的拓?fù)湫蛄小?/p>
1 拓?fù)渑判蛩惴ǖ拇鎯?chǔ)結(jié)構(gòu)
在計(jì)算機(jī)中實(shí)現(xiàn)時(shí)，有向無(wú)環(huán)圖采用了鄰接表作為存儲(chǔ)結(jié)構(gòu)。同時(shí)在基本的鄰接表的基礎(chǔ)上進(jìn)行了改進(jìn)，為了實(shí)現(xiàn)算法的方便，在頂點(diǎn)結(jié)構(gòu)中加了一項(xiàng)，用來(lái)存放該頂點(diǎn)入度的值。通過(guò)這個(gè)入度的值可以進(jìn)行下面兩操作：
（1）判斷當(dāng)前頂點(diǎn)是否是無(wú)前驅(qū)的頂點(diǎn)：即判斷其入度是否為0；
（2）輸出頂點(diǎn)后，需要?jiǎng)h除該頂點(diǎn)和所有以它為尾的弧的操作：即將以該頂點(diǎn)為弧尾的另一端的弧頭頂點(diǎn)的入度減1。
同時(shí)，需要設(shè)一個(gè)棧結(jié)構(gòu)來(lái)存放拓?fù)渑判蜻^(guò)程中所有入度為零的頂點(diǎn)[3]。改進(jìn)后的有向無(wú)環(huán)圖的存儲(chǔ)結(jié)構(gòu)如下：
以圖1為例，圖2是圖1的鄰接表結(jié)構(gòu)示意圖。
圖1 無(wú)向圖G
圖2 無(wú)向圖G的鄰接表示意圖
2 拓?fù)渑判虻乃惴ㄋ枷?/h2>
拓?fù)渑判虻乃惴ㄋ枷胧牵?/p>
（1）在有向無(wú)環(huán)圖中任選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)（無(wú)前驅(qū)的頂點(diǎn)可能有多個(gè)）并且輸出。
（2）刪除該頂點(diǎn)以及所有由該頂點(diǎn)發(fā)出的弧。
重復(fù)上述兩步，直到圖中所有頂點(diǎn)全部輸出為止。
其偽代碼如下：
（1）棧S初始化；
（2）掃描頂點(diǎn)表，將所有無(wú)前驅(qū)的頂點(diǎn)入棧；
（3）當(dāng)棧S非空時(shí)循環(huán)
棧頂元素vj出棧；輸出vj；
頂點(diǎn)vj的各個(gè)鄰接點(diǎn)的入度減1，若間后入度為0，則將該頂點(diǎn)入棧S。
若所有的頂點(diǎn)都已輸出，就表明所輸出的序列即為所求的該有向無(wú)環(huán)圖的拓?fù)湫蛄小?/p>
3 全拓?fù)渑判蛩惴ǖ脑砼c實(shí)現(xiàn)[3]
全拓?fù)渑判虿捎昧肃徑颖碜鳛閳D的存儲(chǔ)結(jié)構(gòu)，通過(guò)深度優(yōu)先搜索獲得序列，利用棧結(jié)構(gòu)存儲(chǔ)無(wú)前驅(qū)的頂點(diǎn)，利用隊(duì)列結(jié)構(gòu)存儲(chǔ)所有可能的待檢測(cè)的序列，利用窮舉法來(lái)判斷是否符合拓?fù)渑判虻囊?，最終求出所有符合要求的解。
（1）統(tǒng)計(jì)所有入度為0的頂點(diǎn)，窮舉出由這些頂點(diǎn)開(kāi)始所能構(gòu)造的所有可能的頂點(diǎn)序列；
（2）判斷當(dāng)前序列是否是合法的拓?fù)渑判?，如果是，則輸出該序列，轉(zhuǎn)（1）。
（3）否則轉(zhuǎn)（2），直到所有可能序列都完成檢測(cè)為止。
全拓?fù)渑判蚝瘮?shù)代碼如下：
4 程序運(yùn)行結(jié)果
根據(jù)圖1收入邊數(shù)：6和9條邊的信息（以“起點(diǎn)編號(hào) 重點(diǎn)編號(hào)”格式輸入），最終求得圖G的全拓?fù)湫蛄袨?個(gè)，具體情況如圖3所示。見(jiàn)圖3：
圖3 圖G的全拓?fù)湫蛄星蠼饨Y(jié)果
5 結(jié)語(yǔ)
本文給出了全拓?fù)湫蛄兴惴ǖ幕舅枷牒途唧w編程實(shí)現(xiàn)過(guò)程。全拓?fù)渑判蛩惴ㄋ枷牒?jiǎn)單明了，時(shí)間復(fù)雜度和空間復(fù)雜度適當(dāng)。求解全拓?fù)渑判蚰康氖菫榱饲蠼馓厥鈼l件下的最佳的拓?fù)湫蛄?。因此，若在獲得備選序列的過(guò)程中加上貪心規(guī)則，算法的性能還能得到進(jìn)一步提高。
[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.
[2]王瓊.拓?fù)渑判蛩惴ǖ耐卣寡芯縖J].計(jì)算機(jī)工程與應(yīng)用，2006-24.
[3]朱立華，王汝傳.AOV網(wǎng)中全拓?fù)渑判蛩惴ǖ脑O(shè)計(jì)及應(yīng)用[J].微機(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-），女，吉林遼源人，碩士研究生，副教授，研究方向?yàn)閿?shù)字圖像處理、算法設(shè)計(jì)與分析、數(shù)據(jù)庫(kù)
2016-04-14
2016-07-02
猜你喜歡
排序不等式中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2022年11期)2022-02-14 07:14:12 過(guò)非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)中等數(shù)學(xué)(2021年9期)2021-11-22 08:06:58 恐怖排序科普童話(huà)·學(xué)霸日記(2020年1期)2020-05-08 16:45:11 節(jié)日排序小天使·一年級(jí)語(yǔ)數(shù)英綜合(2019年2期)2019-01-10 11:57:30 關(guān)于頂點(diǎn)染色的一個(gè)猜想山東科學(xué)(2018年6期)2018-12-20 11:08:58 刻舟求劍兒童繪本(2018年5期)2018-04-12 16:45:32 SiBNC陶瓷纖維前驅(qū)體的結(jié)構(gòu)及流變性能材料科學(xué)與工程學(xué)報(bào)(2016年1期)2017-01-15 13:33:52 可溶性前驅(qū)體法制備ZrC粉末的研究進(jìn)展當(dāng)代化工研究(2016年7期)2016-03-20 16:21:54 前驅(qū)體磷酸鐵中磷含量測(cè)定的不確定度評(píng)定電源技術(shù)(2015年9期)2015-06-05 09:36:06 溶膠-凝膠微波加熱合成PbZr0.52Ti0.48O3前驅(qū)體應(yīng)用化工(2014年11期)2014-08-16 15:59:13
- 現(xiàn)代計(jì)算機(jī)的其它文章
- 高校計(jì)算機(jī)實(shí)驗(yàn)室建設(shè)與管理研究
- 美國(guó)大學(xué)通識(shí)教育對(duì)音樂(lè)學(xué)院計(jì)算機(jī)教學(xué)的啟示
- 基于Android的試題練習(xí)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
- 一種綜合電子信息系統(tǒng)仿真集成設(shè)計(jì)方法研究
- 基于校園無(wú)線(xiàn)局域網(wǎng)絡(luò)的智能視頻監(jiān)控系統(tǒng)
- 基于云端的智能車(chē)位分享系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
薛春艷
（廈門(mén)大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門(mén) 361000）
基于鄰接表結(jié)構(gòu)的拓?fù)渑判虻娜蛄兴惴ㄑ芯?/p>
薛春艷
（廈門(mén)大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，廈門(mén) 361000）
拓?fù)渑判蚴怯邢驘o(wú)環(huán)圖的用來(lái)描述各活動(dòng)間的先后關(guān)系的重要應(yīng)用。利用拓?fù)渑判蛩惴艿玫綀D中的各活動(dòng)的線(xiàn)性序列，同時(shí)這個(gè)序列滿(mǎn)足各活動(dòng)在圖中體現(xiàn)的先后關(guān)系，即拓?fù)湫蛄?。常用的求解拓?fù)渑判蚍椒ㄊ乔蟮靡粋€(gè)拓?fù)湫蛄屑纯?。為了增?qiáng)算法的實(shí)用價(jià)值，給出求解有向無(wú)環(huán)圖的所有拓?fù)湫蛄械姆椒?，并討論算法的原理及代碼實(shí)現(xiàn)，驗(yàn)證全拓?fù)渑判蛩惴ǖ膶?shí)用性和正確性。
拓?fù)渑判?；全序列；鄰接?/p>
0 引言
有向無(wú)環(huán)圖在實(shí)際應(yīng)用中經(jīng)常用來(lái)描述工程或者系統(tǒng)的進(jìn)行過(guò)程。如工程施工圖、學(xué)生選課關(guān)系圖等。在圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)間的先后關(guān)系，這種有向圖稱(chēng)為AOV網(wǎng)(Activity On Vertex Network)。將AOV網(wǎng)中的各個(gè)頂點(diǎn)排成一個(gè)線(xiàn)性序列，使各頂點(diǎn)在序列中保持其在圖中體現(xiàn)出來(lái)的先后關(guān)系，這個(gè)過(guò)程稱(chēng)為拓?fù)渑判?。由此得到的線(xiàn)性序列稱(chēng)為拓?fù)湫蛄衃1]。
求有向無(wú)環(huán)圖的拓?fù)湫蛄械囊饬x在于可以根據(jù)拓?fù)湫蛄袑?duì)圖中活動(dòng)進(jìn)行串行地安排，從而提高活動(dòng)安排的效率。如學(xué)生課程間的安排、生產(chǎn)控制過(guò)程的優(yōu)化、工程施工的過(guò)程管理等[2]。
有向無(wú)環(huán)圖的拓?fù)湫蛄型ǔＧ闆r下是不唯一的，常用的拓?fù)渑判蚍椒ó?dāng)?shù)玫揭粋€(gè)拓?fù)湫蛄泻缶徒Y(jié)束了；在很多應(yīng)用中，只求出一個(gè)拓?fù)湫蛄惺遣粔虻?，需要得到的該圖的全部可能的拓?fù)湫蛄?，再根?jù)相關(guān)的要求選出最佳的拓?fù)湫蛄小?/p>
1 拓?fù)渑判蛩惴ǖ拇鎯?chǔ)結(jié)構(gòu)
在計(jì)算機(jī)中實(shí)現(xiàn)時(shí)，有向無(wú)環(huán)圖采用了鄰接表作為存儲(chǔ)結(jié)構(gòu)。同時(shí)在基本的鄰接表的基礎(chǔ)上進(jìn)行了改進(jìn)，為了實(shí)現(xiàn)算法的方便，在頂點(diǎn)結(jié)構(gòu)中加了一項(xiàng)，用來(lái)存放該頂點(diǎn)入度的值。通過(guò)這個(gè)入度的值可以進(jìn)行下面兩操作：
（1）判斷當(dāng)前頂點(diǎn)是否是無(wú)前驅(qū)的頂點(diǎn)：即判斷其入度是否為0；
（2）輸出頂點(diǎn)后，需要?jiǎng)h除該頂點(diǎn)和所有以它為尾的弧的操作：即將以該頂點(diǎn)為弧尾的另一端的弧頭頂點(diǎn)的入度減1。
同時(shí)，需要設(shè)一個(gè)棧結(jié)構(gòu)來(lái)存放拓?fù)渑判蜻^(guò)程中所有入度為零的頂點(diǎn)[3]。改進(jìn)后的有向無(wú)環(huán)圖的存儲(chǔ)結(jié)構(gòu)如下：
以圖1為例，圖2是圖1的鄰接表結(jié)構(gòu)示意圖。
圖1 無(wú)向圖G
圖2 無(wú)向圖G的鄰接表示意圖
2 拓?fù)渑判虻乃惴ㄋ枷?/h2>
拓?fù)渑判虻乃惴ㄋ枷胧牵?/p>
（1）在有向無(wú)環(huán)圖中任選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)（無(wú)前驅(qū)的頂點(diǎn)可能有多個(gè)）并且輸出。
（2）刪除該頂點(diǎn)以及所有由該頂點(diǎn)發(fā)出的弧。
重復(fù)上述兩步，直到圖中所有頂點(diǎn)全部輸出為止。
其偽代碼如下：
（1）棧S初始化；
（2）掃描頂點(diǎn)表，將所有無(wú)前驅(qū)的頂點(diǎn)入棧；
（3）當(dāng)棧S非空時(shí)循環(huán)
棧頂元素vj出棧；輸出vj；
頂點(diǎn)vj的各個(gè)鄰接點(diǎn)的入度減1，若間后入度為0，則將該頂點(diǎn)入棧S。
若所有的頂點(diǎn)都已輸出，就表明所輸出的序列即為所求的該有向無(wú)環(huán)圖的拓?fù)湫蛄小?/p>
3 全拓?fù)渑判蛩惴ǖ脑砼c實(shí)現(xiàn)[3]
全拓?fù)渑判虿捎昧肃徑颖碜鳛閳D的存儲(chǔ)結(jié)構(gòu)，通過(guò)深度優(yōu)先搜索獲得序列，利用棧結(jié)構(gòu)存儲(chǔ)無(wú)前驅(qū)的頂點(diǎn)，利用隊(duì)列結(jié)構(gòu)存儲(chǔ)所有可能的待檢測(cè)的序列，利用窮舉法來(lái)判斷是否符合拓?fù)渑判虻囊?，最終求出所有符合要求的解。
（1）統(tǒng)計(jì)所有入度為0的頂點(diǎn)，窮舉出由這些頂點(diǎn)開(kāi)始所能構(gòu)造的所有可能的頂點(diǎn)序列；
（2）判斷當(dāng)前序列是否是合法的拓?fù)渑判?，如果是，則輸出該序列，轉(zhuǎn)（1）。
（3）否則轉(zhuǎn)（2），直到所有可能序列都完成檢測(cè)為止。
全拓?fù)渑判蚝瘮?shù)代碼如下：
4 程序運(yùn)行結(jié)果
根據(jù)圖1收入邊數(shù)：6和9條邊的信息（以“起點(diǎn)編號(hào) 重點(diǎn)編號(hào)”格式輸入），最終求得圖G的全拓?fù)湫蛄袨?個(gè)，具體情況如圖3所示。見(jiàn)圖3：
圖3 圖G的全拓?fù)湫蛄星蠼饨Y(jié)果
5 結(jié)語(yǔ)
本文給出了全拓?fù)湫蛄兴惴ǖ幕舅枷牒途唧w編程實(shí)現(xiàn)過(guò)程。全拓?fù)渑判蛩惴ㄋ枷牒?jiǎn)單明了，時(shí)間復(fù)雜度和空間復(fù)雜度適當(dāng)。求解全拓?fù)渑判蚰康氖菫榱饲蠼馓厥鈼l件下的最佳的拓?fù)湫蛄?。因此，若在獲得備選序列的過(guò)程中加上貪心規(guī)則，算法的性能還能得到進(jìn)一步提高。
[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.
[2]王瓊.拓?fù)渑判蛩惴ǖ耐卣寡芯縖J].計(jì)算機(jī)工程與應(yīng)用，2006-24.
[3]朱立華，王汝傳.AOV網(wǎng)中全拓?fù)渑判蛩惴ǖ脑O(shè)計(jì)及應(yīng)用[J].微機(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-），女，吉林遼源人，碩士研究生，副教授，研究方向?yàn)閿?shù)字圖像處理、算法設(shè)計(jì)與分析、數(shù)據(jù)庫(kù)
2016-04-14
2016-07-02
猜你喜歡
中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2022年11期)2022-02-14 07:14:12
中等數(shù)學(xué)(2021年9期)2021-11-22 08:06:58
科普童話(huà)·學(xué)霸日記(2020年1期)2020-05-08 16:45:11
小天使·一年級(jí)語(yǔ)數(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é)報(bào)(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
- 現(xiàn)代計(jì)算機(jī)的其它文章
- 高校計(jì)算機(jī)實(shí)驗(yàn)室建設(shè)與管理研究
- 美國(guó)大學(xué)通識(shí)教育對(duì)音樂(lè)學(xué)院計(jì)算機(jī)教學(xué)的啟示
- 基于Android的試題練習(xí)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
- 一種綜合電子信息系統(tǒng)仿真集成設(shè)計(jì)方法研究
- 基于校園無(wú)線(xiàn)局域網(wǎng)絡(luò)的智能視頻監(jiān)控系統(tǒng)
- 基于云端的智能車(chē)位分享系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)