[計算機軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)圖a(編輯修改稿)
2025-01-04 02:27 本頁面
【文章內(nèi)容簡介】 19 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。 n個頂點需要 n*n個單元存儲邊 (弧 )?？臻g效率為O(n2)。 例 3 ： 有權(quán)圖（即 網(wǎng)絡(luò) ）的 鄰接矩陣 如何表示？ 定義： [ i ][ j ]= Wij vi, vj 或（ vi, vj） ∈ VR ∞ 無邊（弧） v1 v2 v3 v4 N v5 v6 5 4 8 9 7 5 5 6 1 3 以有向網(wǎng)為例： 鄰接矩陣： = ( v1 v2 v3 v4 v5 v6 ) 鄰接矩陣法 優(yōu)點： 鄰接矩陣法 缺點： 頂點表： ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 對稀疏圖而言尤其浪費空間 。 20 注： 用兩個數(shù)組分別存儲頂點表和鄰接矩陣 define INFINITY INT_MAX //最大值 ∞ define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點數(shù) Typedef enum {DG, DN, UG, UN } GraphKind。 //有向 /無向圖，有向 /無向網(wǎng) 圖的鄰接矩陣在機內(nèi)如何表示？ （參見教材 P161） 對于 n個頂點的圖或網(wǎng)，空間效率 =O(n2) Typedef struct ArcCell{ //弧（邊） 結(jié)點的定義 VRType adj。 //頂點間關(guān)系，無權(quán)圖取 1或 0；有權(quán)圖取權(quán)值類型 InfoType *info。 //該弧相關(guān)信息的指針 }ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]。 Typedef struct{ //圖的定義 VertexType vexs [MAX_VERTEX_NUM ] 。 //頂點表，用一維向量即可 (n) AdjMatrix arcs。 //鄰接矩陣 n*n Int Vernum, arum。 //頂點總數(shù) n，?。ㄟ叄┛倲?shù) e GraphKind kind。 //圖的種類標志 }MGraph。 21 Status CreateUDN(MGraph amp。G){ //無向網(wǎng)的構(gòu)造，用鄰接矩陣表示 scanf(amp。, amp。, amp。IncInfo)。 //輸入總頂點數(shù) n、總弧數(shù) e和信息 for(i=0。i,。++i) scanf(amp。[i] )。//輸入 n個頂點值，存入一維向量 例： 用鄰接矩陣生成 無向網(wǎng) 的算法 （參見教材 P162） 對于 n個頂點 e條弧的網(wǎng)， 建網(wǎng)時間效率 = O(n+n2+e*n) for(i=0。 i。 ++i) //對鄰接矩陣 n*n個單元初始化， adj=∞ ,info=NULL for(j=0。j。++j) [i][j]={INFINITY, NULL}。 for(k=0。k。++k){ //給鄰接矩陣有關(guān)單元賦初值 (循環(huán)次數(shù)＝弧數(shù) e scanf(amp。v1, amp。v2, amp。w)。 //輸入弧的兩頂點以及對應(yīng)權(quán)值 i=LocateVex(G,v1)。 j=LocateVex(G,v2)。 //找到兩頂點在矩陣中的位置 (n次 ) [i][j].adj=w。 //輸入對應(yīng)權(quán)值 If(IncInfo) Input(*[i][j].info)。 //如果弧有信息則填入 [i][j] = [j] [i]； //無向網(wǎng)是對稱矩陣 } return OK。 } // CreateUDN 22 2. 鄰接表（鏈式）表示法 ① 對每個頂點 vi 建立一個 單鏈表 ，把與 vi有關(guān)聯(lián)的 邊的信息 （即度或出度邊） 鏈接 起來，表中每個結(jié)點都設(shè)為 3個域 : ② 每個單鏈表還應(yīng)當附設(shè)一個 頭結(jié)點 （設(shè)為 2個域），存 vi信息； adjvex nextarc info data firstarc 表結(jié)點 頭結(jié)點 鄰接點域， 表示 vi 鄰接點的位置 鏈域， 指向下一個邊或弧的結(jié)點 數(shù)據(jù)域， 與邊有關(guān)信息（如權(quán)值） 數(shù)據(jù)域，存儲頂點 vi 信息 鏈域， 指向單鏈表的第一個結(jié)點 ③ 每個單鏈表的 頭結(jié)點另外用順序存儲 結(jié)構(gòu)存儲。 23 例 1： 無向圖的鄰接表如何表示？ v1 v2 v3 v5 v4 鄰接表 0 1 2 3 4 ^ 1 3 3 4 ^ 1 4 2 ^ 0 例 2： 有向圖的鄰接表如何表示？ v1 v2 v3 v4 V4 V3 ^ V2 V1 2 ^ 3 ^ 0 ^ 1 鄰接表 (出邊 ) V4 V3 V2 V1 ^ 3 ^ 0 ^ 2 ^ 0 逆鄰接表 (入邊 ) 請注意：鄰接表不惟一！因各個邊結(jié)點的鏈入順序是任意的。 v1 v2 v3 v4 v5 2 3 ^ 1 4 2 ^
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1