知識點13：圖的遍歷PPT課件

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

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

3、該圖一定是（一定是（ ）。）。A.完全圖完全圖 B.連通圖連通圖 C.有回路有回路 D.一棵樹一棵樹分析：對于無向圖來說，若無向圖是連通圖，則一次遍歷能夠訪問到圖中的所有頂點，分析：對于無向圖來說，若無向圖是連通圖，則一次遍歷能夠訪問到圖中的所有頂點，但若無向圖是非連通圖，則只能訪問到初始點所在連通分量中的所有頂點，其他連但若無向圖是非連通圖，則只能訪問到初始點所在連通分量中的所有頂點，其他連通分量中的頂點不可能訪問到。通分量中的頂點不可能訪問到。解答：解答：B。題題2 假設圖假設圖G采用鄰接表存儲，設計一個算法，輸出圖采用鄰接表存儲，設計一個算法，輸出圖G中從頂點中從頂點u到到v的長度為的長

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

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