[其它課程]數(shù)據(jù)結(jié)構(gòu)第16次課圖a-資料下載頁
2025-01-21 12:57本頁面
【正文】 邊條邊 ）n 如果用 鄰接矩陣 來表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要 從頭掃描 該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為 O(n2)。n 如果用 鄰接表 來表示圖，雖然有 2e 個(gè)表結(jié)點(diǎn)，但只需掃描 e 個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問 n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為 O(n+e)。結(jié)論： 稠密圖 適于在鄰接矩陣上進(jìn)行深度遍歷； 稀疏圖 適于在鄰接表上進(jìn)行深度遍歷。36數(shù)據(jù)結(jié)構(gòu)二、廣度優(yōu)先搜索二、廣度優(yōu)先搜索 ( BFS )基本思想： —— 仿樹的層次遍歷過程。Breadth_First Searchv1v1v2 v3v8v7v6v4 v5BFS 結(jié)果結(jié)果例例 1：：→→ →→→→→→v2 v3→→v4 v5 →→v6 v7→→ v8例例 2：：v3 →BFS 結(jié)果結(jié)果v4 → v5 →起點(diǎn)遍歷步驟起點(diǎn)v2 → v1 → v6 →v9 → v8 → v737數(shù)據(jù)結(jié)構(gòu)V1V2V4 V5V3V7V6V8例 例 V1V2V4V5 V3V7V6V8廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8V1V2V4 V5V3V7V6V8例廣度遍歷： V1? V2 ?V3 ? V4 ?V6 ?V7 ?V8 ?V5練習(xí)：38數(shù)據(jù)結(jié)構(gòu)廣度優(yōu)先搜索（遍歷）步驟：簡單歸納：? 在訪問了起始點(diǎn) v之后，依次訪問 v的鄰接點(diǎn)；? 然后再依次訪問這些頂點(diǎn)中未被訪問過的鄰接點(diǎn)；? 直到所有頂點(diǎn)都被訪問過為止。廣度優(yōu)先搜索是一種 分層的搜索過程 ，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。39數(shù)據(jù)結(jié)構(gòu)討論 1：計(jì)算機(jī)如何實(shí)現(xiàn)BFS？鄰接表—— 除輔助數(shù)組 visited [n ]外，還需再開一輔助隊(duì)列！例：起點(diǎn) 輔助隊(duì)列v2已訪問過了BFS 遍歷結(jié)果遍歷結(jié)果入隊(duì)！初始 f=n1,r=040數(shù)據(jù)結(jié)構(gòu)討論 2： BFS算法如何編程？BFS1(List, n, v) {Visit(v)。 Visited[v]=1。front=n1。rear=0。q[rear]=v。while(rear!=front){ front=(front+1)%n。 v=q[front]。 p=List[v].firstarc。 while(!p){ if(! Visited[adjvex(p)] ) { Visit(adjvex(p))。 Visited[adjvex(p)]=1。 rear=(rear+1)%n。 q[rear]= adjvex(p)} p=nextarc(p)。 } }return。 } —— 層次遍歷應(yīng)當(dāng)用隊(duì)列！//List為鄰接表 ， v為起點(diǎn)， Q[n]為輔助隊(duì)列 //訪問（例如打印）頂點(diǎn) v并修改標(biāo)志 // BFS1//指向單鏈表中下一個(gè)鄰接點(diǎn)//隊(duì)列指針初始化//起始點(diǎn)入隊(duì)//隊(duì)不空時(shí)//訪問過的頂點(diǎn)出隊(duì)//P指向第 1個(gè)鄰接點(diǎn)未到表尾，且鄰接域未訪問過， 則先輸出再改標(biāo)記，最后再入隊(duì)41數(shù)據(jù)結(jié)構(gòu)開始訪問 V0,置 標(biāo)志求 V鄰接點(diǎn) ww存在嗎 V下一鄰接點(diǎn) ?ww訪問過結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭 V出隊(duì) 訪問 w,置 標(biāo)志w入隊(duì)NaaY42數(shù)據(jù)結(jié)構(gòu)v廣度優(yōu)先遍歷算法開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY 43數(shù)據(jù)結(jié)構(gòu)BFS 算法效率分算法效率分析析 :DFS與與 BFS之比較：之比較：? 空間復(fù)雜度相同，都是 O(n)(借用了堆?；蜿?duì)列）；? 時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu) （鄰接矩陣或鄰接表） 有關(guān)，而與搜索路徑無關(guān)。167。 如果使用鄰接表來表示圖，則 BFS循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + … + d n1 = O(e)， 其中的 di 是頂點(diǎn) i 的度 。167。 如果使用鄰接矩陣，則 BFS對于每一個(gè)被訪問到的頂點(diǎn)，都要循環(huán)檢測矩陣中的整整一行（ n 個(gè)元素），總的時(shí)間代價(jià)為 O(n2)。（ 設(shè)圖中有設(shè)圖中有 n 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)， e 條邊條邊 ）44數(shù)據(jù)結(jié)構(gòu)void AJ(adjlist GL,int i,int n){Queue Q。InitQueue(Q)。couti’ ‘。visited[i]=true。QInsert(Q,i)。while(!QueueEmpty(Q)){int k=QDelete(Q)。edgenode *p=GL[k]。while(p!=NULL) { int j=padjvex。 if (!visited[j]){ coutj’ ‘。visited[j]=true。QInsert(Q,j)。}p=pnext。} }}該函數(shù)實(shí)現(xiàn)的是 ( )的 ( )操作，其中采用的存儲(chǔ)結(jié)構(gòu)是 ( ),調(diào)用了 ( )數(shù)據(jù)結(jié)構(gòu) ?45數(shù)據(jù)結(jié)構(gòu)void AK(adjlist GL,int i,int n) { couti’ ’ 。 visited[i]=true。 edgenode *p=GL[i]。 while (p!=NULL) { int j=padjvex。 if( ! visited[j] ) AK(GL,j,n)。 p=pnext。 } }該函數(shù)實(shí)現(xiàn)的是 ( )的 ( )操作，系統(tǒng)內(nèi)部需要調(diào)用 ( )數(shù)據(jù)結(jié)構(gòu) ?46
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1