【正文】 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 20 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。 // 在 G中增添弧 v,w，若 G是無向的，則還增添對稱弧 w,v。G) // 銷毀圖 結構的建立和銷毀 對頂點的訪問操作 LocateVex(G, u) // 若 G中存在頂點 u，則返回該頂點在圖中 “ 位置 ” ，否則返回其它信息。通常邊數(shù)遠少于 nlogn 邊很多的圖。 證明： 若是有向完全圖，則 n個頂點中的每個頂點都有一條弧指向其它 n1個頂點 , 因此總邊數(shù) =n(n1) 1 2 3 4 6 證明： 從①可以直接推論出無向完全圖的邊數(shù) ——因為無方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為 n(n1)/2。 B A C D F E B A C D F E 強連通圖： 在有向圖中 , 每一對頂點 vi和 vj, 都存在一條從 vi到 vj和從 vj到vi的路徑 強連通分量： 非強連通圖中的極大強連通子圖。 //在圖 G中增添新頂點 v。 例 1： 鄰接矩陣： = （ v1 v2 v3 v4 v5 ） v1 v2 v3 v4 v5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 頂點表： 無向圖的鄰接矩陣如何表示？ v1 v2 v3 v5 v4 A 18 例 2 ：有向圖的鄰接矩陣如何表示？ 分析 1： 有向圖的鄰接矩陣可能是不對稱的。 // 頂點向量 AdjMatrix arcs。 ② 鄰接矩陣的空間復雜度為 O(n2),而鄰接表的空間復雜度為 O(n+e)。 tailvex headvex hlink tlink 弧結點 data firstin firstout 頂點結點 ∧ ∧ ∧ A,B C,A C,B A,C 33 這是 無向圖 的另一種鏈式存儲結構，當對邊操作時建議采用此種結構存儲。 思路： 將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。若是稀疏圖，則比鄰接矩陣表示法合適。 //對無權圖 ,用 1或 0表示相鄰否；對帶權圖，則為權值類型 。 //從頂點 v起廣度優(yōu)先遍歷圖 G，并對每個頂點調(diào)用函數(shù) Visit一次且僅一次。 //返回 v的（相對于 w的） “下一個鄰接點 ” 。 A B E C F 如 :從 A到 F長度為 3 的路徑{A,B,C,F}或 {A， E， C， F} 簡單路徑 :指序列中頂點不重復出現(xiàn)的路徑。 P(v,w) 定義了弧 v,w的意義或信息。 頂點 v的度： 是和 v 相關聯(lián)的邊的數(shù)目 ,記為 TD(v). 頂點 v的出度 : 以頂點 v 為尾的弧的數(shù)目 。 結構的建立和銷毀 插入或刪除頂點 對鄰接點的操作 遍歷 插入或刪除弧 基本操作 對頂點的訪問操作 13 對鄰接點的操作 FirstAdjVex(G, v)。 DFSTraverse(G, v, Visit())。 圖的鄰接矩陣在機內(nèi)如何表示？ （參見教材 P161） 注： 用兩個數(shù)組分別存儲頂點表和鄰接矩陣 define INFINITY INT_MAX //最大值 ∞ define MAX_VERTEX_NUM 20 //假設的最大頂點數(shù) typedef enum {DG, DN, UDG,UDN } GraphKind。 80 64 1 2 5 當鄰接表的存儲結構形成后，圖便唯一確定！ 26 分析 1： 對于 n個頂點 e條邊的