軟件設計師試題解析：拓撲排序是指有向圖中的所有頂點排成一個線性序列的過程

信管網(wǎng)考友

拓撲排序是指有向圖中的所有頂點排成一個線性序列的過程，若在有向圖中從頂點vi到vj有一條路徑，則在該線性序列中，頂點vi必然在頂點vj之前。因此，若不能得到全部頂點的拓撲排序序列，則說明該有向圖一定 （ ） 。

A、包含回路

B、是強連通圖

C、是完全圖

D、是有向樹

信管網(wǎng)考友

這個題怎么選

信管網(wǎng)考友

A

信管網(wǎng)考友

B

信管網(wǎng)考友

A

信管網(wǎng)參考答案: A(僅供參考,歡迎評論交流)

信管網(wǎng)解析:

解析:對有向圖進行拓撲排序的方法如下:

(1 )在AOV網(wǎng)中選擇一個入度為0 (沒有前驅(qū))的頂點且輸出它。

(2)在網(wǎng)中刪除該頂點及其與該頂點有關(guān)的所有邊。

(3)重復以上步驟,直至網(wǎng)中不存在入度為0的頂點為止。

執(zhí)行結(jié)果會有兩種情況：一種是所有頂點已輸出，此事整個拓撲排序完成，說明網(wǎng)中不存在回路；另一種是尚有未輸出的頂點，剩余的頂點均有前驅(qū)頂點，表明網(wǎng)中存在回路，拓撲排序無法進行下去。