圖的定義和術語及存儲結構-資料下載頁
2025-07-25 03:44本頁面
【正文】 //該弧相關信息的指針 } ArcNode； 29 Typedef struct { //圖結構 AdjList vertics 。 //應包含鄰接表 int vexnum, arum。 //應包含頂點總數(shù)和弧總數(shù) int kind。 //還應說明圖的種類（用標志） }ALGraph。 Typedef struct VNode{ //頂點結構 VertexType data。 //頂點信息 ArcNode * firstarc。 //指向第一條依附該頂點的弧的指針 }VNode, AdjList[ MAX_VERTEX_NUM ]。 //鄰接表 30 它是 有向圖 的另一種鏈式存儲結構。 思路： 將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。 (1)開設弧結點，設 5個域（每段弧是一個數(shù)據(jù)元素） (2)開設頂點結點，設 3個域（每個頂點也是一個數(shù)據(jù)元素） tailvex headvex hlink tlink info 弧結點 3. 十字鏈表表示法 tailvex: 弧尾頂點位置 headvex: 弧頭頂點位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息 31 data : 頂點信息 firstin : 以頂點為弧頭的第一條弧結點 firstout: 以頂點為弧尾的第一條弧結點 問： n個頂點的集合怎樣儲存？ 順序存儲結構 data firstin firstout 頂點結點 十字鏈表優(yōu)點： 容易操作，如求頂點的入度、出度等。 空間復雜度和建表的時間復雜度都與鄰接表相同。 32 A B C A B C 0 1 2 ∧ 0 2 ∧ 0 1 2 1 2 0 ∧ 例：畫出有向圖的十字鏈表。 tailvex headvex hlink tlink 弧結點 data firstin firstout 頂點結點 ∧ ∧ ∧ A,B C,A C,B A,C 33 這是 無向圖 的另一種鏈式存儲結構，當對邊操作時建議采用此種結構存儲。 （ 1）設立邊結點， 6個域（每條邊是一個數(shù)據(jù)元素） （ 2）設立頂點結點， 2個域（每個頂點也是一個數(shù)據(jù)元素） mark ivex ilink jvex jlink info 邊結點 4. 鄰接多重表表示法 mark： 標志域，標記該邊是否被搜索過。 ivex， jvex : 邊依附的兩個頂點位置 ilink: 指向下一條依附頂點 i 的邊位置 Jlink： 指向下一條依附頂點 j 的邊位置 info: 邊信息 34 data : 存儲頂點信息 firstedge : 依附頂點的第一條邊結點 data firstedge 頂點結點 問 :n個頂點的集合怎樣儲存？ 仍用順序存儲結構 鄰接多重表優(yōu)點： 容易操作，如求頂點的度 ,對邊操作等。 空間復雜度和建表的時間復雜度都與鄰接表相同。 35 v1 v2 v3 v5 v4 例：畫出無向圖的鄰接多重表。 mark ivex ilink jvex jlink 邊結點 data firstedge 頂點結點 1 2 1 ^ 4 2 3 2 ^ 4 3 ^ 4 ^ 0 v1 1 v2 2 v3 3 v4 4 v5 0 1 2 3 4 0 1 ^… 0 3 (v1,v2) (v1,v4) (v2,v5) (v2,v3) (v3,v4) (v3,v5) (v4,v5)
環(huán)評公示相關推薦
鄂ICP備17016276號-1