【正文】 )是 簡單路徑 ， (0,1,2,3,4,0)又是 回路 。 連通圖 :無向圖中如果任意兩個頂點之間是連通的 。 1 0 2 3 4 0和 3是 連通的 。 1 0 2 3 4 6 5 0和 6是 不連通的 。 注意極大的含義 ：如果某個連通子圖再加上一個頂點后，仍然是連通的，則它不是連通分量。 強連通分量： 有向圖的極大強連通子圖。 右圖中，頂點 0的入度和出度分別為 3和 1，頂點 0的度為 4 1 0 2 3 4 1 0 2 3 4 頂點 2的入度和出度分別為？ 頂點的度： 與該頂點相關(guān)聯(lián)的邊的數(shù)目。 有向圖中 ， 頂點的度 =入度 +出度 。 去掉一條就不連通 ， 再加上一條邊將構(gòu)成回路 。 1 0 2 3 4 圖 G1的生成樹 1 0 2 3 4 圖 G1 有根有向樹： 是一個有向圖 ， 它恰有一個頂點的入度為 0， 其余頂點的入度為 1。 網(wǎng)： 在圖的每條邊上加上一個數(shù)字稱為 權(quán) ， 也稱代價 , 帶權(quán)的圖稱為 網(wǎng) 。 自由樹： 不包含回路的連通圖 。 運算： void CreateGraph( Graph* g, int n, T noedge ) 后置條件 : 已構(gòu)造一個只有 n個結(jié)點，不包含任何邊的有向圖。 BOOL Delete( Graph *g, int u, int v) 后置條件：從圖中刪除邊 u， v，若刪除成功，則函數(shù)返回 TRUE，否則返回 FALSE。 int Vertices Graph g) 后置條件：函數(shù)返回圖中頂點數(shù)目。在以后的各小節(jié)中，我們將通過添加新運算，陸續(xù)擴充 ADT 10－ 1 的圖抽象數(shù)據(jù)類型。d, int **amp。 圖的矩陣表示法及其實現(xiàn) 圖的鄰接表表示法及其實現(xiàn) 圖的存儲結(jié)構(gòu) 圖的 矩陣表示法 鄰接矩陣 一個有 n個頂點的圖 G=(V,E)的鄰接矩陣是一個 n?n的矩陣 A，A的每個元素是 0或 1。 //兩結(jié)點間無邊時的值 (0或 ?) int Vertices。 //指向存儲鄰接矩陣的二維數(shù)組的指針 } Graph。 void CreateGraph(Graph* g, int n, T noedge ) { int i, j。 gVertices=n。 for(i=0。 i++){ gA[i]=(T*)malloc(n*sizeof(T))。 jn。 gA[i][i]=0。 return true。 if(u0 || v0 || un1 || vn1 || u==v || gA[u][v]!=gNoEdge) { printf(BadInput\n)。 } gA[u][v]=w。 } //邊的插入 0 1 3 2 0 1 2 3 0 0 0 0 0 1 1 0 1 0 2 0 0 0 1 3 1 1 0 0 1 插入 0,2邊 //邊的刪除 BOOL Delete(Graph *g, int u, int v) { int n=gVertices。 return FALSE。 return TRUE。 每個單鏈表相當(dāng)于鄰接 矩陣的一行 ,它指示了該行中的非零的元素。 頂點結(jié)點存入一個一維數(shù)組。 T W。 }ENode。 ENode** A。 邊結(jié)點的結(jié)構(gòu)類型 圖中的頂點數(shù) 01 2 3 ? 1 ? 3 ? 0 0 2 ? A 鄰接表的表頭組成一維指針數(shù)組， A是指向該數(shù)組的指針 3. 建立鄰接表 函數(shù) CreateGraph構(gòu)造一個有 n個頂點，但 不包含邊 的有向圖。 void CreateGraph(Graph* g, int n) { int i。 gA=(ENode**)malloc(n*sizeof(ENode*))。 in。 } 0 1 ... n1 ... ? ? ? 搜索、插入或刪除從頂點 u發(fā)出的邊，只在 A[u]所指向的單鏈表中操作 。 ENode* p。 if(u0 || un1) return FALSE。 pamp。pAdjVex!=v。 if (!p) return FALSE。 } //插入邊的函數(shù) BOOL Add(Graph *g, int u, int v, T w) { int n。 n=gVertices。 return FALSE。 gA[u]=p。 } 01 2 3 ? 1 ? 3 ? 0 0 2 ? p ↓ 1,3 3 0 1 3 2 插入鄰接表中由指針 A[u]所指示的單鏈表的最前面 ENode* NewENode( int vex, T weight, ENode* nextarc) { ENode* p。 pAdjVex=vex。 pNextArc=nextarc。 } //刪除邊的函數(shù) BOOL Delete(Graph *g, int u, int v) { int n=gVertices。 if(u1 amp。 un) { p=gA[u]。 while (pamp。 pAdjVex!=v){ q=p。 } if (p) { if (q) qNextArc=pNextArc。 free(p)。 } } printf(BadInput\n)。 } 01 2 3 ? 1 ? 3 ? 0 0 2 ? 0 1 3 2 3 1,3 P ↓ q=NULL 在由指針 A[u]所指示的單鏈表中，搜索 AdjVex域的值為 v的邊結(jié)點 圖的遍歷 圖的遍歷 : 指從圖 G的任意一個頂點 v出發(fā)，訪問圖中所有結(jié)點且每個結(jié)點僅訪問一次的過程。 為了避免發(fā)生上述兩種情況 ， 圖的搜索算法通常為圖的每個頂點保留一個標(biāo)志位 (mark bit)。 在遍歷過程中 ， 當(dāng)某個頂點被訪問時 ， 其標(biāo)志位被標(biāo)記 。 搜索結(jié)束后 ， 如果還有未標(biāo)記過的頂點 ， 遍歷算法可以選一個未標(biāo)記的頂點 ， 從它出發(fā)開始繼續(xù)搜索 。 依次從 v的未訪問過的鄰接點出發(fā)，深度優(yōu)先搜索 圖 G. 從 A出發(fā) 將訪問走過的邊保留，去掉訪問時未走過的邊，就得到以 A為根的 DFS生成樹。 一條無向邊被視作兩條有向邊，被查看兩次。 另選一個頂點出發(fā)搜索圖 G的其余部分 。 DFS遞歸算法（ 【 程序 10－ 5】 ） 。 visited[v]=TRUE。 for ( w=[v]。 w=wNextArc) if (!visited[wAdjVex] ) DFS(g, wAdjVex, visited)。 int i, n=。 in。 for (i=0。 i++) if (!visited[i]) DFS(g, i, visited)。 n個頂點、 e條邊的圖采用鄰接表存儲， DFS算法的時間為 O(n+e),而采用鄰接矩陣表示，時間為 O(n2)。 2 依次訪問頂點 v的未訪問的鄰接點，再訪問與這些 鄰接點相鄰接且未訪問的頂點。 寬度優(yōu)先搜索 寬度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批