[其它課程]數(shù)據(jù)結(jié)構(gòu)第16次課圖a(編輯修改稿)
2025-02-17 12:57 本頁面
【文章內(nèi)容簡介】 f enum {DG, DN, AG,AN } GraphKind。 //有向 /無向圖，有向 /無向網(wǎng)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 ]。圖的鄰接矩陣存儲表示 （參見教材P161）對于 n個頂點的圖或網(wǎng)，空間效率 =O(n2)18數(shù)據(jù)結(jié)構(gòu)Typedef struct //圖的定義{ VertexType vexs [MAX_VERTEX_NUM ] 。 //頂點表，用一維向量即可AdjMatrix arcs。 //鄰接矩陣Int Vernum, arum。 //頂點總數(shù)，?。ㄟ叄┛倲?shù)GraphKind kind。 //圖的種類標志} Mgraph。19數(shù)據(jù)結(jié)構(gòu)二、鄰接表（鏈式）表二、鄰接表（鏈式）表示法示法v 對每個頂點對每個頂點 vi 建立一個建立一個 單鏈表單鏈表 ，把與，把與 vi有關(guān)聯(lián)的有關(guān)聯(lián)的 邊的信息邊的信息 （即（即度或出度邊）度或出度邊） 鏈接鏈接 起來，表中每個結(jié)點都設(shè)為起來，表中每個結(jié)點都設(shè)為 3個域；個域；v 每個單鏈表還應(yīng)當附設(shè)一個每個單鏈表還應(yīng)當附設(shè)一個 頭結(jié)點頭結(jié)點 （設(shè)為（設(shè)為 2個域），存?zhèn)€域），存 vi信息；信息；adjvex info nextarcdata firstarc表結(jié)點表結(jié)點頭結(jié)點頭結(jié)點鄰接點域 ， 表示 vi一個鄰接點的 位置鏈域 ， 指向vi下一個邊或弧的結(jié)點數(shù)據(jù)域 ， 與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域 ，存儲頂點 vi 信息鏈域 ， 指向單鏈表的第一個結(jié)點v 每個單鏈表的每個單鏈表的 頭結(jié)點另外用順序存儲頭結(jié)點另外用順序存儲 結(jié)構(gòu)存儲。結(jié)構(gòu)存儲。20數(shù)據(jù)結(jié)構(gòu)例例 1：： 無向圖的鄰無向圖的鄰接表接表v1 v2v3v5v4鄰接表01234^1334 ^14 2 ^0例例 2：： 有向圖的鄰接表有向圖的鄰接表v1 v2v3 v4V4V3^V2V1 2^3^0^1鄰接表 (出邊 )V4V3V2V1 ^3^0^2^0逆鄰接表 (入邊 )注：注： 鄰接表不唯一，因各個邊結(jié)點的鏈入順序是任意的。鄰接表不唯一，因各個邊結(jié)點的鏈入順序是任意的。v1v2v3v4v523 ^14 2 ^021數(shù)據(jù)結(jié)構(gòu)例例 3：： 已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。絡(luò)。8064125當鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！22數(shù)據(jù)結(jié)構(gòu)分析 1: 對于 n個頂點 e條邊的無向圖 ，鄰接表中除了 n個頭結(jié)點外，只有 2e個表結(jié)點 ,空間效率為 O(n+2e)。若是稀疏圖 (en2)， 則比鄰接矩陣表示法 O(n2)省空間。鄰接表存儲法的特點：分析 2:在 有向圖 中，鄰接表中除了 n個頭結(jié)點外，只有 e個表結(jié)點,空間效率為 O(n+e)。 若是稀疏圖，則比鄰接矩陣表示法合適。— 它其實是對鄰接矩陣法的一種改進怎樣計算無向圖頂點的度？鄰接表的 缺點：怎樣計算有向圖頂點的出度？怎樣計算有向圖頂點的入度？怎樣計算有向圖頂點 Vi的度： 需遍歷全表鄰接表的 優(yōu)點：TD(Vi)=單鏈表中鏈接的結(jié)點個數(shù)OD(Vi)＝ 單鏈出邊表中鏈接的結(jié)點數(shù)I D( Vi ) ＝ 鄰接點為 Vi的弧個數(shù)TD(Vi) = OD( Vi ) + I D( Vi )空間效率高； 容易尋找頂點的鄰接點；判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。23數(shù)據(jù)結(jié)構(gòu)討論：鄰接表與鄰接矩陣有什么異同之處？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)24數(shù)據(jù)結(jié)構(gòu)圖的鄰接表存儲表示 （參見教材P163）define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點數(shù)Typedef struct ArcNode { int adjvex。 //該弧所 指向的頂點位置 struct ArcNode *nextarcs。 //指向下一條弧的指針 InfoArc *info。 //該弧相關(guān)信息的指針} ArcNode；Typedef struct VNode{ //頂點結(jié)構(gòu) VertexType data。 //頂點信息 ArcNode * firstarc。 //指向依附該頂點的第一條弧的指針}VNode, AdjList[ MAX_VERTEX_NUM ]。 Typedef struct { //圖結(jié)構(gòu) AdjList vertics 。 //應(yīng)包含鄰接表 int vexnum, arum。 //應(yīng)包含頂點總數(shù)和弧總數(shù) int kind。 //還應(yīng)說明圖的種類（用標志）}ALGraph。 //圖結(jié)構(gòu) 圖的鄰接表生成算法作為自測題?？臻g效率為 O(n+2e)或O(n+e)時間效率為 O(n+e*n)25數(shù)據(jù)結(jié)構(gòu)一、 深度優(yōu)先搜索二、 廣度優(yōu)先搜索 圖的遍歷遍歷定義： 從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做 圖圖的遍歷的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1