為什么拓?fù)渑判虿粚儆趦?nèi)部排序法？拓?fù)渑判蚴菍?duì)有向圖的頂點(diǎn)進(jìn)行排序。它關(guān)心的是圖中每個(gè)頂點(diǎn)之間的連接關(guān)系，也稱為拓?fù)潢P(guān)系，因?yàn)樗魂P(guān)心每個(gè)頂點(diǎn)的位置和距離。在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為多

為什么拓?fù)渑判虿粚儆趦?nèi)部排序法？

拓?fù)渑判蚴菍?duì)有向圖的頂點(diǎn)進(jìn)行排序。它關(guān)心的是圖中每個(gè)頂點(diǎn)之間的連接關(guān)系，也稱為拓?fù)潢P(guān)系，因?yàn)樗魂P(guān)心每個(gè)頂點(diǎn)的位置和距離。

在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為多少？

在圖中設(shè)n個(gè)頂點(diǎn)和e個(gè)弧，則鄰接表拓?fù)渑判虻臅r(shí)間復(fù)雜度為O（n，e）]~。在數(shù)據(jù)結(jié)構(gòu)中，拓?fù)湫蚴怯脕?lái)判斷有向圖中是否存在循環(huán)的。頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)序列的有向圖稱為頂點(diǎn)活動(dòng)網(wǎng)絡(luò)（AOV）。AOV網(wǎng)絡(luò)應(yīng)該是一個(gè)有向無(wú)環(huán)圖，也就是說(shuō)，不應(yīng)該有循環(huán)，因?yàn)槿绻醒h(huán)，循環(huán)上的所有活動(dòng)都不能執(zhí)行。在AOV網(wǎng)絡(luò)中，如果沒(méi)有環(huán)，所有的活動(dòng)都可以被安排成一個(gè)線性序列，這樣每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都在活動(dòng)的前面。在數(shù)據(jù)結(jié)構(gòu)中，這種序列稱為拓?fù)湫蛄?，而由AOV網(wǎng)絡(luò)構(gòu)造拓?fù)湫蛄械倪^(guò)程稱為拓?fù)湫颉？傊绻邢驁D中存在拓?fù)湫?，則有向圖中不存在環(huán)。擴(kuò)展數(shù)據(jù)：有向圖拓?fù)渑判虻乃惴ㄋ枷耄篈OV網(wǎng)構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄖ饕谝粋€(gè)循環(huán)中執(zhí)行以下兩個(gè)步驟，直到?jīng)]有度為0的頂點(diǎn)。

1. 選擇一個(gè)度數(shù)為0的頂點(diǎn)并輸出它；

2。從網(wǎng)絡(luò)中刪除此頂點(diǎn)和所有輸出邊。在循環(huán)結(jié)束時(shí)，如果輸出頂點(diǎn)數(shù)小于網(wǎng)絡(luò)中的頂點(diǎn)數(shù)，則輸出“循環(huán)”信息，否則輸出頂點(diǎn)序列為拓?fù)湫蛄小?/p>

你用什么方法判斷它的頂點(diǎn)？

如果是鄰接表存儲(chǔ)，拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度應(yīng)該是o（n，e），n是頂點(diǎn)的個(gè)數(shù)，e是弧的個(gè)數(shù)

我認(rèn)為這是錯(cuò)誤的。拓?fù)渑判虺Ｓ糜谂袛嘤邢驁D是否有環(huán)，因此作為一種判斷方法，無(wú)論有無(wú)環(huán)都可以使用