> 引用：[https://www.cnblogs.com/jaxu/p/11338294.html](https://www.cnblogs.com/jaxu/p/11338294.html) # 介紹 多對多的一種數據結構。 圖：一些頂點和一些邊的集合。  ## 術語  # 分類 ## 有向圖和無向圖  ## 入度和出度 對于 `有向圖` 來說。 入度：進入一個頂點的邊數。 出席：從一個頂點出去的邊數。 ## 有權圖  # 連通性 ### 連通圖 1. 從一個頂點到另一頂點，若存在至少一條路徑，則稱兩個頂點是連通的。 2. 在 `無向圖` 中，若任意兩個頂點都連通，則圖是連通圖。  ### 強連通圖 在 `有向圖` 中，若任意兩個頂點都含有至少一條通路，則圖是強連通圖。  ## 連通網 在連通圖中，若圖的邊具有一定的意義，每一條邊都對應著一個數，稱為權；權代表著連接連個頂點的代價，稱這種連通圖叫做連通網。  # 生成樹 對 `連通圖` 進行遍歷時，遍歷過程中所經過的 `邊` 和 `頂點` 的組合可看做是一棵普通樹，通常稱為生成樹。 如下圖，a為連通圖，b為生成樹。  因為連通圖中有多個邊，所以一個連通圖可能會有多個生成樹。