第七章圖
圖的概念
圖G是由頂點集V和邊集E組成頂點集是有窮非空集邊集是有窮集;
G中每條邊都有方向稱有向圖;有向邊稱弧;邊的始點稱弧尾;邊的終點稱弧頭;G中每條邊都沒有方向的稱無向圖
頂點n與邊數e的關系無向圖的邊數e介於~n(n)/之間有n(n)/條邊的稱無向完全圖;
有向圖的邊數e介於~n(n)之間有n(n)條邊的稱有向完全圖;
無向圖中頂點的度是關聯與頂點的邊數;有向圖中頂點的度是入度與出度的和
所有圖均滿足所有頂點的度數和的一半為邊數
圖G(VE)如V是V的子集E是E的子集且E中關聯的頂點均在V中則G(VE)是G的子圖
在有向圖中從頂點出發都有路徑到達其它頂點的圖稱有根圖;
在無向圖中任意兩個頂點都有路徑連通稱連通圖;極大連通子圖稱連通分量;
在有向圖中任意順序兩個頂點都有路徑連通稱強連通圖;極大連通子圖稱強連通分量;
將圖中每條邊賦上權則稱帶權圖為網絡
圖的存儲結構
鄰接矩陣表示法
鄰接矩陣是表示頂點間相鄰關系的矩陣n個頂點就是n階方陣
無向圖是對稱矩陣;有向圖行是出度列是入度
鄰接表表示法
對圖中所有頂點把與該頂點相鄰接的頂點組成一個單鏈表稱為鄰接表adjvex|next如要保存頂點信息加入data;
對所有頂點設立頭結點vertex|firstedge並順序存儲在一個向量中;vertex保存頂點信息firstedge保存鄰接表頭指針
鄰接矩陣表示法與鄰接表表示法的比較
) 鄰接矩陣是唯一的鄰接表不唯一;
) 存儲稀疏圖用鄰接表存儲稠密圖用鄰接矩陣;
) 求無向圖頂點的度都容易求有向圖頂點的度鄰接矩陣較方便;
) 判斷是否是圖中的邊鄰接矩陣容易鄰接表最壞時間為O(n);
) 求邊數e鄰接矩陣耗時為O(n^)與e無關鄰接表的耗時為O(e+n);
圖的遍歷
圖的深度優先遍歷
圖的深度優先遍歷類似與樹的前序遍歷按訪問頂點次序得到的序列稱DFS序列
對鄰接表表示的圖深度遍歷稱DFS時間復雜度為O(n+e); 對鄰接矩陣表示的圖深度遍歷稱DFSM時間復雜度為O(n^);
圖的廣度優先遍歷
圖的廣度優先遍歷類似與樹的層次遍歷按訪問頂點次序得到的序列稱BFS序列
對鄰接表表示的圖廣度遍歷稱BFS時間復雜度為O(n+e); 對鄰接矩陣表示的圖廣度遍歷稱BFSM時間復雜度為O(n^);
生成樹和最小生成樹
將沒有回路的連通圖定義為樹稱自由樹
生成樹
連通圖G的一個子圖若是一棵包含G中所有頂點的樹該子圖稱生成樹
有DFS生成樹和BFS生成樹BFS生成樹的高度最小
非連通圖生成的是森林
最小生成樹
將權最小的生成樹稱最小生成樹(是無向圖的算法)
普裡姆算法
) 確定頂點S初始化候選邊集T[~n];formvex|tovex|lenght
) 選權值最小的T[i]與第條記錄交換;
) 從T[]中將tovex取出替換以下記錄的fromvex計算權;若權小則替換否則不變;
) 選權值最小的T[i]與第條記錄交換;
) 從T[]中將tovex取出替換以下記錄的fromvex計算權;若權小則替換否則不變;
) 重復n次
初始化時間是O(n)選輕邊的循環執行nk次調整輕邊的循環執行nk;算法的時間復雜度為O(n^)適合於稠密圖
克魯斯卡爾算法
) 初始化確定頂點集和空邊集;對原邊集按權值遞增順序排序;
) 取第條邊判斷邊的個頂點是不同的樹加入空邊集否則刪除;
) 重復e次
對邊的排序時間是O(eloge);初始化時間為O(n);執行時間是O(loge);算法的時間復雜度為O(eloge)適合於稀疏圖
最短路徑
路徑的開始頂點稱源點路徑的最後一個頂點稱終點;
單源最短路徑問題已知有向帶權圖求從某個源點出發到其余各個頂點的最短路徑;
單目標最短路徑問題將圖中每條邊反向轉換為單源最短路徑問題;
單頂點對間最短路徑問題以分別對不同頂點轉換為單源最短路徑問題;
所有頂點對間最短路徑問題分別對圖中不同頂點對轉換為單源最短路徑問題;
迪傑斯特拉算法
) 初始化頂點集S[i]路徑權集D[i]前趨集P[i];
) 設置S[s]為真D[s]為;
) 選取D[i]最小的頂點加入頂點集;
) 計算非頂點集中頂點的路徑權集;
) 重復)n次
算法的時間復雜度為O(n^)
拓撲排序
對一個有向無環圖進行拓撲排序是將圖中所有頂點排成一個線性序列滿足弧尾在弧頭之前這樣的線性序列稱拓撲序列
無前趨的頂點優先
總是選擇入度為的結點輸出並刪除該頂點的所有邊設置各個頂點入度時間是O(n+e)設置棧或隊列的時間是O(n)算法時間復雜度為O(n+e)
無後繼的頂點優先
總是選擇出度為的結點輸出並刪除該頂點的所有邊設置各個頂點出度時間是O(n+e)設置棧或隊列的時間是O(n)算法時間復雜度為O(n+e)求得的是逆拓撲序列
附二:
第七章圖
*************************************************************************************
圖的邏輯結構特征就是其結點(頂點)的前趨和後繼的個數都是沒有限制的即任意兩個結點之間之間都可能相關
圖GraphG=(VE)V是頂點的有窮非空集合E是頂點偶對的有窮集
有向圖Digraph每條邊有方向;無向圖Undigraph每條邊沒有方向
有向完全圖具有n*(n)條邊的有向圖;無向完全圖具有n*(n)/條邊的無向圖;
有根圖有一個頂點有路徑到達其它頂點的有向圖;簡單路徑是經過頂點不同的路徑;簡單回路是開始和終端重合的簡單路徑;
網絡是帶權的圖
*************************************************************************************
圖的存儲結構·鄰接矩陣表示法用一個n階方陣來表示圖的結構是唯一的適合稠密圖 ·無向圖鄰接矩陣是對稱的
·有向圖行是出度列是入度
建立鄰接矩陣算法的時間是O(n+n^+e)其時間復雜度為O(n^)
·鄰接表表示法用頂點表和鄰接表構成不是唯一的適合稀疏圖·頂點表結構 vertex | firstedge指針域存放鄰接表頭指針
·鄰接表用頭指針確定 ·無向圖稱邊表;
·有向圖又分出邊表和逆鄰接表;
·鄰接表結點結構為 adjvex | next
時間復雜度為O(n+e)空間復雜度為O(n+e)
圖的遍歷 ·深度優先遍歷借助於鄰接矩陣的列使用棧保存已訪問結點
·廣度優先遍歷借助於鄰接矩陣的行使用隊列保存已訪問結點
*************************************************************************************
生成樹的定義若從圖的某個頂點出發可以系統地訪問到圖中所有頂點則遍歷時經過的邊和圖的所有頂點所構成的子圖稱作該圖的生成樹
最小生成樹圖的生成樹不唯一從不同的頂點出發可得到不同的生成樹把權值最小的生成樹稱為最小生成樹(MST)
構造最小生成樹的算法 ·Prim算法的時間復雜度為O(n^)與邊數無關適於稠密圖
·Kruskal算法的時間復雜度為O(lge)主要取決於邊數較適合於稀疏圖
*************************************************************************************
最短路徑的算法·Dijkstra算法時間復雜度為O(n^)·類似於prim算法
*************************************************************************************
拓撲排序是將有向無環圖G中所有頂點排成一個線性序列若∈E(G)則在線性序列u在v之前這種線性序列稱為拓撲序列
拓撲排序也有兩種方法·無前趨的頂點優先每次輸出一個無前趨的結點並刪去此結點及其出邊最後得到的序列即拓撲序列
·無後繼的結點優先每次輸出一個無後繼的結點並刪去此結點及其入邊最後得到的序列是逆拓撲序列
From:http://tw.wingwit.com/Article/program/sjjg/201311/23751.html
