圖：

圖結構區別于線性結構和樹型結構，區別可見下圖

邏輯上的圖(graph)結構由頂點(vertex)和邊(edge)組成。

一個圖結構G包含頂點集合V和邊集合E，任何兩個頂點之間可以有一個邊表示兩者的關系。

對于一個存在的G，V不可以為空集，E可以為空集。

左中右分別都是圖結構

與圖相關的概念：

有向圖：

邊都具有方向的圖結構就是有向圖結構。邊的方向表示訪問的方向。

有向無環圖：

對于一個有向圖，如果對于任意一個節點來說，從該這一個結點起，不存在路徑使得可以重新回到這一結點上，這個有向圖就是有向無環圖。

有向有環圖：

與有向無環圖相反。

入度，出度：

這一概念只適用于有向圖。對于有向圖種，一個指向一個頂點的邊數量稱為個頂點的入度，從這個頂點指出的邊的數量稱為這個頂點的出度。

11這一頂點的入度是2，出度為3

無向圖：

無向圖中，連接兩個頂點的邊是沒有方向的，可以在邏輯上認為是兩個頂點間如果有邊直接連通，則一定兩個方向都有的有向圖。

混合圖：

混合圖種既存在有向邊，也存在無向邊。

簡單圖、多重圖：

如果在無向圖中，直接連通兩個頂點的邊大于等于2條，這些邊稱為平行邊。

如果在有向圖中，直接連通兩個頂點的同方向的邊大于等于2條，這些邊稱為平行邊。

如果在圖中一條邊直接連通同一個頂點，就成為自環。

如果在圖結構中存在平行邊或者自環，這個圖就稱為多重圖，如果兩者都不存在，那么稱為簡單圖。

無向完全圖、有向完全圖：

如果在無向圖中任意兩個頂點之間都存在直接連通兩個頂點的邊，那么這個無向圖就成為無向完全圖。

如果在有向圖中任意兩個頂點之間都存在方向相反的直接連通兩個頂點兩個邊，那么這個有向圖就成為有向完全圖。

無向完全圖

有向完全圖

稠密圖、稀疏圖：

邊數接近于完全圖的圖就是稠密圖，邊數遠遠少于完全圖的圖就是稀疏圖。

有權圖：

連接頂點的邊上帶有權值的圖稱為有權圖

連通圖：

如果無向圖中任意兩個頂點都可以連通，無論是間接還是直接，那么這個無向圖稱為連通圖。

連通圖

連通分量：

連通分量就是無向圖中的最大連通子圖數量，也就是一個無向圖分出來的最多的互不連通的部分。對于一個連通圖來說，連通分量為1。

強連通圖：

強連通圖就是對有向圖定義的連通圖。

強連通圖

強連通分量：

同無向圖的連通分量概念。

圖的實現：

圖一般有兩種實現方法，一種是鄰接矩陣，還有一種是鄰接表，鄰接矩陣實際操作比較復雜，這里主要寫鄰接表的代碼實現。

圖的鄰接矩陣實現：

無向圖

有向圖

圖的鄰接表實現：

圖的鄰接表實現主要是分別將結點和邊存放在結構體中，再以一定的方式將這些結構聯系起來。以下實現代碼主要使用哈希map來實現有向有權圖，代碼總體還是以表現思路為主。

//有向有權圖的頂點結構，假定頂點存儲的元素為int類型

圖的遍歷：

廣度優先搜索(BFS):

廣度優先搜索類似于二叉樹的層序遍歷。從一個指定的頂點開始，將指定的頂點視作邏輯上的第一層，指定的頂點所連通的頂點視作邏輯上的第二層，指定的頂點所聯通的頂點所連通的頂點視作邏輯上的第三層，以此類推依次遍歷，直到遍歷完所有頂點。

BFS的一種情況//圖結構的廣度優先遍歷

由以上的廣度優先遍歷實現代碼可知，廣度優先遍歷上邏輯上下一層的元素一定是再當前層元素之后被訪問，但是邏輯上同一層的元素的訪問先后次序沒有規律，這取決于outEdges這一set結構中的存儲順序。

深度優先搜索(DFS)：

深度優先搜索的思路類似于二叉樹的先序遍歷，從指定的頂點開始，訪問該頂點后繼續訪問該頂點的邏輯上下一層的第一個頂點，以此類推直到不存在下一層的頂點，那就返回倒數第二層層的第二個頂點的位置繼續重復以上操作，直到所有的頂點都被遍歷。

DFS的一種情況//圖的深度優先遍歷

有向圖的應用：AOV網(Activity On Vertex Network)

一項大的工程經常被分為多個小的子工程，多個子工程之間可能存在一定的先后順序，也就是說某些子工程必須在其他子工程完成后才能開始。因此，在現代化管理中，人們常用有向圖來描述和分析一項大工程的計劃和實施過程，子工程被稱為活動(Activity)，在有向圖中用頂點來表示，有向邊表示活動之間的向后關系，這樣的圖結構稱為AOV網。

結構：

標準的AOV網結構是一個有向無環圖。

拓撲排序：

將AOV網中的所有頂點按活動的發生順序排成一個序列，該序列一定滿足活動發生的先后順序，但同一優先級的活動的順序不一定。比如說下圖的排序結果是ABCDEF或者ABDCEF。

用卡恩算法實現AOV網的拓撲排序：

算法實現(僅僅體現思路)

//假定之前寫的Graph就是AOV結構

總結

以上是生活随笔為你收集整理的分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历_数据结构与算法学习笔记：图...的全部內容，希望文章能夠幫你解決所遇到的問題。

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