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

信管網(wǎng)考友

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

A、包含回路

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

C、是完全圖

D、是有向樹

信管網(wǎng)考友

這個題怎么選

信管網(wǎng)考友

A

信管網(wǎng)考友

B

信管網(wǎng)考友

A

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

信管網(wǎng)解析:

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

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

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

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

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