【正文】 ?無向完全圖 ——n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是 n(n1)/2 ?路徑 ——有向圖 G=(V,E)中，若存在一個(gè)頂點(diǎn)序列vp,vi1,vi2,…vin,vq ，使得 vp,vi1,vi1,vi2 ,…,vin,vq均是圖中的邊，則稱此序列是從頂點(diǎn) vp到 vq一條 路徑。 ?路徑長(zhǎng)度 ——該路徑上經(jīng)過邊的數(shù)目。 ?回路 ——一條路徑第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的 叫 ~ ?簡(jiǎn)單路徑 ——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫 ~ ?簡(jiǎn)單回路 ——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫 ~ ?有根圖 ——若存在一個(gè)頂點(diǎn) v，從該頂點(diǎn)到其余各個(gè)頂點(diǎn)都有路徑，則稱此圖為有根圖 ?連通 ——從頂點(diǎn) x到頂點(diǎn) y有一條路徑，則說 x和 y是連通的 ?連通圖 ——圖中任意兩個(gè)頂點(diǎn)都是連通的叫連通圖 ?連通分量 ——無向圖 G的極大連通子圖稱為 G的連通分量 ?強(qiáng)連通圖 ——若 G中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱圖 G是強(qiáng)連通圖 ?強(qiáng)連通分量 ——有向圖 G的極大強(qiáng)連通子圖稱為 G的強(qiáng)連通分量 ?權(quán) ——與圖的邊相關(guān)的數(shù) 值 叫 權(quán)值。 ?網(wǎng)絡(luò) ——邊上帶權(quán)的圖稱為網(wǎng)絡(luò) v1v2v3（ a ） （ b ） （ c ）v1v2v3v1v2v3G1例圖 與 子 圖v2v3有 向 完 全 圖v1v2v3v1無 向 完 全 圖例v1v2v3v4v5路 徑 ： v 1 ， v 2 ， v 4 ， v 3 ， v 1路 徑 長(zhǎng) 度 ： 4簡(jiǎn) 單 路 徑 ： v 1 ， v 2 ， v 4回 路 ： v 3 ， v 5 ， v 4 ， v 3 ， v 1 ， v 2 ， v 4簡(jiǎn) 單 回 路 ： v 3 ， v 5 ， v 4 ， v 3例v1v2v3v4v1v2v3例例頂 點(diǎn)v 1的 度 為3定 點(diǎn)v 4的 度 為2頂 點(diǎn)v 2的 出 度 為2， 入 度 為1， 度 為3v1v2v3v4v5例一 個(gè) 連 通 圖v1v2v3一 個(gè) 強(qiáng) 連 通 圖例v1v5v4v3v2v7v6（ a ） （ b ）G5v1v5v4v3v2v7v6例 非 連 通 圖 G5 和 它 的 兩 個(gè) 連 通 分 量 圖的存儲(chǔ)結(jié)構(gòu) ?鄰接矩陣 ——表示頂點(diǎn)之間鄰接關(guān)系的矩陣 ?設(shè) G=(V,E）是具有 n個(gè)頂點(diǎn)的圖，則 G的 鄰接矩陣 是一個(gè) n階方陣 A， A中元素的值 aij可以定義為： 1 : vi, vj 或 ( vi, vj) 是 E 中 的 邊0 : vi, vj 或 ( vi, vj) 不 是 E 中 的 邊ai j = A BDCv4v3v2v5v1（ a ） （ b ）A2=0 1 1 11 0 0 11 0 0 11 1 1 0A1=0 1 0 0 10 0 1 0 00 1 0 0 00 1 1 0 00 0 0 1 0ADCB01234r2v4v3v2012345v5v1數(shù) 組數(shù) 組r1?特點(diǎn)： ?無向圖的鄰接矩陣對(duì)稱；有 n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為 n178。 有向圖鄰接矩陣不一定對(duì)稱；有 n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為 n178。 ?無向圖中頂點(diǎn) Vi的度是鄰接矩陣 A中第 i行元素之和 ?有向圖中， ?頂點(diǎn) Vi的出度是 A中第 i行元素之和 ?頂點(diǎn) Vi的入度是 A中第 i列元素之和 ?網(wǎng)的鄰接矩陣可定義為： Wi j : i ≠ j 且 vi, vj 或 ( vi, vj) 是 E 中 的 邊0 : i = j∞ : i ≠ j 且 vi, vj 或 ( vi, vj) 不 是 E 中 的 邊ai j = A3=03∞423065∞2∞310∞605345501例v1v5v4v3v212554363網(wǎng) 絡(luò) 及 其 鄰 接 矩 陣可以得到鄰接矩陣存儲(chǔ)結(jié)構(gòu) C語言描述如下： define n 5 /* 圖的頂點(diǎn)數(shù) */ define e 6 /* 圖的邊數(shù) */ define max 10000 /* 設(shè)置一個(gè)極大數(shù)無窮大 */ typedef char vextype。 /* 頂點(diǎn)類型 */ typedef int adjtype。 /* 權(quán)值類型 */ typedef struct { vextype vertex[n+1]。 /* 頂點(diǎn)數(shù)組 */ adjtype edge[n+1][n+1]。 /* 鄰接矩陣 */ }adj_matrix。 ?鄰接表 ?鄰接表法 (Adjacency List)是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 頂點(diǎn)采用順序方式進(jìn)行存儲(chǔ)， 用 n個(gè)單鏈表來存儲(chǔ)圖中的邊，第 i個(gè)單鏈表是所有與第 i個(gè)頂點(diǎn)相關(guān)聯(lián)的邊鏈接而成的，稱此單鏈表為第 i個(gè)頂點(diǎn)的 邊表 ，邊表中的每個(gè)結(jié)點(diǎn)稱為 邊表結(jié)點(diǎn) 。 在頂點(diǎn)的順序表中，每個(gè)元素增加一個(gè)指針域用來存放各個(gè)邊表的頭指針，稱此順序表為 頂點(diǎn)表 ，而順序表中的每個(gè)元素稱為 頂點(diǎn)表結(jié)點(diǎn) 。 頂點(diǎn)表和各頂點(diǎn)的邊表一起組成圖的鄰接表。 a d j v e x n e x t l i n kv e r t e x邊 表 結(jié) 點(diǎn) 頂 點(diǎn) 表 結(jié) 點(diǎn)鄰接表存儲(chǔ)結(jié)構(gòu) C語言描述如下： typedef struct node { int adjvex。 /* 鄰接點(diǎn)域 */ struct node *next。 /* 指針域 */ }edgenode。 /* 定義邊表結(jié)點(diǎn) */ typedef struct { vextype vertex。 /* 頂點(diǎn)域 */ edgenode *link。 /* 指針域 */ }vexnode。 /* 定義頂點(diǎn)表結(jié)點(diǎn) */ vexnode adjlist[n+1]。 v2v3v4v12 5 ^012345v e r t e x l i n ka d j v e x n e x t3 ^2 ^2 3 ^頂 點(diǎn) 表 出 邊 表v54 ^v4v3v2v5v1例有 向 圖 及 其 鄰 接 表A BDC例BCDA2 3 4 ^01234v e r t e x l i n ka d j v e x n e x t1 4 ^1 4 ^1頂 點(diǎn) 表邊 表2 3 ^無 向 圖 及 其 鄰 接 表?特點(diǎn) ?無向圖中頂點(diǎn) Vi的度為第 i個(gè)單鏈表中的結(jié)點(diǎn)數(shù) ?有向圖中 ?頂點(diǎn) Vi的出度為第 i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù) ?頂點(diǎn) Vi的入度為整個(gè) 單鏈表中鄰接點(diǎn)域值是 i的結(jié)點(diǎn)個(gè)數(shù) ?逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以 Vi終點(diǎn)的單鏈表 v4v3v2v5v1例v2v3v4v1^1 3012345v e r t e x l i n ka d j v e x n e x t4 ^254 ^頂 點(diǎn) 表 入 邊 表v51 ^有 向 圖 及 其 逆 鄰 接 表邊集數(shù)組 (edgeset array)是圖的一種順序存儲(chǔ)方式，利用一維數(shù)組來存儲(chǔ)圖中所有的邊，數(shù)組中的每個(gè)元素用來存儲(chǔ)圖中的一條邊，包括：始點(diǎn)、終點(diǎn)的序號(hào)及權(quán)值，該數(shù)組中所含元素的個(gè)數(shù)要大于等于圖中邊的條數(shù)。 ?邊集數(shù)組 ?鄰接表法 (Adjacency List)是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1 12 35 62 23 41 0 32 35 48 63 45 51 8 1 20 1 2 3 4 5 6 7 8起 點(diǎn)終 點(diǎn)權(quán) 值（ b ）v1v2v5v4v3（ a ）581 231 861 06typedef struct edge { int fromvex。 /* 邊的始點(diǎn)域 */ int endvex。 /* 邊的終點(diǎn)域 */ int weight。 /* 邊的權(quán)值域 */ }edgeset。 /* 定義邊集數(shù)組類型 */ edgeset ge[e+1]。 /* 邊集數(shù)組全局量 */ 有 向 圖 及 其 邊 集 數(shù) 組167。 圖的遍歷 ?深度優(yōu)先遍歷 (DFS) ?方法：對(duì)于給定的圖 G，假設(shè)初始時(shí)所有頂點(diǎn)均未被訪問過，則可從 G中任選一頂點(diǎn) vi做為初始出發(fā)點(diǎn)，深度優(yōu)先搜索可定義為：訪問出發(fā)點(diǎn) vi，置訪問標(biāo)記為 1，然后依次從 vi的未被訪問過的鄰接點(diǎn) vj出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有和 vi有路徑相通的頂點(diǎn)均被訪問過。很顯然圖的深度優(yōu)先搜索過程是遞歸的。它的特點(diǎn)是盡可能先對(duì)圖從縱深方向進(jìn)行搜索，故稱為深度優(yōu)先搜索。 DFS序列為： v1， v2， v4， v8， v5， v3， v6， v7。 v4v1v2v5v8v6v3v7?深度優(yōu)先遍歷算法 ?遞歸算法 void DFS(int i) { int j。 printf (輸出序號(hào)為 %d的頂點(diǎn) : %c\n,i,adjvertex[i])。 visited[i]=1。 /* 標(biāo)記 vi已經(jīng)訪問過 */ for (j=1。j=n。j++) /* 依次搜索 vi的鄰接點(diǎn) */ if((adjedge[i][j])amp。amp。(!visited[j])) DFS(j)。} v4v1v2v5v8v6v3v70 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 0 0 1 1 00 1 0 0 0 0 0 10 1 0 0 0 0 0 10 0 1 0 0 0 1 00 0 1 0 0 1 0 00 0 0 1 1 0 0 0void DFSL(int i) { edgenode *p。 printf(輸出序號(hào)為 %d的頂點(diǎn) : %c\n,i,adjlist[i].vertex)。 visited [i]=1。 /* 標(biāo)記 vi已經(jīng)訪問過 */ p=adjlist[i].link。 /* p為 vi的邊表頭指針 */ while (p) /* 依次搜索 vi的鄰接點(diǎn) */ { if(!visited[padjvex]) DFSL(padjvex)。 p=pnext。 } } v4v1v2v5v8v6v3v73 2 7 68 2 6 3 012345678v e r t e x l i n ka d j v e x n e x tv1 v2 v3 v4 v5 v6 v7 v8