【正文】 / 對無權(quán)圖，用 1或 0表示相鄰否； // 對帶權(quán)圖，則為權(quán)值類型。 InfoType *info。 // 該弧相關(guān)信息的指針 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]。 typedef struct { // 圖的定義 VertexType // 頂點(diǎn)信息 vexs[MAX_VERTEX_NUM]。 AdjMatrix arcs。 // 弧的信息 int vexnum, arum。 // 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind。 // 圖的種類標(biāo)志 } MGraph。 網(wǎng)絡(luò)的鄰接矩陣 ???????????????????jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),(]][[0EEEEWA . e d g eA B D C E 15 9 7 21 11 3 2 ????????????????0 1 5 ∞ 9 ∞∞ 0 3 ∞ ∞= ∞ ∞ 0 ∞ 2∞ ∞ 2 1 0 ∞1 1 7 ∞ ∞A . e d g e 00 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3 B A C D F E 二、圖的鄰接表 存儲表示 同一個頂點(diǎn)發(fā)出的邊 鏈接在同一個邊鏈表中 ，每一個鏈結(jié)點(diǎn)代表一 條邊 (邊結(jié)點(diǎn) ), 結(jié)點(diǎn)中有 另一頂點(diǎn)的下標(biāo) adjvex 和指針 nextedge。 1 4 2 3 0 1 2 0 1 2 3 4 A B C D E 有向圖的鄰接表 ? ? ? ? ? A B E C D 可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。 A B E C D 有向圖的逆鄰接表 A B C D E 3 0 3 4 2 0 ? ? ? ? ? 0 1 2 3 4 在有向圖的鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。 鄰接表表示法特點(diǎn)： 1）無向圖鄰接表邊結(jié)點(diǎn)數(shù)是邊數(shù)的兩倍 . 2）頂點(diǎn) vi的度：在無向圖中等于第 i個鏈表中的 結(jié)點(diǎn)數(shù)；在有向圖鄰接表中 ,第 i行的結(jié)點(diǎn)數(shù)等于 頂點(diǎn) i的出度，在有向圖逆鄰接表中 ,第 i行的結(jié)點(diǎn) 數(shù)等于頂點(diǎn) i的入度。 3）在鄰接表上容易找到任一頂點(diǎn)的第一個鄰接點(diǎn) 和下一個鄰接點(diǎn) 4）設(shè)存儲頂點(diǎn)的一維數(shù)組大小為 n(圖的頂點(diǎn)數(shù) n), G占用存儲空間： n+e； G占用存儲空間與它的頂 點(diǎn)數(shù)和邊數(shù)有關(guān)；適用于邊稀疏的圖； typedef struct ArcNode { int adjvex。 // 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc。 // 指向下一條弧的指針 InfoType *info。 // 該弧相關(guān)信息的指針 } ArcNode。 adjvex nextarc info 弧的結(jié)點(diǎn)結(jié)構(gòu) typedef struct VNode { VertexType data。 // 頂點(diǎn)信息 ArcNode *firstarc。 // 指向第一條依附該頂點(diǎn)的弧 } VNode, AdjList[MAX_VERTEX_NUM]。 data firstarc 頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu) typedef struct { AdjList vertices。 int vexnum, arum。 int kind。 // 圖的種類標(biāo)志 } ALGraph。 圖的結(jié)構(gòu)定義 三、有向圖的十字鏈表存儲表示 弧的結(jié)點(diǎn)結(jié)構(gòu) 弧尾頂點(diǎn)位置 弧頭頂點(diǎn)位置 弧的相關(guān)信息 指向下一個有相同弧尾的結(jié)點(diǎn) 指向下一個有相同弧頭的結(jié)點(diǎn) typedef struct ArcBox { // 弧 的結(jié)構(gòu)表示 int tailvex, headvex。 InfoType *info。 struct ArcBox *hlink, *tlink。 } VexNode。 頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu) 頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧 指向該頂點(diǎn)的第一條出弧 typedef struct VexNode { // 頂點(diǎn)的結(jié)構(gòu)表示 VertexType data。 ArcBox *firstin, *firstout。 } VexNode。 typedef struct { VexNode xlist[MAX_VERTEX_NUM]。 // 頂點(diǎn)結(jié)點(diǎn) (表頭向量 ) int vexnum, arum。 //有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) } OLGraph。 有向圖的結(jié)構(gòu)表示 (十字鏈表 ) A B C D A B C D 0 1 0 2 2 0 2 3 3 0 3 1 3 2 0 1 2 3 四、無向圖的鄰接多重表存儲表示 typedef struct Ebox { VisitIf mark。 // 訪問標(biāo)記 int ivex, jvex。 //該邊依附的兩個頂點(diǎn)的位置 struct EBox *ilink, *jlink。 InfoType *info。 // 該邊信息指針 } EBox。 邊的結(jié)構(gòu)表示 typedef struct { // 鄰接多重表 VexBox adjmulist[MAX_VERTEX_NUM]。 int vexnum, edgenum。 } AMLGraph。 頂點(diǎn)的結(jié)構(gòu)表示 typedef struct VexBox { VertexType data。 EBox *firstedge。 // 指向第一條依附該頂點(diǎn)的邊 } VexBox。 無向圖的結(jié)構(gòu)表示 A B C D E 0 1 2 3 4 A B C D E 0 1 0 3 2 1 2 3 2 4 4 1 圖的遍歷 從圖中某個頂點(diǎn)出發(fā)游歷圖，訪遍 圖中其余頂點(diǎn)，并且使圖中的每個頂點(diǎn) 僅被訪問一次的過程。 深度優(yōu)先搜索 廣度優(yōu)先搜索 遍歷應(yīng)用舉例 從圖中某個頂點(diǎn) V0 出發(fā)，訪問此頂點(diǎn)，然后 依次從 V0的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖 ， 直至圖中所有和 V0有路徑相通的頂點(diǎn)都被訪問到。 一、深度優(yōu)先搜索遍歷圖 連通圖的深度優(yōu)先搜索遍歷 V w1 SG1 SG2 SG3 W W2和 W3 均為 V 的鄰接點(diǎn)， SG SG2 和 SG3 分別為含頂點(diǎn)W W2和 W3 的子圖。 訪問頂點(diǎn) V ： for (W W W3 ) 若 該鄰接點(diǎn) W未被訪問 ， 則 從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。 w2 w3 從上頁的圖解可見 : 1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷； 解決的辦法是：為每個頂點(diǎn)設(shè)立一個 “訪問標(biāo)志 visited[w]”。 2. 如何判別 V的鄰接點(diǎn)是否被訪問？ a c b d e g f F F F F F F F T T T T