圖的定義和術(shù)語及存儲結(jié)構(gòu)(已改無錯字)
2022-08-22 03:44:25 本頁面
【正文】 GraphKind kind。 // 圖的種類標(biāo)志 } MGraph。 22 2. 鄰接表（鏈?zhǔn)剑┍硎痉? ① 對每個頂點 vi 建立一個 單鏈表 ，把與 vi有關(guān)聯(lián)的 邊（或以 vi為尾的弧 )的信息鏈接 起來，表中每個結(jié)點都設(shè)為 3個域。 ② 每個單鏈表還應(yīng)當(dāng)附設(shè)一個 表頭結(jié)點 （設(shè)為 2個域），存 vi信息； adjvex nextarc info data firstarc 表結(jié)點 頭結(jié)點 鄰接點域，表示 vi 鄰接點的位置 鏈域， 指向下一條邊或弧的結(jié)點 數(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 請注意：鄰接表不唯一！因各個邊結(jié)點的鏈入順序是任意的。 v1 v2 v3 v4 v5 2 3 ^ 1 4 2 ^ 0 v1鄰接點 v4的位置 此無權(quán)圖未開第 3分量 TD(Vi)=單鏈表中 Vi鏈接的結(jié)點個數(shù) 24 例 2：有向圖的鄰接表如何表示？ v1 v2 v3 v4 V4 V3 ^ V2 V1 2 ^ 3 ^ 0 ^ 1 鄰接表 (出邊 ) V4 V3 V2 V1 ^ 3 ^ 0 ^ 2 ^ 0 逆鄰接表 (入邊 ) 0123 0123 在有向圖的鄰接表中不易找到指向該頂點的弧。 OD(Vi)=鄰接表中 Vi鏈接的結(jié)點數(shù)ID(Vi)=逆鄰接表中 Vi鏈接的結(jié)點數(shù) TD(Vi) = OD( Vi ) + ID( Vi ) 25 例 3：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。 80 64 1 2 5 當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！ 26 分析 1： 對于 n個頂點 e條邊的無向圖，鄰接表中除了 n個頭結(jié)點外，只有 2e個表結(jié)點 ,空間效率為 O(n+2e)。 若是稀疏圖 (en2)，則比鄰接矩陣表示法 O(n2)省空間。 鄰接表存儲法的特點： 分析 2:在有向圖中，鄰接表中除了 n個頭結(jié)點外，只有 e個表結(jié)點 ,空間效率為 O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。 —它其實是對鄰接矩陣法的一種改進，兩個結(jié)點表示一條邊或弧 鄰接表的 缺點： 鄰接表的 優(yōu)點： 空間效率高； 容易尋找頂點的鄰接點； 判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。 27 討論：鄰接表與鄰接矩陣有什么異同之處？ 1. 聯(lián)系： 鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。 2. 區(qū)別： ① 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但 鄰接表不唯一 （鏈接次序與頂點編號無關(guān)）。 ② 鄰接矩陣的空間復(fù)雜度為 O(n2),而鄰接表的空間復(fù)雜度為 O(n+e)。 3. 用途： 鄰接矩陣多用于稠密圖的存儲（ e接近 n(n1)/2)； 而鄰接表多用于稀疏圖的存儲（ en2) 28 圖的鄰接表在機內(nèi)如何表示？ （參見教材 P163） define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點數(shù) Typedef struct ArcNode { //弧結(jié)構(gòu) int adjvex。 //該弧所指向的頂點位置 struct ArcNode *nextarcs。 //指向下一條弧的指針 InfoArc *info。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1