0.拓?fù)湫颍?/b>在計(jì)算機(jī)科學(xué)領(lǐng)域，有向圖的拓?fù)渑判蚴菍?duì)其頂點(diǎn)的一種線性結(jié)構(gòu)，是的對(duì)于從頂點(diǎn)u到頂點(diǎn)v的每個(gè)有向邊uv寞射，u都排在v之前。
PS：當(dāng)且僅當(dāng)圖中沒有定向環(huán)時(shí)锌钮，即有向無環(huán)圖桥温，才有可能行進(jìn)行拓?fù)渑判颉?/p>
1.在圖論中，由一個(gè)有向無環(huán)圖的頂點(diǎn)組成的序列梁丘，當(dāng)且僅當(dāng)滿足下列條件時(shí)侵浸，才能稱為改該圖的一個(gè)拓?fù)渑判颍?/b>
<1>:序列中包含每個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)只出現(xiàn)一次氛谜。
<2>:若A在序列中排在B的前面掏觉，則在圖中不存在從B到A的路徑。
2.卡恩算法：卡恩于1962年提出了該算法值漫。
簡(jiǎn)單來說就是：
1.假設(shè)L是存放結(jié)果的列表澳腹，先找到那些入度為0的節(jié)點(diǎn)，把這些節(jié)點(diǎn)加入到L中杨何，因?yàn)檫@些節(jié)點(diǎn)沒有任何的父節(jié)點(diǎn)(即入度為0)酱塔。
2.然后把這些節(jié)點(diǎn)相連的邊從圖中去掉，再尋找圖中的入度為0的節(jié)點(diǎn)危虱。
3.對(duì)于那些新找到的入度為0的節(jié)點(diǎn)來說羊娃，他們的父節(jié)點(diǎn)已經(jīng)在L中了，所以也可以放入L
4.重復(fù)上述操作埃跷，知道找不到入度為0的節(jié)點(diǎn)蕊玷。
5.如果此時(shí)L中的元素個(gè)數(shù)和節(jié)點(diǎn)總數(shù)相等，說明排序完成了弥雹；如果L中的元素個(gè)數(shù)和節(jié)點(diǎn)總數(shù)不同垃帅，說明圖中有環(huán)，無法進(jìn)行拓?fù)渑判颉?/p>
3.深度優(yōu)先搜索
1.假設(shè)L是一個(gè)空的存放結(jié)果的列表缅糟。深度優(yōu)先搜索任意順序循環(huán)遍歷圖中的每個(gè)節(jié)點(diǎn)挺智。如果此節(jié)點(diǎn)入度為0，將其加入到L窗宦，并標(biāo)記已訪問過赦颇。
2.如果遇到了之前已經(jīng)遇到的節(jié)點(diǎn)或者葉節(jié)點(diǎn)，直接終止算法赴涵。
2.重復(fù)所有的節(jié)點(diǎn)媒怯。如果L的元素等于節(jié)點(diǎn)元素個(gè)數(shù)，說明拓?fù)渑判蛞淹瓿伤璐埽駝t說明原圖中存在環(huán)扇苞，無法進(jìn)行拓?fù)渑判颉?/p>
