【正文】 i列 ）的元素之和是頂點(diǎn) Vi的度 。 例 ， G1中 V2的度是 3。 – 有向圖 鄰接矩陣第 i行的元素之和為頂點(diǎn) Vi的出度；第 j列的元素之和為頂點(diǎn) Vj的入度 。 例 ， G2中 ， V2的出度為 0（ 第 2行的元素之和為 0） ， V1的入度為 1（ 第 1列的元素之和為 1） 。 o o o o v1 v2 v3 v4 G1 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 3 2 4 G2 網(wǎng)的鄰接矩陣 ? 定義： Wij 若 （ Vi， Vj） 或 〈 Vi， Vj〉 ? E A[i， j] = ? 若 （ Vi， Vj） 或 〈 Vi， Vj〉 ? E = V1 V2 V3 V4 A== ? 5 ? 3 ? ? 2 ? ? ? ? ? ? ? 7 ? 4x4 G5的鄰接矩陣。 V1 V2 V3 V4 G5 2 3 5 7 鄰接表表示法 ? 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表 （ n個(gè)頂點(diǎn)建立 n個(gè)單鏈表 ） ， 第 i個(gè)單鏈表中的結(jié)點(diǎn)包含頂點(diǎn) Vi的所有鄰接頂點(diǎn) 。 ? 在鄰接表中 ， 每個(gè)頂點(diǎn)由三個(gè)域組成： ? 每個(gè)單鏈表附設(shè)一個(gè)頭結(jié)點(diǎn) ， 結(jié)構(gòu)為： adjvex data nextarc 頂點(diǎn) Vi的鄰接點(diǎn) 與邊或弧有關(guān)的權(quán)值 指向 Vi的下一個(gè) 鄰接點(diǎn)的指針 Vexdata firstarc 指向 Vi單鏈表的第一個(gè)結(jié)點(diǎn) 存放 Vi信息 鄰接表存儲(chǔ)結(jié)構(gòu)描述 C語言描述 define VTXNUM n struct arode { int adjvex； float data； struct arode *nextarc； }； typedef struct arode ARCNODE ； struct headnode { int data ； ARCNODE * firstarc ； } adjlist[VTXNUM]； 無向圖 G1的鄰接表 V1 V2 V3 V4 ^ V3 V2 V1 V4 ^ V3 ^ V1 V2 ^ V2 頂點(diǎn) Vi的度恰好就是 第 i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。 o o o o v1 v2 v3 v4 G1 有向圖 G2的鄰接表 1 2 3 4 ^ 2 3 ^ 4 ^ 1 ^ ?在有向圖中，第 i個(gè)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn) Vi的出度；例如， V2的出度為 0。 ?為求入度，必須遍歷整個(gè)鄰接表。 1 3 2 4 G2 逆鄰接表 ? 為求頂點(diǎn) Vi的入度 ， 對(duì)每個(gè)頂點(diǎn) Vi， 建立一個(gè)鏈接以 Vi為弧頭的鄰接點(diǎn)鏈表 ， 稱該表為逆鄰接表 。 例如 G2的逆鄰接表為： 1 2 3 4 4 1 1 3 ^ ^ ^ ^ 顯然逆鄰接表的單鏈表中結(jié)點(diǎn)的個(gè)數(shù)就是頂點(diǎn) Vi的入度。 1 3 2 4 G2 建立鄰接表的算法 ? 操作步驟： – step1 初始化鄰接表的 n個(gè)頭結(jié)點(diǎn) ， 并讀入一條弧或邊的偶對(duì) 〈 i， j〉 或 （ i， j） 。 – step2 申請一個(gè)結(jié)點(diǎn) S的空間 ， 將 S插入到第 i個(gè)單鏈表中； – step3 讀下一條弧或邊的偶對(duì) ， 若存在此弧或邊 ， 則繼續(xù)執(zhí)行 step2；否則 ， 結(jié)束 。 建立鄰接表算法的程序 createadjlist(struct headnode G[],int n) { int i,j,k。 float w。 ARCNODE *s。 for (k=1。 k= n 。 k++ ) { scanf( “%d”, amp。G[k].data)。 G[k].firstarc = NULL 。 } scanf(“%d,%d,%f”, amp。i,amp。j,amp。w )。 while (( i =0 amp。amp。 i n)amp。amp。(j=0 amp。amp。 jn)) { s= (ARCNODDE *)malloc(sizeof(ARCNODE))。 sadjvex = j。 sinfo = w。 snextarc = G[i].firstarc。 G[i].firstarc = s。 scanf(“%d,%d,%f”,amp。i,amp。j,amp。w)。 } } 三、圖的遍歷 ? 圖的遍歷 （ Traversing Graph） 從圖中指定頂點(diǎn)出發(fā)訪問圖中每一個(gè)頂點(diǎn) ， 且使每個(gè) 頂點(diǎn)只被訪問一次 ， 該過程為圖的遍歷 。 ? 圖的遍歷要比樹結(jié)構(gòu)復(fù)雜的多 。 出發(fā)點(diǎn)不同 ，任一頂點(diǎn)的鄰接點(diǎn)就不相同 ， 路徑也就不同 。 ? 因?yàn)閳D中元素是 “ 多對(duì)多 ” 的關(guān)系 ， 為避免發(fā)生重復(fù) ， 設(shè)立一個(gè)輔助數(shù)組 visited[]， 每訪問一個(gè)頂點(diǎn) ， 便將其狀態(tài) visited[i]置為“ 真 ” 。 ? 常用的圖的遍歷方法有兩種： – 深度優(yōu)先遍歷法 – 廣度優(yōu)先遍歷法 深度優(yōu)先遍歷法 ? 深度優(yōu)先遍歷法類似于樹的先根遍歷法 。 ? 算法思想： – step1 從圖中某個(gè)頂點(diǎn) V0出發(fā) ， 并訪問此頂點(diǎn)； – step2 從 V0出發(fā) ， 訪問與 V0鄰接的頂點(diǎn) V1后 ， 再從 V1出發(fā) ， 訪問與 V1鄰接且未被訪問過的頂點(diǎn) V2。 重復(fù)上述過程 ， 直到不存在未訪問過的鄰接點(diǎn)為止 。 – step3 如果是連通圖 ， 從任一頂點(diǎn) V0出發(fā) ，就可以遍歷所有相鄰接的頂點(diǎn)；如果是非連通圖 ， 則再選擇一個(gè)未被訪問過的頂點(diǎn)作為出發(fā)點(diǎn) ， 重復(fù) step step2， 直到全部被訪問過的鄰接點(diǎn)都被訪問為止 。 深度優(yōu)先遍歷法舉例 遍歷過程 訪問頂點(diǎn) 所過邊 ?起始頂點(diǎn) V1 V1 ?V1的第 1個(gè)鄰接點(diǎn) V3 V3 （ V1， V3） ?V3的第 1個(gè)鄰接點(diǎn) V1已訪問，取下 一個(gè)鄰接點(diǎn) V5 V5 （ V3， V5） ?V5的第 1個(gè)鄰接點(diǎn) V3已訪問，取下 一個(gè)鄰接點(diǎn) V2 V2 （ V5， V2） ?V2的兩個(gè)鄰接點(diǎn)均被訪問， 回退到 V5， V5的鄰接點(diǎn)均被訪問， 回退到 V3， V3的鄰接點(diǎn)均被訪問 ， 回退到 V1， V1的另一個(gè)鄰接點(diǎn) V4 未被訪問 V4 （ V1， V4） ?V4的第一個(gè)鄰接點(diǎn) V1已被訪問， 另一個(gè)鄰接點(diǎn) V6未被訪問 V6 （ V4， V6） ?V6的鄰接點(diǎn)被訪問，回退到 V4 ?V4的鄰接點(diǎn)均被訪問 ?回退到 V1，返回到出發(fā)點(diǎn)，遍歷結(jié)束。 V1 V3 V5 V4 V6 G6 V2 示例 遍歷產(chǎn)生的結(jié)果 ? 深度優(yōu)先遍歷 G6所走過的序列： V1? V3 ? V5 ? V2 ? V4 ? V6 ? 所走過的邊： （ V1， V3） ， （ V3， V5） ， （ V5， V2） ， （ V1， V4） ，（ V4， V6） ? 遍歷生成樹 V1 V3 V5 V2 V4 V6 深度優(yōu)先遍歷算法程序 (非遞歸 ) Traver_dfs(struct headnode G[],int v) { int i,stack[N],visited[N], top=1 。 ARCNODE *p。 for (i=0。iN。i++) visited[I]=0。 printf(“%d ”,G[v].data)。 visited[v]=1。 top ++。 stack[top]=v。 p=G[v].firstarc。 while((top!=1)||(p!=NULL)) { while(p!=NULL) { if (visited[padjvex]) p=pnextarc。 else { printf(“%d ”,G[padjvex].data)。 visited[padjvex]=1。 top++。 stack[top]=padjvex。 p=G[padjvex].firstarc。