軟件設(shè)計(jì)師試題解析：拓?fù)渑判蚴侵赣邢驁D中的所有頂點(diǎn)排成一個(gè)線性序列的過(guò)程

信管網(wǎng)考友

拓?fù)渑判蚴侵赣邢驁D中的所有頂點(diǎn)排成一個(gè)線性序列的過(guò)程，若在有向圖中從頂點(diǎn)vi到vj有一條路徑，則在該線性序列中，頂點(diǎn)vi必然在頂點(diǎn)vj之前。因此，若不能得到全部頂點(diǎn)的拓?fù)渑判蛐蛄校瑒t說(shuō)明該有向圖一定 （ ） 。

A、包含回路

B、是強(qiáng)連通圖

C、是完全圖

D、是有向樹(shù)

信管網(wǎng)考友

這個(gè)題怎么選

信管網(wǎng)考友

A

信管網(wǎng)考友

B

信管網(wǎng)考友

A

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

信管網(wǎng)解析:

解析:對(duì)有向圖進(jìn)行拓?fù)渑判虻姆椒ㄈ缦?

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

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

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

執(zhí)行結(jié)果會(huì)有兩種情況：一種是所有頂點(diǎn)已輸出，此事整個(gè)拓?fù)渑判蛲瓿?，說(shuō)明網(wǎng)中不存在回路；另一種是尚有未輸出的頂點(diǎn)，剩余的頂點(diǎn)均有前驅(qū)頂點(diǎn)，表明網(wǎng)中存在回路，拓?fù)渑判驘o(wú)法進(jìn)行下去。