圖 (Graph)
圖并不是現(xiàn)實世界中的一幅畫, 例如
在計算機中, 圖是一種數(shù)據(jù)結(jié)構(gòu). 圖是計算機科學(xué)的一個概念, 在數(shù)學(xué)中也有對應(yīng)的數(shù)學(xué)分之: 圖論.
計算機中的圖如果表示出來大概長成這樣
可以把上圖想象成一個社交網(wǎng)絡(luò), 網(wǎng)絡(luò)中的每個圓表示一個User, User存在某種關(guān)系.
或者看作是一個城市群, 每個圓表示一個城市, 城市之間通過道路聯(lián)通.
直觀的從圖片上看 有3個組成部分:
- 紅色的圓
- 黃色的邊
- 黑色的數(shù)字
更一般的叫法是:
- 頂點(Vertex)
- 邊(Edge)
- 存儲的數(shù)據(jù)(Data)
圖的概念
- 頂點 (Vertex): 組成圖最小的元素, 頂點可以包含數(shù)據(jù). 一個圖可以有多個頂點.
- 邊 (Edge): 一般來說, 邊連接著兩個頂點, 因此一個圖中也可以存在多條邊
- 相鄰頂點(Adjacency Vertex): 相鄰頂點也叫頂點的度, 簡單來說就是一個頂點通過邊可以訪問到的其他頂點的集合, 例如圖中頂點0的相鄰頂點是{2, 3}
有了這些概念, 在理解的基礎(chǔ)上就可以對圖做一個稍微正式點的定義了
圖中的頂點集合用V表示, 邊的集合用E表示, 一張圖有若干頂點和相連接的邊組成, 因此圖G是由集合V和集合E組成, 可以表示為G(V,E)
簡單圖
上圖中的圖叫做簡單圖, 那什么樣的圖不叫簡單圖呢? 如下所示
在頂點0, 存在一個邊, 這種邊稱之為 自環(huán)邊(self-loop)
在頂點0和1之間, 除了之前那張圖片上的一條邊之外, 又多了一條邊, 多出來的這條邊稱之為 平行邊(parallel)
因此, 擁有自環(huán)邊或平行邊的圖不是簡單圖.
圖的分類
上面給出的圖的示例屬于最簡單的無向無權(quán)圖.
因為圖的邊可以附加一些信息(權(quán)), 以及邊是可以有方向的, 因此圖有兩個大類:
- 有權(quán)圖和無權(quán)圖
- 有向圖和無向圖
進一步的組合可以分為:
- 有權(quán)有向圖
- 有權(quán)無向圖
- 無權(quán)有向圖
- 無權(quán)無向圖
不同種類的圖有不同的作用, 在開始學(xué)習(xí)圖算法的時候, 應(yīng)先從最簡單的無權(quán)無向圖開始.
圖的基本表示
通過圖片可以很清楚的知道圖的形狀, 那么如何轉(zhuǎn)換到計算機中表示呢?
對于這個問題, 有兩種方式:
- 鄰接矩陣
- 鄰接表
這兩種方式各有優(yōu)缺點, 具體選擇哪一種需要看場景
鄰接矩陣
