【正文】 長度： 路徑上邊或弧的數(shù)目。 簡單路徑： 序列中頂點 (兩端點除外 )不重復(fù)出現(xiàn)的路徑。 連通： 無向圖中從頂點 v到 v180。是連通的 。 v2 v1 v3 v4 v5 7 連通分量： 無向圖的極大連通子圖；任何連通圖的連通分量只有一個，即其本身；非連通圖有多個連通分量 (非連通圖的每一個連通部分 )。 v2 v1 v3 v4 強連通分量： 有向圖的極大強連通子圖；任何強連通圖的強連通分量只有一個，即其本身；非強連通圖有多個強連通分量。其中一個一維數(shù)組存儲數(shù)據(jù)元素 (頂點 )的信息，另一個二維數(shù)組 (圖的鄰接矩陣 )存儲數(shù)據(jù)元素之間的關(guān)系 (邊或弧 )信息。 ? 有向圖鄰接矩陣不一定對稱；有 n個頂點的有向圖需存儲空間為 n178。 ? 無向圖中頂點 vi的度 TD(vi) 是鄰接矩陣中第 i行 1的個數(shù)。 頂點 vi的 入 度 是鄰接矩陣中第 i列 1的個數(shù)。 特點： ? 若無向圖中有 n個頂點、 e條邊，則其鄰接表需 n個頂點表結(jié)點和 2e個邊表結(jié)點。 ? 無向圖中頂點 vi 的度為第 i 個單鏈表中的結(jié)點數(shù)。 圖的存儲結(jié)構(gòu)之鄰接表 (類似于樹的孩子鏈表表示法 ) 12 v2 v1 v3 v4 G1 0 1 2 3 2 ^ 1 3 ^ ^ 0 v1 v3 v4 v2 ^ 0 1 2 3 ^ 3 0 ^ ^ 2 v1 v3 v4 v2 ^ 0 鄰接表 逆鄰接表 ? 頂點 vi 的 出度 為第 i 個單鏈 表中的結(jié)點個數(shù)。 找出度易，找入度難。 ? 頂點 vi 的 入度 為第 i 個單鏈 表中的結(jié)點個數(shù)。 13 從圖的任意指定頂點出發(fā)，依照某種規(guī)則去訪問圖中所有頂點，且每個頂點僅被訪問一次，此過程叫做 圖的遍歷 。 V1 V2 V4 V5 V3 V7 V6 V8 圖的遍歷 14 方法： 從圖的某一結(jié)點出發(fā)，首先依次訪問該結(jié)點的所有鄰接頂點 Vi1, Vi2, …, V in ,再依次訪問與 Vi1, Vi2, …, Vin 相鄰接的所有未被訪問的頂點，重復(fù)此過程，直至所有頂點均被訪問為止。重復(fù)上述過程，直到全部頂點都訪問完畢 。隱式圖 ? 在路徑問題、連通性問題和網(wǎng)絡(luò)優(yōu)化等問題中， 圖的結(jié)構(gòu)是顯式給出 的，包括圖中的頂點、邊及權(quán)重，這類圖稱為顯式圖 ，即一般意義上的圖。 ? 兩種典型的隱式圖：子集樹，排列樹 17 2 顯式圖 amp。這 n個元素都在子集中或被選取記為 1，不在子集中或被舍去記為 0，這樣搜索空間為： (0,0,……,0,0), (0,0,……,0,1), (0,0,……,1,0), (0,0,……,1,1), …… (1,1,……,1,1) 。隱式圖 子集樹 ? 共 2n 個狀態(tài)。隱式圖 排列樹 ? 當(dāng)要求解的問題需要在 n個元素的 排列 中搜索問題的解時，解空間樹被稱作 排列樹 (permutation tree)。若表示為樹形就是一個 n度樹，這樣的樹有 n! 個葉結(jié)點，所以每一個遍歷樹中所有節(jié)點的算法都必須耗時 O(n! ) 20 2 顯式圖 amp。方法分類 ? 窮舉搜索（盲目搜索） 是對圖的最基本的搜索算法，是蠻力策略的一種表現(xiàn)形式。 ? 啟發(fā)式搜索 是利用一些啟發(fā)信息，提前判斷出先搜索哪些狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從而可以提前舍棄對這些狀態(tài)的嘗試。 ? 搜索分為兩大類： 隱含地檢查所有可能情況 22 3 圖搜索術(shù)語 amp。 ? 狀態(tài)空間 :由根結(jié)點到其它結(jié)點的所有路徑（分支），就確定了這個問題的狀態(tài)空間。 ? 答案狀態(tài) :是這樣一些解狀態(tài) S，對于這些解狀態(tài)而言，由根到 S的這條路徑確定了這問題的一個解（即它滿足隱式約束條件）。 23 3 圖搜索術(shù)語 amp。 ? E結(jié)點： 當(dāng)前正在生成其兒子結(jié)點的活結(jié)點叫 E結(jié)點（正在擴展的結(jié)點）。 24 3 圖搜索術(shù)語 amp。規(guī)則：皇后能吃掉同一行、同一列、同一對角線的任意棋子。 問題狀態(tài) 狀態(tài)空間 解狀態(tài) 答案狀態(tài) ● ● ● ● ● ● ● 25 二、廣度優(yōu)先搜索 ? 1 圖的廣度優(yōu)先遍歷 /搜索算法 ? 2 廣度優(yōu)先搜索的應(yīng)用 ? 例 求經(jīng)過城市最少的路線問題 ? 例 走迷宮問題 26 1 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索 ? 首先訪問出發(fā)點 V，接著依次訪問 V的所有鄰接點{Wi}，再依次訪問分別與 {Wi}鄰接的所有未曾訪問過的頂點， …… ，直至與 V相通的頂點都已訪問，若此時還有未訪問的頂點，則按相同的過程繼續(xù)。 ―先被訪問的頂點”的鄰接點先于“后被 ……‖ 被訪問 V1 V2 V4 V5 V3 V7 V6 V8 27 1 廣度優(yōu)先搜索 算法要素 ? 廣度優(yōu)先搜索：活結(jié)點的擴展是按先來先處理的原則進(jìn)行；但搜索過程中還需暫時保存部分活結(jié)點。實際應(yīng)用中，用數(shù)組或鏈表實現(xiàn)隊列。 28 2 廣度優(yōu)先搜索 算法的基本思路 ? 算法設(shè)計的基本步驟 ? 1）確定圖的存儲方式； ? 2）圖的遍歷過程中的操作，其中包括為輸出問題解而進(jìn)行的存儲操作； ? 3）輸出問題的結(jié)論。 //從頂點 v 開始的廣度優(yōu)先搜索 把頂點 v標(biāo)記為已到達(dá)頂點； 初始化隊列 Q，其中僅包含一個元素 v。 令 u 為鄰接于 w 的頂點 。 //n 為結(jié)點個數(shù) bfs(int k,graph head[]) { int i。 edgenode *p。 visited[k]=1。 //vk已訪問，將其入隊 while(!QueueEmpty(Q)) //隊非空則執(zhí)行 { i=DeQueue(Q)。 //取 vi的邊表頭指針 while(pnull) //擴展 E結(jié)點 { if(visited[padjvex]=0) //若 vj未訪問過 { print (―visit vertex‖,padjvex)。 EnQueue(Q,padjvex)。 } //找 vi的下一鄰接點 } 31 1 廣度優(yōu)先搜索 鄰接矩陣表示圖的算法 bfsm(int k, graph g[][100],int n) { int i,j。 InitQueue(Q)。 //訪問源點 vk visited[k]=1。 while(not QueueEmpty(Q)) { i=DeQueue(Q)。jGn。 visited[j]=1。} //訪問過的 vj入隊 } } 32