圖的遍歷

圖的遍歷(Traversing Graph)：從圖的某1頂點(diǎn)動(dòng)身，訪遍圖中的其余頂點(diǎn)，且每一個(gè)頂點(diǎn)僅被訪問(wèn)1次。
圖的遍歷算法是各種圖的操作的基礎(chǔ)。但圖的遍歷存在以下特點(diǎn)：
◆ 復(fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)，而有些頂點(diǎn)卻還沒(méi)有被遍歷到的情況。
◆ 解決辦法：在遍歷進(jìn)程中記下已被訪問(wèn)過(guò)的頂點(diǎn)。設(shè)置1個(gè)輔助向量Visited1…n，其初值為0，1旦訪問(wèn)了頂點(diǎn)vi后，使Visited[i]為1或?yàn)樵L問(wèn)的次序號(hào)。
圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。

深度優(yōu)先搜索(Depth First Search

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)