吐血整理程序員必讀書單：https://github.com/silently9527/ProgrammerBooks
微信公眾號：貝塔學(xué)Java
前言
從本篇開始我們將會一起來學(xué)習(xí)圖相關(guān)的算法，圖算有很多相當(dāng)實用算法杭朱，比如：垃圾回收器的標(biāo)記清除算法扳埂、地圖上求路徑的最短距離法瑟、拓?fù)渑判虻妊谕辍Ｔ陂_始學(xué)習(xí)這些算法之前我們需要先來了解下圖的基本定義扼劈，以及使用哪種數(shù)據(jù)結(jié)構(gòu)來表示一張圖往枷，本篇我們先從無向圖開始學(xué)習(xí)登舞。
圖的定義
圖：是有一組頂點和一組能夠?qū)蓚€訂單相連組成的贰逾。連接兩個頂點的邊沒有方向，這種圖稱之為無向圖菠秒。
圖的術(shù)語
通過同一條邊相連的兩個頂點我們稱這兩個頂點相鄰疙剑；
某個頂點的度數(shù)即表示連接這個頂點的邊的總數(shù)；如上圖：頂點1的度數(shù)是3
一條邊連接了一個頂點與其自身践叠，我們稱為自環(huán)
連接同一對頂點的邊稱為平行邊
術(shù)語還有很多言缤，暫時這里只列出本篇我們需要使用到的術(shù)語，后面有在使用到其他的術(shù)語再做解釋酵熙，太多也不太容易記得住
如何表示出圖
圖用什么數(shù)據(jù)結(jié)構(gòu)來表示主要參考兩個要求：
- 在開發(fā)圖的相關(guān)算法時轧简，圖的表示的數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，所以這種數(shù)據(jù)結(jié)構(gòu)效率的高
- 在實際的過程中圖的大小不確定匾二，可能會很大哮独，所以需要預(yù)留出足夠的空間
考慮了這兩個要求之后大佬們提出以下三個方法來供選擇：
- 鄰接矩陣
鍵入有v個頂點的圖拳芙，我們可以使用v乘以v的矩陣來表示，如果頂點v與w相連皮璧，那么把v行w列設(shè)置為true舟扎，這樣就可以表示兩個頂點相連，但是這個方式有個問題悴务，如果遇到圖很大睹限，會造成空間的浪費。不滿足第二點讯檐。其次這種方式?jīng)]辦法表示平行邊 - 邊的數(shù)組
可以定義一個表示的邊對象羡疗，包含兩個int屬性表示頂點，但是如果需要找到某個頂點的相連頂點有哪些别洪，我們就需要遍歷一遍全部的邊叨恨。這種數(shù)據(jù)結(jié)構(gòu)的效率較差 - 鄰接表數(shù)組
定義一個數(shù)組，數(shù)組的大小為頂點的個數(shù)挖垛，數(shù)據(jù)下標(biāo)表示頂點痒钝，數(shù)組中每個元素都是一個鏈表對象（LinkedListQueue）,鏈表中存放的值就是與該頂點相連的頂點。（LinkedListQueue我們已經(jīng)在之前的文章中實現(xiàn)痢毒，可以參考文章《https://juejin.cn/post/6926685994347397127》）
無向圖的API定義
public class Graph {
public Graph(int V); //創(chuàng)建含有v個頂點不含邊的圖
public int V(); //返回頂點的個數(shù)
public int E(); //返回圖中邊的總數(shù)
public void addEdge(int v, int w); //向圖中添加一條邊 v-W
public Iterable<Integer> adj(int v); //返回與v相鄰的所有頂點
public String toString(); //使用字符串打印出圖的關(guān)系
}
無向圖API的實現(xiàn)
要實現(xiàn)上面定義的API送矩，我們需要三個成員變量，v表示圖中頂點的個數(shù)哪替，e表示圖總共邊的數(shù)據(jù)栋荸，LinkedListQueue的數(shù)組用來存儲頂點v的相鄰節(jié)點；
構(gòu)造函數(shù)會初始化空的鄰接表數(shù)組
因為是無向圖凭舶，所以addEdge方法在向圖中添加邊既要添加一條v->w的邊蒸其，有需要添加一條w->v的邊
public class Graph {
private final int v;
private int e;
private LinkedListQueue<Integer>[] adj;
public Graph(int v) {
this.v = v;
this.adj = (LinkedListQueue<Integer>[]) new LinkedListQueue[v];
for (int i = 0; i < v; i++) {
this.adj[i] = new LinkedListQueue<>();
}
}
public int V() {
return v;
}
public int E() {
return e;
}
public void addEdge(int v, int w) {
this.adj[v].enqueue(w);
this.adj[w].enqueue(v);
this.e++;
}
public Iterable<Integer> adj(int v) {
return this.adj[v];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(v).append(" 個頂點，").append(e).append(" 條邊\n");
for (int i = 0; i < v; i++) {
sb.append(i).append(": ");
for (int j : this.adj[i]) {
sb.append(j).append(" ");
}
sb.append("\n");
}
return sb.toString();
}
}
圖的常用工具方法
基于圖數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)库快，我們可以提供一些工具方法
- 計算頂點v的度數(shù)
頂點的度數(shù)就等于與之相連接頂點的個數(shù)
public static int degree(Graph graph, int v) {
int degree = 0;
for (int w : graph.adj(v)) {
degree++;
}
return degree;
}
- 計算所有頂點的最大度數(shù)
public static int maxDegree(Graph graph) {
int maxDegree = 0;
for (int v = 0; v < graph.V(); v++) {
int degree = degree(graph, v);
if (maxDegree < degree) {
maxDegree = degree;
}
}
return maxDegree;
}
- 計算所有頂點的平均度數(shù)
每條邊都有兩個頂點，所以圖所有頂點的總度數(shù)是邊的2倍
public static double avgDegree(Graph graph) {
return 2.0 * graph.E() / graph.V();
}
- 計算圖中的自環(huán)個數(shù)
對于頂點v钥顽，如果v同時也出現(xiàn)了在v的鄰接表中义屏，那么表示v存在一個自環(huán)；由于是無向圖蜂大，每條邊都被記錄了兩次（如果不好理解可以把圖的toString打印出來就可以理解了）
public static int numberOfSelfLoops(Graph graph) {
int count = 0;
for (int v = 0; v < graph.V(); v++) {
for (int w : graph.adj(v)) {
if (v == w) {
count++;
}
}
}
return count / 2;
}
總結(jié)
本篇我們主要學(xué)習(xí)使用何種數(shù)據(jù)結(jié)構(gòu)來表示一張圖闽铐，以及基于這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了幾個簡單的工具方法，在下一篇我們將來學(xué)習(xí)圖的第一個搜索算法 - 深度優(yōu)先搜索
文中所有源碼已放入到了github倉庫:
https://github.com/silently9527/JavaCore
最后（點關(guān)注奶浦，不迷路）
文中或許會存在或多或少的不足兄墅、錯誤之處，有建議或者意見也非常歡迎大家在評論交流澳叉。
最后隙咸，寫作不易沐悦，請不要白嫖我喲，希望朋友們可以點贊評論關(guān)注三連五督，因為這些就是我分享的全部動力來源??
