圖的定義和術(shù)語(yǔ)及存儲(chǔ)結(jié)構(gòu)-文庫(kù)吧
2025-07-10 03:44 本頁(yè)面
【正文】 A， E， C， F} 簡(jiǎn)單路徑 :指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 簡(jiǎn)單回路 :指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。 10 連通圖： 無(wú)向 圖 G中任意兩個(gè)頂點(diǎn)之間都有路徑相連通。 連通分量： 非連通圖中的極大連通子圖。 B A C D F E B A C D F E 強(qiáng)連通圖： 在有向圖中 , 每一對(duì)頂點(diǎn) vi和 vj, 都存在一條從 vi到 vj和從 vj到vi的路徑 強(qiáng)連通分量： 非強(qiáng)連通圖中的極大強(qiáng)連通子圖。 A B E C F A B E C F 11 生成樹(shù)： v1 v2 v3 v4 生成森林： 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹(shù)。 由若干棵 生成樹(shù) 組成，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。（對(duì)有向或無(wú)向圖均適用） 12 CreatGraph(amp。G, V, VR)//按定義 (V,VR)構(gòu)造圖 DestroyGraph(amp。G) // 銷(xiāo)毀圖 結(jié)構(gòu)的建立和銷(xiāo)毀 對(duì)頂點(diǎn)的訪問(wèn)操作 LocateVex(G, u) // 若 G中存在頂點(diǎn) u，則返回該頂點(diǎn)在圖中 “ 位置 ” ，否則返回其它信息。 GetVex(G, v) // 返回 v 的值。 PutVex(amp。G, v, value) // 對(duì) v 賦值 value。 結(jié)構(gòu)的建立和銷(xiāo)毀 插入或刪除頂點(diǎn) 對(duì)鄰接點(diǎn)的操作 遍歷 插入或刪除弧 基本操作 對(duì)頂點(diǎn)的訪問(wèn)操作 13 對(duì)鄰接點(diǎn)的操作 FirstAdjVex(G, v)。 //返回 v的“第一個(gè)鄰接點(diǎn)” 若該頂點(diǎn)在 G中沒(méi)有鄰接點(diǎn)，則返回 “ 空 ” 。 NextAdjVex(G, v, w)。 //返回 v的（相對(duì)于 w的） “下一個(gè)鄰接點(diǎn) ” 。若 w是 v的最后一個(gè)鄰接點(diǎn)，則返回“ 空 ” 。 插入或刪除頂點(diǎn) InsertVex(amp。G, v)。 //在圖 G中增添新頂點(diǎn) v。 DeleteVex(amp。G, v)； //刪除 G中頂點(diǎn) v及其相關(guān)的弧。 14 插入和刪除弧 InsertArc(amp。G, v, w)。 // 在 G中增添弧 v,w，若 G是無(wú)向的，則還增添對(duì)稱弧 w,v。 DeleteArc(amp。G, v, w)。 //在 G中刪除弧 v,w，若 G是無(wú)向的，則還刪除對(duì)稱弧 w,v。 DFSTraverse(G, v, Visit())。 //從頂點(diǎn) v起深度優(yōu)先遍歷圖 G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù) Visit一次且僅一次。 BFSTraverse(G, v, Visit())。 //從頂點(diǎn) v起廣度優(yōu)先遍歷圖 G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù) Visit一次且僅一次。 遍 歷 15 圖的存儲(chǔ)結(jié)構(gòu) 圖的特點(diǎn)： 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)： 難！ （多個(gè)頂點(diǎn)，無(wú)序可言，無(wú)法僅以頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系） 可用 多重鏈表 (數(shù)組 )表示法 (鏈?zhǔn)?)表示法 3. 十字鏈表 表示法 4. 鄰接多重表 表示法 但可 用 數(shù)組 描述元素間關(guān)系。 非線性結(jié)構(gòu) （ m :n） 鄰接矩陣 ?鄰接表 ?十字鏈表 ?鄰接多重表 各種表示法成立的原則：存入電腦后能唯一復(fù)原 16 ① 建立一個(gè) 頂點(diǎn)表 和一個(gè) 鄰接矩陣 。 1. 鄰接矩陣（數(shù)組）表示法 ??? ??? , ),( , ,]][[.否則或者如果01AEjiEjijia r c s記錄各個(gè)頂點(diǎn)信息 表示各個(gè)頂點(diǎn)之間關(guān)系 ② 設(shè)圖 A = (V, E ) 有 n 個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組 [n][n]，定義為： 17 分析 1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1