第6章圖(編輯修改稿)
2024-11-29 15:08 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 一個(gè)矩陣，使得 ? ? 關(guān)聯(lián)）和頂點(diǎn)（邊（其它情況） ii veij 10?? 圖的遍歷 ? 深度優(yōu)先搜索遍歷 ? 從圖中某個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中所有頂點(diǎn)，且使得每一頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程稱之為圖的遍歷 ? 假定給定圖 G的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)，在 G中任選一頂點(diǎn) v為初始出發(fā)點(diǎn)，則深度優(yōu)先搜索可定義如下： ? 從指定的起點(diǎn) v出發(fā) (先訪問(wèn) v，并將其標(biāo)記為已訪問(wèn)過(guò) )，訪問(wèn)它的任意相鄰接的頂點(diǎn) w1，再訪問(wèn) w1的任一個(gè)未訪問(wèn)的相鄰接頂點(diǎn) w2，如此下去，直到某頂點(diǎn)已無(wú)被訪問(wèn)過(guò)的鄰接頂點(diǎn)或者它的所有鄰接頂點(diǎn)都已經(jīng)被訪問(wèn)過(guò)了，就回溯到它的前驅(qū)。如果這個(gè)訪問(wèn)和回溯過(guò)程返回到遍歷開(kāi)始的頂點(diǎn)，就結(jié)束遍歷過(guò)程。如果圖中仍存在一些未訪問(wèn)過(guò)的結(jié)點(diǎn)，就另選一個(gè)未訪問(wèn)過(guò)的結(jié)點(diǎn)重新開(kāi)始深度優(yōu)先搜索遍歷。 圖的遍歷 ? 深度優(yōu)先搜索遍歷算法表示如下： ? DFS(v) ? num(v)=i++。 ? for 所有與 v鄰接的頂點(diǎn) u ? if num（ u） 是 0 ? 將 edge（ uv） 連接到 edges中； ? DFS（ u） ； ? ? depthFirstSearch() ? for 所有向量 v ? num(v)=0。 ? edges=null。 ? i=1。 ? while 有一個(gè)向量 v使得 num(v)是 0 ? DFS（ v） ； ? 輸出 edges。 圖的遍歷 ? 廣度優(yōu)先搜索遍歷 ? 設(shè)圖 G的初態(tài)是所有頂點(diǎn)均未訪問(wèn)過(guò)，在 G中任選一頂點(diǎn) v為初始出發(fā)點(diǎn)，則廣度優(yōu)先搜索遍歷的基本思想是：從指定的起點(diǎn) v出發(fā)，訪問(wèn)與它相鄰的所有頂點(diǎn) w1， w2， …… ；然后再依次訪問(wèn) w1，w2， …… 鄰接的尚未被訪問(wèn)的所有頂點(diǎn)，再?gòu)倪@些頂點(diǎn)出發(fā)訪問(wèn)與它們相鄰接的尚未被訪問(wèn)的頂點(diǎn)，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1