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