[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)圖a(參考版)
2024-12-11 02:27本頁面
【正文】 35 一、深度優(yōu)先搜索 ( DFS ) 基本思想： —— 仿樹的先序遍歷過程 。 簡單歸納： ? 訪問起始點(diǎn) v。 如果有， 則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問； 如果沒有，就 再退回一步 進(jìn)行搜索 。 圖常用的遍歷： 怎樣避免重復(fù)訪問？ 34 深度優(yōu)先搜索（遍歷）步驟： 詳細(xì)歸納： ?在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問 它的任一鄰接頂點(diǎn) w1； ?再從 w1 出發(fā)，訪問 與 w1鄰接 但還 未被訪問 過的頂點(diǎn) w2； ?然后再從 w2 出發(fā)，進(jìn)行類似的訪問， … ?如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。 解決思路： 可設(shè)置一個 輔助數(shù)組 visited [n ]，用來標(biāo)記每個被訪問過的頂點(diǎn)。 遍歷實(shí)質(zhì)： 找每個頂點(diǎn)的鄰接點(diǎn)的過程。 0 v1 1 v2 2 v3 3 v4 4 v5 0 1 2 3 4 Firstedge data 頂點(diǎn)結(jié)點(diǎn) mark info jlink jvex ilink ivex 邊結(jié)點(diǎn) 空間復(fù)雜度和建表的時間復(fù)雜度都與鄰接表相同。 設(shè)立 邊結(jié)點(diǎn)， 6個域 （每條邊是一個數(shù)據(jù)元素） 設(shè)立 頂點(diǎn)結(jié)點(diǎn)， 2個域 （每個頂點(diǎn)也是一個數(shù)據(jù)元素） mark ivex ilink jvex jlink info 邊結(jié)點(diǎn) data : 存儲頂點(diǎn)信息 Firstedge : 依附頂點(diǎn)的第一條邊結(jié)點(diǎn) data Firstedge 頂點(diǎn)結(jié)點(diǎn) 4. 鄰接多重表表示法 mark： 標(biāo)志域 ivex， jvex : 邊依附的兩個頂點(diǎn)位置 ilink: 指向下一條依附頂點(diǎn) i 的邊位置 jlink。 Firstout Firstin data 頂點(diǎn)結(jié)點(diǎn) info tlink hlink headvex tailvex 弧結(jié)點(diǎn) 0 v1 1 v2 2 v3 3 v4 0 1 2 3 0 1 0 ^ ^ 2 此無權(quán)圖未開第 4分量 空間復(fù)雜度和建表的時間復(fù)雜度都與鄰接表相同 。 采用十字鏈表構(gòu)造有向圖算法見教材 p165 30 v1 v2 v3 v4 2 0 2 ^ ^ 3 3 ^ 0 3 ^ ^ 1 例：畫出有向圖的十字鏈表。 //表頭向量 int vexnum, arum。 }VexNode。 Typedef struct VexNode{ //頂點(diǎn)結(jié)構(gòu) , 3分量 VertexType data。 InfoType *info。 開設(shè) 弧結(jié)點(diǎn)，設(shè) 5個域 （每段弧是一個數(shù)據(jù)元素） 開設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè) 3個域 （每個頂點(diǎn)也是一個數(shù)據(jù)元素） tailvex headvex hlink tlink info data : 頂點(diǎn)信息 Firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn) Firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn) data Firstin Firstout 頂點(diǎn)結(jié)點(diǎn) 弧結(jié)點(diǎn) 3. 十字鏈表表示法 tailvex: 弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息 n個頂點(diǎn)的集合怎樣儲存？ 仍用順序存儲結(jié)構(gòu) 29 define MAX_VERTEX_NUM 20 十字鏈表存儲結(jié)構(gòu)描述： Typedef struct ArcBox { //弧結(jié)點(diǎn)結(jié)構(gòu)， 5分量 int tailvex , headvex 。 //該弧相關(guān)信息的指針 } ArcNode； 28 它是 有向圖 的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 //該弧所指向的頂點(diǎn)位置 struct ArcNode *nextarcs。 //還應(yīng)說明圖的種類（用標(biāo)志） }ALGraph。 //應(yīng)包含鄰接表 int vexnum, arum。 //指向依附該頂點(diǎn)的第一條弧的指針 }VNode, AdjList[ MAX_VERTEX_NUM ]。 3. 用途： 鄰接矩陣多用于稠密圖的存儲（ e接近 n(n1)/2)； 而鄰接表多用于稀疏圖的存儲（ en2) 27 圖的鄰接表在機(jī)內(nèi)如何表示？ （參見教材 P163） define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點(diǎn)數(shù) 空間效率為 O(n+2e)或 O(n+e) 時間效率為 O(n+e*n) Typedef struct VNode{ //頂點(diǎn)結(jié)構(gòu) VertexType data。 2. 區(qū)別： ① 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點(diǎn)編號一致），但 鄰接表不唯一 （鏈接次序與頂點(diǎn)編號無關(guān)）。 — 它其實(shí)是對鄰接矩陣法的一種改進(jìn) 怎樣計(jì)算無向圖頂點(diǎn)的度？ 鄰接表的 缺點(diǎn)： 怎樣計(jì)算有向圖頂點(diǎn)的出度？ 怎樣計(jì)算有向圖頂點(diǎn)的入度？ 怎樣計(jì)算有向圖頂點(diǎn) Vi的度： 需遍歷全表 鄰接表的 優(yōu)點(diǎn)： TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個數(shù) OD(Vi)＝ 單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù) I D( Vi ) ＝ 鄰接點(diǎn)為 Vi的弧個數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1