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