[計算機軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)圖a-文庫吧資料
2024-12-14 02:27本頁面
【正文】 TD(Vi) = OD( Vi ) + I D( Vi ) 空間效率高； 容易尋找頂點的鄰接點； 判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。 鄰接表存儲法的特點： 分析 2:在 有向圖 中，鄰接表中除了 n個頭結(jié)點外，只有 e個表結(jié)點 ,空間效率為 O(n+e)。 當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！ 25 分析 1: 對于 n個頂點 e條邊的無向圖 ，鄰接表中除了 n個頭結(jié)點外，只有 2e個表結(jié)點 ,空間效率為 O(n+2e)。 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é)點的鏈入順序是任意的。 //如果弧有信息則填入 [i][j] = [j] [i]； //無向網(wǎng)是對稱矩陣 } return OK。 //找到兩頂點在矩陣中的位置 (n次 ) [i][j].adj=w。 //輸入弧的兩頂點以及對應(yīng)權(quán)值 i=LocateVex(G,v1)。v2, amp。++k){ //給鄰接矩陣有關(guān)單元賦初值 (循環(huán)次數(shù)＝弧數(shù) e scanf(amp。 for(k=0。j。 i。[i] )。i,。IncInfo)。, amp。 21 Status CreateUDN(MGraph amp。 //頂點總數(shù) n，?。ㄟ叄┛倲?shù) e GraphKind kind。 //頂點表，用一維向量即可 (n) AdjMatrix arcs。 //該弧相關(guān)信息的指針 }ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]。 //有向 /無向圖，有向 /無向網(wǎng) 圖的鄰接矩陣在機內(nèi)如何表示？ （參見教材 P161） 對于 n個頂點的圖或網(wǎng)，空間效率 =O(n2) Typedef struct ArcCell{ //?。ㄟ叄?結(jié)點的定義 VRType adj。 例 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 對稀疏圖而言尤其浪費空間 。 n個頂點需要 n*n個單元存儲邊 (弧 )。 ID(vi )=? [ j ][i ] 頂點的 度 =第 i行元素之和 +第 i列元素之和 , 即： TD( vi ) = OD( vi ) + ID( vi ) v1 v2 v3 v4 A 鄰接矩陣： = ( v1 v2 v3 v4 ) v1 v2 v3 v4 注： 在有向圖的鄰接矩陣中， 第 i行含義：以結(jié)點 vi為尾的弧 (即出度邊）； 第 i列含義：以結(jié)點 vi為頭的弧 (即入度邊）。 頂點表： 下面無向圖的鄰接矩陣如何表示？ v1 v2 v3 v5 v4 A 記錄各個頂點信息 表示各個頂點之間關(guān)系 ② 設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 [n][n]，定義為： 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 18 例 2 ： 下面有向圖的鄰接矩陣如何表示？ 分析 1： 有向圖的鄰接矩陣 可能是不對稱 的。 非線性結(jié)構(gòu) （ m :n） 鄰接矩陣 ?鄰接表 ?十字鏈表 ?鄰接多重表 各種表示法成立的原則：存入電腦后能 惟一復(fù)原 17 ① 建立一個 頂點表 和一個 鄰接矩陣 。 操作結(jié)果： 在 G 中刪除以 v, w為頂點的邊 。G, v, w)。 初始條件： 圖 G 存在， v 和 w 是 G 中兩個頂點。 14 加工型操作 InsertEdge(amp。若 w是 v 的最后一個鄰接點，則返回“空”。 初始條件 :圖 G存在 ,v是 G中某個頂點 ,w是 v的鄰接頂點。 若 v,w∈ G，則稱 w 為 v 的鄰接點，若 (v,w)∈ G，則稱 w 和 v 互為 鄰接點 。 操作結(jié)果： 返回 v 的第一個 鄰接點 。 引用型操作
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1