圖的定義和術(shù)語及存儲(chǔ)結(jié)構(gòu)(存儲(chǔ)版)
【正文】 。 空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。 （ 1）設(shè)立邊結(jié)點(diǎn)， 6個(gè)域（每條邊是一個(gè)數(shù)據(jù)元素） （ 2）設(shè)立頂點(diǎn)結(jié)點(diǎn)， 2個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素） mark ivex ilink jvex jlink info 邊結(jié)點(diǎn) 4. 鄰接多重表表示法 mark： 標(biāo)志域，標(biāo)記該邊是否被搜索過。 //頂點(diǎn)信息 ArcNode * firstarc。 3. 用途： 鄰接矩陣多用于稠密圖的存儲(chǔ)（ e接近 n(n1)/2)； 而鄰接表多用于稀疏圖的存儲(chǔ)（ en2) 28 圖的鄰接表在機(jī)內(nèi)如何表示？ （參見教材 P163） define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點(diǎn)數(shù) Typedef struct ArcNode { //弧結(jié)構(gòu) int adjvex。 80 64 1 2 5 當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！ 26 分析 1： 對(duì)于 n個(gè)頂點(diǎn) e條邊的無向圖，鄰接表中除了 n個(gè)頭結(jié)點(diǎn)外，只有 2e個(gè)表結(jié)點(diǎn) ,空間效率為 O(n+2e)。 // 鄰接矩陣 int vexnum, arum。 圖的鄰接矩陣在機(jī)內(nèi)如何表示？ （參見教材 P161） 注： 用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣 define INFINITY INT_MAX //最大值 ∞ define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點(diǎn)數(shù) typedef enum {DG, DN, UDG,UDN } GraphKind。 分析 2： 頂點(diǎn) vi的出度 =第 i行元素之和 。 DFSTraverse(G, v, Visit())。 DeleteVex(amp。 結(jié)構(gòu)的建立和銷毀 插入或刪除頂點(diǎn) 對(duì)鄰接點(diǎn)的操作 遍歷 插入或刪除弧 基本操作 對(duì)頂點(diǎn)的訪問操作 13 對(duì)鄰接點(diǎn)的操作 FirstAdjVex(G, v)。 A B E C F A B E C F 11 生成樹： v1 v2 v3 v4 生成森林： 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。 頂點(diǎn) v的度： 是和 v 相關(guān)聯(lián)的邊的數(shù)目 ,記為 TD(v). 頂點(diǎn) v的出度 : 以頂點(diǎn) v 為尾的弧的數(shù)目 。 ② 無向完全圖有 n(n1)/2 條邊 。 P(v,w) 定義了弧 v,w的意義或信息。 子 圖： 邊較少的圖。 A B E C F 如 :從 A到 F長(zhǎng)度為 3 的路徑{A,B,C,F}或 {A， E， C， F} 簡(jiǎn)單路徑 :指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。G, V, VR)//按定義 (V,VR)構(gòu)造圖 DestroyGraph(amp。 //返回 v的（相對(duì)于 w的） “下一個(gè)鄰接點(diǎn) ” 。G, v, w)。 //從頂點(diǎn) v起廣度優(yōu)先遍歷圖 G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù) Visit一次且僅一次。 v1 v2 v3 v4 A 鄰接矩陣： = ( v1 v2 v3 v4 ) v1 v2 v3 v4 注： 在有向圖的鄰接矩陣中， 第 i行含義：以結(jié)點(diǎn) vi為尾的弧 (即出度邊）； 第 j列含義：以結(jié)點(diǎn) vj為頭的弧 (即入度邊）。 //對(duì)無權(quán)圖 ,用 1或 0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型 。 22 2. 鄰接表（鏈?zhǔn)剑┍硎痉? ① 對(duì)每個(gè)頂點(diǎn) vi 建立一個(gè) 單鏈表 ，把與 vi有關(guān)聯(lián)的 邊（或以 vi為尾的弧 )的信息鏈接 起來，表中每個(gè)結(jié)點(diǎn)都設(shè)為 3個(gè)域。若是稀疏圖，則比鄰接矩陣表示法合適。 //該弧相關(guān)信息的指針 } ArcNode； 29 Typedef
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1