圖的基本概念

首先，你要明確圖是什么樣子的，就是下面這個樣子的

圖的定義與術語

有向圖和無向圖

直接對比圖就可以看出來，有向圖和無向圖的區別了，這個沒有什么難的。

有向圖和無向圖的表示法有略微的區別，注意看 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稱為弧頭或終點。

任何兩點之間都有邊的無向圖稱為無向完全圖。 任何兩點之間都有弧的有向圖稱為有向完全圖。

權、帶權圖：圖的邊附帶數值，這個數值叫權。每條邊都帶權的圖稱為帶權圖。

頂點的度、入度、出度： 1. 無向圖中頂點v的度是與該頂點相關聯的邊的數目，記為D(v)。 2. 有向圖中，把以頂點v為終點的弧的數目稱為v的入度，記為ID(v)；把以頂點v為始點的弧的數目稱為v的出度，記為OD(v)。有向圖頂點v的度為入度和出度之和，即D（v） = ID（v）+ OD（v）。

簡單路徑、回路、簡單回路：序列中頂點不重復出現的路徑稱為簡單路徑。第一個頂點和最后一個頂點相同的路徑稱為回路。除了第一個頂點和最后一個頂點外，其余頂點不重復的回路，稱為簡單回路或簡單環。

下面還有一些需要了解的術語

連通、連通圖、連通分量、極大連通子圖、強連通、強連通圖、強連通分量、生成樹、生成森林

如果精力足夠，都看看吧

圖的存儲結構

圖的存儲結構有很多中，例如 鄰接矩陣、鄰接表、十字鏈表和鄰接多重表

鄰接矩陣

矩陣中標記1，有邊，標記0，沒有邊

注意：無向圖的鄰接矩陣是一個對稱矩陣

帶權圖的鄰接矩陣

鄰接矩陣自考/期末考試真題

嘗試著，畫出無向圖吧！

鄰接表

鄰接表是順序存儲與鏈式存儲相結合的存儲方法。

下圖中，左側是無向圖，右側是該無向圖的鄰接表，注意看，∧該符號，表示結束，沒有連接的頂點了。

有向圖及其類似，這個就不在做圖擴充

圖的遍歷

圖的遍歷是指從圖的某個頂點出發，系統地訪問圖的每個頂點，并且每個頂點只被訪問一次。 遍歷圖的基本方法有兩種：深度優先搜索和廣度優先搜索。

連通圖的深度優先搜索

深度優先，就是往下走，走不動了，返回上一級在走

連通圖的廣度優先搜索

順著一個頂點，然后都遍歷完。

圖的應用

最小生成樹的概念

概念：一個圖的最小生成樹是圖所有生成樹中權總和最小的生成樹

構造最小生成樹的Prim算法

每次都找權值最小的

看案例

構造最小生成樹的克魯斯卡爾算法 與 單源最短路徑 這兩種算法，自己看一下吧。

拓撲排序

AOV網 工程或者某種流程可以分為若干個小的工程或階段，這些小的工程或階段就稱為活動。 如果以圖中的頂點來表示活動，有向邊表示活動之間的優先關系，這種用頂點表示活動的有向圖稱為AOV網。

2. 拓撲排序 設G=(V，E) 是一個具有n個頂點的有向圖，V中頂點的序列v~1~，v~2~，...，v~n~稱為一個拓撲序列，當且僅當該頂點序列滿足下列條件：若在有向圖G中，從頂點v~i~ ~ v~j~ 有一條路徑，則在拓撲序列中頂點v~i~必須排在v~j~之前。找到一個有向圖的一個拓撲序列的過程稱為拓撲排序。完成拓撲排序的前提條件是AOV網中不允許出現回路。

拓撲排序算法的時間復雜度為O(n+e)，n是圖的頂點個數，e是圖的弧的數目。

拓撲排序算法的基本步驟如下：

圖中選擇一個入度為0的頂點，輸出該頂點

從圖中刪除該頂點及相關聯的弧，調整被刪弧的弧頭結點的入度（入度減1）；

重復執行上述兩個步驟，直到所有的入度為0

好好理解一下拓撲排序算法吧

自考/數據結構期末考試真題

畫圖說明步驟 更多圖示： https://dwz.cn/r4lCXEuL

拓撲排序不唯一~

總結

以上是生活随笔為你收集整理的c++ 图的连通分量是什么_【自考】数据结构第五章图，期末不挂科指南，第9篇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。