【正文】 第 7章 圖 圖是一種非線性結(jié)構(gòu) ,結(jié)構(gòu)較復(fù)雜 ,數(shù)據(jù)元素之間的關(guān)系是任意的。它可應(yīng)用到電子線路分析、系統(tǒng)工程、人工智能等。 167。 圖的定義和術(shù)語 ?圖的抽象數(shù)據(jù)類型 :P156~157 ?圖的定義 ?圖 (Graph)—— 圖 G是由兩個集合 V(G)和 E(G)組成的 ,記為 G=(V,E) 其中： V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的 無序 對 或有序?qū)? ?零圖：只有頂點(diǎn)沒有邊， E（ G）為空集 ?有向圖 —— 有向圖 G是由兩個集合 V(G)和 E(G)組成的 其中： V(G)是頂點(diǎn)的非空有限集 E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c(diǎn)的有序?qū)?，記?v,w， v,w是頂點(diǎn)， v為弧尾， w為弧頭 ?無向圖 —— 無向圖 G是由兩個集合 V(G)和 E(G)組成的 其中： V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記為?v,w） 或（ w,v)， 并且（ v,w)=(w,v) 例 2 4 5 1 3 6 G1 圖 G1中： V(G1)={1,2,3,4,5,6} E(G1)={1,2, 2,1, 2,3, 2,4, 3,5, 5,6, 6,3} 例 1 5 7 3 2 4 G2 6 圖 G2中： V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)} ?圖的基本術(shù)語 ?完全圖： n個頂點(diǎn)的圖中，每個頂點(diǎn)與其它 n1個頂點(diǎn)都有邊 ?有向完全圖 —— n個頂點(diǎn)的有向圖最大邊數(shù)是 n(n1) ?無向完 全 圖 —— n個頂點(diǎn)的無向圖最大邊數(shù)是 n(n1)/2 ?權(quán) —— 與圖的邊或弧相關(guān)的數(shù)叫 ~ ?網(wǎng) —— 帶權(quán)的圖叫 ~ ?子圖 —— 如果圖 G(V,E)和圖 G‘(V’,E‘),滿足： ?V’?V ?E’?E 則稱 G‘為 G的子圖 ?頂點(diǎn)的度 ?無向圖中，頂點(diǎn)的度為與每個頂點(diǎn)相連的邊數(shù) ?有向圖中，頂點(diǎn)的度分成入度與出度 ?入度：以該頂點(diǎn)為頭的弧的數(shù)目 ?出度：以該頂點(diǎn)為尾的弧的數(shù)目 ?路徑 —— 路徑是頂點(diǎn)的序列 V={Vi0,Vi1,……V in}， 滿足 (Vij1,Vij)?E 或 Vij1,Vij?E,(1j?n) ?路徑長度 —— 沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和 ?回路 —— 第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑叫 ~ ?簡單路徑 —— 序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫 ~ ?簡單回路 —— 除了第一個頂點(diǎn)和最后一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫 ~ ?連通 —— 從頂點(diǎn) V到頂點(diǎn) W有一條路徑，則說 V和 W是連通的 ?連通圖 —— 圖中任意兩個頂點(diǎn)都是連通的叫 ~ ?連通分量 —— 非連通圖的每一個連通部分叫 ~ (P159 圖 ) ?強(qiáng)連通圖 —— 有向圖中，如果對每一對 Vi,Vj?V, Vi?Vj,從Vi到 Vj 和從 Vj到 Vi都存在路徑，則稱 G是 ~ P159圖 V2是自身對自身的強(qiáng)連通分量 例 2 1 3 2 1 3 有向完全圖 無向完全圖 3 5 6 例 2 4 5 1 3 6 圖與子圖 例 2 4 5 1 3 6 G1 頂點(diǎn) 2入度： 1 出度： 3 頂點(diǎn) 4入度： 1 出度： 0 例 1 5 7 3 2 4 G2 6 頂點(diǎn) 5的度： 3 頂點(diǎn) 2的度： 4 例 1 5 7 3 2 4 G2 6 例 2 4 5 1 3 6 G1 路徑： 1， 2， 3， 5， 6， 3 路徑長度： 5 簡單路徑： 1， 2， 3， 5 回路： 1， 2， 3， 5， 6， 3， 1 簡單回路： 3， 5， 6， 3 路徑： 1， 2， 5， 7， 6， 5， 2， 3 路徑長度： 7 簡單路徑： 1， 2， 5， 7， 6 回路： 1， 2， 5， 7， 6， 5， 2， 1 簡單回路： 1， 2， 3， 1 連通圖 例 2 4 5 1 3 6 強(qiáng)連通圖 3 5 6 例 非連通圖 連通分量 例 2 4 5 1 3 6 ?有向樹 :一個有向圖若只有一個頂點(diǎn)的入度為 0, 其余頂點(diǎn)的入度都為 1,則該圖稱為一棵有向樹 . ?生成森林 :由若干棵有向樹組成 ,含圖中全部頂點(diǎn) ,這些頂點(diǎn)構(gòu)成若干棵互不相交的有向樹的弧 . P160圖 167。 圖的存儲結(jié)構(gòu) ?多重鏈表 (P160) 例 G1 2 4 1 3 例 1 5 3 2 4 G2 V1 V2 ^ ^ V4 ^ V3 ^ ^ V1 V2 V4 ^ V5 ^ V3 ?數(shù)組表示法 —— 表示頂點(diǎn)間相聯(lián)關(guān)系的鄰接矩陣 ?定義： 設(shè) G=(V,E)是有 n?1個頂點(diǎn)的圖， G的鄰接矩陣 A是具有以下性質(zhì)的 n階方陣 ????? ????，其它0E (G )v,v或)v,(v若1,],[ jijijiA例 G1 2 4 1 3 例 1 5 3 2 4 G2 ??????????????????0011000101110101010101010? ? ? ? ? ? ? ? ? ? ??????????????0001100000000110? ? ? ? ? ? ? ? ?特點(diǎn)： ?無向圖的鄰接矩陣對稱，可壓縮存儲；有 n個頂點(diǎn)的無向圖需存儲空間為 n(n+1)/2 ?有向圖鄰接矩陣不一定對稱；有 n個頂點(diǎn)的有向圖需存儲空間為 n178。 ?無向圖中頂點(diǎn) Vi的度 TD(Vi)是鄰接矩陣 A中第 i行 (或第 i列 )元素之和 ?有向圖中， ?頂點(diǎn) Vi的出度 OD(vi)是 A中第 i行元素之和 ?頂點(diǎn) Vi的入度 ID(vi)是 A中第 i列元素之和 ?網(wǎng)絡(luò)的鄰接矩陣可定義為： ????????，其它或0E ( G )v,v或)v,(v若,],[ jijiijjiA ???????????????????0618360240120228400530750? ? ? ? ? ? ? ? ? ? 例 1 4 5 2 3 7 5 3 1 8 6 4 2 P162圖 ?關(guān)聯(lián)矩陣 —— 表示頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系的矩陣 ?定義： 設(shè) G=(V,E)是有 n?1個頂點(diǎn)， e?0條邊的圖， G的關(guān)聯(lián)矩陣 A是具有以下性質(zhì)的 n?e階矩陣 ???????為頭邊相連，且頂點(diǎn)與邊不相連頂點(diǎn)與為尾邊相連，且頂點(diǎn)與有向圖：ijijiijijiA,1,0,1],[????邊不相連頂點(diǎn)與，邊相連頂點(diǎn)與，無向圖：jijijiA01],[??????????????????1100011000011011? ? ? ? 4 3 2 1 例 G1 2 4 1 3 1 2 3 4 例 1 5 3 2 4 G2 1 2 3 4 5 6 ? ? ? ? ? ??????????????????1100000001100111001010010000114 3 2 1 5 6 例 B D A C 1 2 3 4 5 6 A B C D 4 3 2 1 5 6 ????????????????????101011110000011100000111?特點(diǎn) ?關(guān)聯(lián)矩陣每列只有兩個非零元素 ，是稀疏矩陣； n越大，零元素比率越大 ?無向圖中頂點(diǎn) Vi的度 TD(Vi)是關(guān)聯(lián)矩陣 A中第 i行元素之和 ?有向圖中， ?頂點(diǎn) Vi的出度是 A中第 i行中“ 1”的個數(shù) ?頂點(diǎn) Vi的入度是 A中第 i行中“ 1”的個數(shù) ?鄰接表 ?實(shí)現(xiàn)：為圖中每個頂點(diǎn)建立一個單鏈表，第 i個單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn) Vi的邊 ?有向圖中指以 Vi為尾的弧 ,即頂點(diǎn) vi的出度 typedef struct node { int adjvex。 //鄰接點(diǎn)域，存放與 Vi鄰接的點(diǎn)在表頭數(shù)組中的位置 struct node *next。 //鏈域，指示下一條邊或弧 }JD。 adjvex next 表頭結(jié)點(diǎn)： typedef struct tnode { int vexdata。 //存放頂點(diǎn)信息 struct node *firstarc。 //指示第一個鄰接點(diǎn) }TD。 TD ga[M]。 //ga[0]不用 vexdata firstarc 例 G1 b d a c 例 a e c b d G2 1 2 3 4 a c d b vexdata firstarc 3 2 4 1 ^ ^ ^ ^ adjvex next 1 2 3 4 a c d b vexdata firstarc 4 2 1 2 ^ ^ ^ adjvex next 5 e 4 3 5 ^ 1 5 3 2 3 ^ ?特點(diǎn) ?無向圖中頂點(diǎn) Vi的度為第 i個單鏈表中的結(jié)點(diǎn)數(shù) ?有向圖中 ?頂點(diǎn) Vi的出度為第 i個單鏈表中的結(jié)點(diǎn)個數(shù) ?頂點(diǎn) Vi的入度為整個 單鏈表中鄰接點(diǎn)域值是 i的結(jié)點(diǎn)個數(shù) ?逆鄰接表：有向圖中對每個結(jié)點(diǎn)建立以 Vi為頭的弧的單鏈表 逆鄰接表 : 例 G1 b d a c 1 2 3 4 a c d b vexdata firstarc 4 1 ^ 1 ^ ^ 3 ^ adjvex next ?有向圖的十字鏈表表示法 弧結(jié)點(diǎn)： typedef struct arode { int tailvex, headvex。 //弧尾、弧頭在表頭數(shù)組中位置 struct arode *hlink； //指向弧頭相同的下一條弧 struct arode *tlink。 //指向弧尾相同的下一條弧 }AD。 tailvex headvex hlink tlink 頂點(diǎn)結(jié)點(diǎn)： typedef struct dnode { int data。 //存與頂點(diǎn)有關(guān)信息 struct arode *firstin； //指向以該頂點(diǎn)為弧頭的第一個弧結(jié)點(diǎn) struct arode