圖的基本概念
首先，你要明確圖是什么樣子的，就是下面這個樣子的
圖的定義與術語
有向圖和無向圖
直接對比圖就可以看出來，有向圖和無向圖的區別了，這個沒有什么難的，
有向圖和無向圖的表示法有略微的區別，注意看
G1有箭頭，有向圖，表示方法是 V={V~0~，V~1~，V~2~，V~3~} E = {<V~0~，V~1~>，<V~1~，V~2~>，<V~1~，V~0~>，<V~2~，V~0~>，<V~2~，V~3~>}
G2無箭頭，無向圖，表示方法是 V={V~0~，V~1~，V~2~，V~3~} E = {(V~0~，V~1~)，(V~1~，V~2~)，(V~0~，V~2~)，(V~2~，V~3~)}
弧、弧頭、弧尾：有向圖的邊稱為弧，無向圖叫做邊，有序偶對<v，w>表示有向圖從v到w的一潭訓，v稱為弧尾或始點，w稱為弧頭或終點，
任何兩點之間都有邊的無向圖稱為無向完全圖，
任何兩點之間都有弧的有向圖稱為有向完全圖，
權、帶權圖：圖的邊附帶數值，這個數值叫權，每條邊都帶權的圖稱為帶權圖，
頂點的度、入度、出度：
- 無向圖中頂點v的度是與該頂點相關聯的邊的數目，記為D(v)，
- 有向圖中，把以頂點v為終點的弧的數目稱為v的入度，記為ID(v)；把以頂點v為始點的弧的數目稱為v的出度，記為OD(v)，有向圖頂點v的度為入度和出度之和，即D（v） = ID（v）+ OD（v），
簡單路徑、回路、簡單回路：序列中頂點不重復出現的路徑稱為簡單路徑，第一個頂點和最后一個頂點相同的路徑稱為回路，除了第一個頂點和最后一個頂點外，其余頂點不重復的回路，稱為簡單回路或簡單環，
下面還有一些需要了解的術語
連通、連通圖、連通分量、極大連通子圖、強連通、強連通圖、強連通分量、生成樹、生成森林
如果精力足夠，都看看吧
圖的存盤結構
圖的存盤結構有很多中，例如 鄰接矩陣、鄰接表、十字鏈表和鄰接多重表
鄰接矩陣
矩陣中標記1，有邊，標記0，沒有邊
注意：無向圖的鄰接矩陣是一個對稱矩陣
帶權圖的鄰接矩陣
鄰接矩陣自考/期末考試真題
嘗試著，畫出無向圖吧！
鄰接表
鄰接表是順序存盤與鏈式存盤相結合的存盤方法，
下圖中，左側是無向圖，右側是該無向圖的鄰接表，注意看，∧該符號，表示結束，沒有連接的頂點了，
有向圖及其類似，這個就不在做圖擴充
圖的遍歷
圖的遍歷是指從圖的某個頂點出發，系統地訪問圖的每個頂點，并且每個頂點只被訪問一次，
遍歷圖的基本方法有兩種：深度優先搜索和廣度優先搜索，
連通圖的深度優先搜索
深度優先，就是往下走，走不動了，回傳上一級在走
連通圖的廣度優先搜索
順著一個頂點，然后都遍歷完，
圖的應用
最小生成樹的概念
概念：一個圖的最小生成樹是圖所有生成樹中權總和最小的生成樹
構造最小生成樹的Prim演算法
每次都找權值最小的
看案例
構造最小生成樹的克魯斯卡爾演算法 與 單源最短路徑 這兩種演算法，自己看一下吧，
拓撲排序
- AOV網
工程或者某種流程可以分為若干個小的工程或階段，這些小的工程或階段就稱為活動，
如果以圖中的頂點來表示活動，有向邊表示活動之間的優先關系，這種用頂點表示活動的有向圖稱為AOV網，
- 拓撲排序
設G=(V，E) 是一個具有n個頂點的有向圖，V中頂點的序列v1，v2，...，vn稱為一個拓撲序列，當且僅當該頂點序列滿足下列條件：若在有向圖G中，從頂點vi ~ vj 有一條路徑，則在拓撲序列中頂點vi必須排在vj之前，找到一個有向圖的一個拓撲序列的程序稱為拓撲排序，完成拓撲排序的前提條件是AOV網中不允許出現回路，
拓撲排序演算法的時間復雜度為O(n+e)，n是圖的頂點個數，e是圖的弧的數目，
拓撲排序演算法的基本步驟如下：
- 圖中選擇一個入度為0的頂點，輸出該頂點
- 從圖中洗掉該頂點及相關聯的弧，調整被刪弧的弧頭結點的入度（入度減1）；
- 重復執行上述兩個步驟，直到所有的入度為0
好好理解一下拓撲排序演算法吧
自考/資料結構期末考試真題
畫圖說明步驟
更多圖示： https://dwz.cn/r4lCXEuL
拓撲排序不唯一~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/227902.html
標籤：其他