知識(shí)點(diǎn)13：圖的遍歷PPT課件

1、知識(shí)點(diǎn)知識(shí)點(diǎn)13：圖的遍歷：圖的遍歷1、圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種方式。深度優(yōu)先搜索是一個(gè)遞、圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種方式。深度優(yōu)先搜索是一個(gè)遞歸的過(guò)程，而廣度優(yōu)先搜索是一個(gè)非遞歸過(guò)程。歸的過(guò)程，而廣度優(yōu)先搜索是一個(gè)非遞歸過(guò)程。（1）深度優(yōu)先搜索）深度優(yōu)先搜索遞歸算法遞歸算法非遞歸算法非遞歸算法圖的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣表示時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為圖的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣表示時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n2) 。當(dāng)以。當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)

2、。深度優(yōu)先搜。深度優(yōu)先搜索遍歷圖的空間復(fù)雜度為索遍歷圖的空間復(fù)雜度為O(n)。（2）廣度優(yōu)先搜索：廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷的）廣度優(yōu)先搜索：廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷的相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。2、樹(shù)的先根遍歷是一種深度優(yōu)先搜索策略，樹(shù)的層次遍歷是一種廣度優(yōu)先搜索、樹(shù)的先根遍歷是一種深度優(yōu)先搜索策略，樹(shù)的層次遍歷是一種廣度優(yōu)先搜索策略策略。題題1如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜素即可訪問(wèn)所有頂點(diǎn)，則該圖如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜素即可訪問(wèn)所有頂點(diǎn)，則

3、該圖一定是（一定是（ ）。）。A.完全圖完全圖 B.連通圖連通圖 C.有回路有回路 D.一棵樹(shù)一棵樹(shù)分析：對(duì)于無(wú)向圖來(lái)說(shuō)，若無(wú)向圖是連通圖，則一次遍歷能夠訪問(wèn)到圖中的所有頂點(diǎn)，分析：對(duì)于無(wú)向圖來(lái)說(shuō)，若無(wú)向圖是連通圖，則一次遍歷能夠訪問(wèn)到圖中的所有頂點(diǎn)，但若無(wú)向圖是非連通圖，則只能訪問(wèn)到初始點(diǎn)所在連通分量中的所有頂點(diǎn)，其他連但若無(wú)向圖是非連通圖，則只能訪問(wèn)到初始點(diǎn)所在連通分量中的所有頂點(diǎn)，其他連通分量中的頂點(diǎn)不可能訪問(wèn)到。通分量中的頂點(diǎn)不可能訪問(wèn)到。解答：解答：B。題題2 假設(shè)圖假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)中從頂點(diǎn)u到到v的長(zhǎng)度為的長(zhǎng)

4、度為k的所有簡(jiǎn)單路徑。的所有簡(jiǎn)單路徑。分析：所謂簡(jiǎn)單路徑是指路徑上的頂點(diǎn)不重復(fù)。本題利用回溯的深度優(yōu)先搜索方分析：所謂簡(jiǎn)單路徑是指路徑上的頂點(diǎn)不重復(fù)。本題利用回溯的深度優(yōu)先搜索方法，從頂點(diǎn)法，從頂點(diǎn)u開(kāi)始，進(jìn)行深度優(yōu)先搜索。由于在搜索過(guò)程中，每個(gè)頂點(diǎn)只訪問(wèn)一開(kāi)始，進(jìn)行深度優(yōu)先搜索。由于在搜索過(guò)程中，每個(gè)頂點(diǎn)只訪問(wèn)一次且不重復(fù)訪問(wèn)，所以這條路徑必定是一條簡(jiǎn)單路徑。因此，在搜索過(guò)程中，需次且不重復(fù)訪問(wèn)，所以這條路徑必定是一條簡(jiǎn)單路徑。因此，在搜索過(guò)程中，需要把當(dāng)前的搜索線路記錄下來(lái)。為了記錄當(dāng)前的搜索路徑，可設(shè)立一個(gè)數(shù)組要把當(dāng)前的搜索線路記錄下來(lái)。為了記錄當(dāng)前的搜索路徑，可設(shè)立一個(gè)數(shù)組path保存

5、走過(guò)的路徑，用保存走過(guò)的路徑，用d記錄走過(guò)的路徑長(zhǎng)度。若當(dāng)前掃描到的結(jié)點(diǎn)記錄走過(guò)的路徑長(zhǎng)度。若當(dāng)前掃描到的結(jié)點(diǎn)u等于等于v且路徑且路徑長(zhǎng)度為長(zhǎng)度為k時(shí)，表示找到了一條路徑，則輸出路徑時(shí)，表示找到了一條路徑，則輸出路徑path。void PathAll(ALGraph *G,int u,int v,int k,int path,int d)/d是到當(dāng)前已走過(guò)的路徑長(zhǎng)度，調(diào)用時(shí)初值為是到當(dāng)前已走過(guò)的路徑長(zhǎng)度，調(diào)用時(shí)初值為-1 int m,i; ArcNode *p; visitedu=1; d+; /路徑長(zhǎng)度加路徑長(zhǎng)度加1 pathd=u; /將當(dāng)前頂點(diǎn)添加到路徑中將當(dāng)前頂點(diǎn)添加到路徑中 if (u= =v & d= =k) for (i=0;iadjlistu.firstarc; /p指向頂點(diǎn)指向頂點(diǎn)u的第一條弧的弧頭結(jié)點(diǎn)的第一條弧的弧頭結(jié)點(diǎn) while (p!=NULL) m=p-adjvex; /m為為u的鄰接頂點(diǎn)的鄰接頂點(diǎn) if (visitedm= =0) PathAll(G,m,v,k,path,d); /若該頂點(diǎn)未標(biāo)記訪問(wèn)，則用遞歸訪問(wèn)它若該頂點(diǎn)未標(biāo)記訪問(wèn)，則用遞歸訪問(wèn)它 p-nextar