轉(zhuǎn)載請標明出處，謝謝！
http://www.itdecent.cn/p/cf03e51a3ca2
關(guān)聯(lián)文章
冒泡、選擇排序 http://www.itdecent.cn/p/176b0b892591
棧和隊列 http://www.itdecent.cn/p/8cb602ef4e21
順序表、單雙鏈表 http://www.itdecent.cn/p/3aeb5998e79e
二叉樹 http://www.itdecent.cn/p/de829eab944c
圖論 http://www.itdecent.cn/p/cf03e51a3ca2
圖
定義：圖(graph)是由一些點(vertex)和這些點之間的連線(edge)所組成的；其中，點通常被成為”頂點(vertex)”，而點與點之間的連線則被成為”邊或弧”(edege)。通常記為，G=(V,E)。
無向圖
有向圖
鄰接點
一條邊上的兩個頂點叫做鄰接點。 例如無向圖中的A點的B點就是鄰接點
在有向圖中，除了鄰接點之外；還有”入邊”和”出邊”的概念。
頂點的入邊，是指以該頂點為終點的邊。而頂點的出邊，則是指以該頂點為起點的邊。
度
在無向圖中，某個頂點的度是鄰接到該頂點的邊(或弧)的數(shù)目。
例如，上面無向圖中頂點A的度是3。
在有向圖中，度還有”入度”和”出度”之分。
某個頂點的入度，是指以該頂點為終點的邊的數(shù)目。而頂點的出度，則是指以該頂點為起點的邊的數(shù)目。
頂點的度=入度+出度。
例如，上面有向圖G2中，頂點B的入度是2，出度是2；頂點B的度=2+2=4。
路徑和回路
路徑：如果頂點(Vm)到頂點(Vn)之間存在一個頂點序列。則表示Vm到Vn是一條路徑。
路徑長度：路徑中”邊的數(shù)量”。
簡單路徑：若一條路徑上頂點不重復出現(xiàn)，則是簡單路徑。
回路：若路徑的第一個頂點和最后一個頂點相同，則是回路。
簡單回路：第一個頂點和最后一個頂點相同，其它各頂點都不重復的回路則是簡單回路。
連通圖和連通分量
連通圖：對無向圖而言，任意兩個頂點之間都存在一條無向路徑，則稱該無向圖為連通圖。 對有向圖而言，若圖中任意兩個頂點之間都存在一條有向路徑，則稱該有向圖為強連通圖。
連通分量：非連通圖中的各個連通子圖稱為該圖的連通分量。
權(quán)
在某些圖中，邊具有與之相關(guān)的數(shù)值，稱為權(quán)
鄰接矩陣
用一個一維數(shù)組存放圖中所有頂點數(shù)據(jù)；用一個二維數(shù)組存放頂點間關(guān)系（邊或?。┑臄?shù)據(jù)，這個二維數(shù)組稱為鄰接矩陣。
無向圖
有向圖
帶權(quán)有向圖
鄰接表
鄰接表存儲的基本思想：對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維數(shù)組構(gòu)成了頂點表。
將節(jié)點存入數(shù)組中，并對節(jié)點的孩子進行鏈式存儲，不管有多少孩子，也不會存在空間按浪費的問題，這個思路同樣適用于圖的存儲。我們把這種數(shù)組與鏈表相結(jié)合的存儲方法稱為鄰接表
無向圖
有向圖
帶權(quán)
圖的遍歷
[參考:]（https://blog.csdn.net/zhangxiangdavaid/article/details/38323633）
深度遍歷
從圖的某個頂點出發(fā)，訪問圖中的所有頂點，且使每個頂點僅被訪問一次。這一過程叫做圖的遍歷。
深度優(yōu)先搜索的思想：
①訪問頂點v；
②依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
③若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止。
比如：
在這里為了區(qū)分已經(jīng)訪問過的節(jié)點和沒有訪問過的節(jié)點，我們引入一個一維數(shù)組bool visited[MaxVnum]用來表示與下標對應(yīng)的頂點是否被訪問過，
流程：
? 首先輸出 V1，標記V1的flag=true;
? 獲得V1的鄰接邊 [V2 V3],取出V2，標記V2的flag=true;
? 獲得V2的鄰接邊[V1 V4 V5],過濾掉已經(jīng)flag的，取出V4，標記V4的flag=true;
? 獲得V4的鄰接邊[V2 V8],過濾掉已經(jīng)flag的，取出V8，標記V8的flag=true;
? 獲得V8的鄰接邊[V4 V5],過濾掉已經(jīng)flag的，取出V5，標記V5的flag=true;
? 此時發(fā)現(xiàn)V5的所有鄰接邊都已經(jīng)被flag了，所以需要回溯。（左邊黑色虛線，回溯到V1，回溯就是下層遞歸結(jié)束往回返）
?image? 回溯到V1，在前面取出的是V2，現(xiàn)在取出V3，標記V3的flag=true;
? 獲得V3的鄰接邊[V1 V6 V7]，過濾掉已經(jīng)flag的,取出V6，標記V6的flag=true;
? 獲得V6的鄰接邊[V3 V7],過濾掉已經(jīng)flag的,取出V7，標記V7的flag=true;
? 此時發(fā)現(xiàn)V7的所有鄰接邊都已經(jīng)被flag了，所以需要回溯。（右邊黑色虛線，回溯到V1，回溯就是下層遞歸結(jié)束往回返）
圖例：
代碼：
public void depthTraverse() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果頂點沒被訪問過先打印*/
System.out.println("打印頂點" + vertices[i]);
traverse(i);
}
}
}
public void traverse(int i) {
isVisited[i] = true;
int v = getFirstBor(i);
while (v!=-1){
if(!isVisited[v]){
System.out.println("visit ="+vertices[v]);
traverse(v);
}
/**
* 以下代碼會先壓入棧中，在遞歸完成后會以先進后出的
* 形式執(zhí)行，達到從下往上把各個頂點的鄰接點打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
v = getNextBor(i,v);
}
}
結(jié)果：
廣度優(yōu)先遍歷
所謂廣度，就是一層一層的，向下遍歷，層層堵截，還是這幅圖，我們?nèi)绻菑V度優(yōu)先遍歷的話，我們的結(jié)果是V1 V2 V3 V4 V5 V6 V7 V8。
廣度優(yōu)先搜索的思想：
① 訪問頂點vi ；
② 訪問vi 的所有未被訪問的鄰接點w1 ,w2 , …wk ；
③ 依次從這些鄰接點（在步驟②中訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；
說明：
為實現(xiàn)③，需要保存在步驟②中訪問的頂點，而且訪問這些頂點的鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。 這里我們就想到了用標準模板庫中的queue隊列來實現(xiàn)這種先進現(xiàn)出的服務(wù)。
老規(guī)矩我們還是走一邊流程：
說明：
?將V1加入隊列，取出V1，并標記為true(即已經(jīng)訪問)，將其鄰接點加進入隊列，則 <—[V2 V3]
?取出V2，并標記為true(即已經(jīng)訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V3 V4 V5]
?取出V3，并標記為true(即已經(jīng)訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V4 V5 V6 V7]
?取出V4，并標記為true(即已經(jīng)訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V5 V6 V7 V8]
?取出V5，并標記為true(即已經(jīng)訪問)，因為其鄰接點已經(jīng)加入隊列，則 <—[V6 V7 V8]
?取出V6，并標記為true(即已經(jīng)訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V7 V8]
?取出V7，并標記為true(即已經(jīng)訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V8]
?取出V8，并標記為true(即已經(jīng)訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[]
圖例
/**
* 廣度優(yōu)先
*/
public void bfs(){
for (int i = 0; i < verticesSize; i++) {
isVisited[i]=false;
}
for (int i = 0; i < verticesSize; i++) {
if(!isVisited[i]){
isVisited[i]=true;
System.out.println("visited vertice:"+ vertices[i]);
bfs(i);
}
}
}
public void bfs() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果頂點沒被訪問過先打印*/
System.out.println("打印頂點" + vertices[i]);
isVisited[i] = true;
bfs(i);
}
}
}
public void bfs(int i) {
/*自定義的隊列*/
Queue queue = new Queue();
int first = getFirstBor(i);
/*如果存在且沒有被訪問過*/
if (first != -1 && !isVisited[first]) {
isVisited[first] = true;
System.out.println("first " + vertices[first]);
queue.enQueue(queue, first);
}
int next = getNextBor(i, first);
while (next != -1) {
if (!isVisited[next]) {
isVisited[next] = true;
System.out.println("next " + vertices[next]);
queue.enQueue(queue, next);
}
next = getNextBor(i, next);
}
/*重復以上操作*/
while (queue.front != queue.rear) {
int temp = queue.array[queue.front];
bfs(temp);
queue.front = (queue.front + 1) % queue.MAX_LENGTH;
}
}
結(jié)果：
兩種算法的復雜度分析
深度優(yōu)先
數(shù)組表示：查找所有頂點的所有鄰接點所需時間為O(n2)，n為頂點數(shù)，算法時間復雜度為O(n2)
廣度優(yōu)先
數(shù)組表示：查找每個頂點的鄰接點所需時間為O(n2)，n為頂點數(shù)，算法的時間復雜度為O(n2)
代碼
public class MyGraph {
/*頂點集*/
public String[] vertices;
/*圖的邊的信息*/
public int[][] matrix;
/*矩陣大小*/
public int verticesSize;
/*被訪問過的頂點集合*/
public boolean[] isVisited;
public static final int MAX_WEIGHT = Integer.MAX_VALUE;
public MyGraph(int verticesSize) {
this.verticesSize = verticesSize;
vertices = new String[verticesSize];
matrix = new int[verticesSize][verticesSize];
isVisited = new boolean[verticesSize];
for (int i = 0; i < verticesSize; i++) {
vertices[i] = "v" + i;
}
}
/*獲取第一個鄰接點*/
public int getFirstBor(int v) {
for (int i = 0; i < verticesSize; i++) {
if (matrix[v][i] > 0 && matrix[v][i] < MAX_WEIGHT) {
// System.out.println(v + " first " + i);
return i;
}
}
return -1;
}
/**
* 獲取到頂點v的鄰接點index的下一個鄰接點
*/
public int getNextBor(int v, int index) {
for (int i = index + 1; i < verticesSize; i++) {
// System.out.println(v + "---" + i + "---" + matrix[v][i]);
if (matrix[v][i] > 0 && matrix[v][i] < MAX_WEIGHT) {
// System.out.println(v + " next " + i);
return i;
}
}
return -1;
}
public void depthTraverse() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果頂點沒被訪問過先打印*/
System.out.println("打印頂點" + vertices[i]);
traverse(i);
}
}
}
public void traverse(int i) {
isVisited[i] = true;
int v = getFirstBor(i);
while (v != -1) {
if (!isVisited[v]) {
System.out.println("visit =" + vertices[v]);
traverse(v);
}
/**
* 以下代碼會先壓入棧中，在遞歸完成后會以先進后出的
* 形式執(zhí)行，達到從下往上把各個頂點的鄰接點打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
v = getNextBor(i, v);
}
}
public void dfs(int i) {
isVisited[i] = true;
int v = getFirstBor(i);
if (v != -1) {
if (!isVisited[v]) {
System.out.println("visit =" + vertices[v]);
traverse(v);
}
/**
* 以下代碼會先壓入棧中，在遞歸完成后會以先進后出的
* 形式執(zhí)行，達到從下往上把各個頂點的鄰接點打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
// v = getNextBor(i,v);
}
}
public void bfs() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果頂點沒被訪問過先打印*/
System.out.println("打印頂點" + vertices[i]);
isVisited[i] = true;
bfs(i);
}
}
}
public void bfs(int i) {
/*自定義的隊列*/
Queue queue = new Queue();
int first = getFirstBor(i);
/*如果存在且沒有被訪問過*/
if (first != -1 && !isVisited[first]) {
isVisited[first] = true;
System.out.println("first " + vertices[first]);
queue.enQueue(queue, first);
}
int next = getNextBor(i, first);
while (next != -1) {
if (!isVisited[next]) {
isVisited[next] = true;
System.out.println("next " + vertices[next]);
queue.enQueue(queue, next);
}
next = getNextBor(i, next);
}
/*重復以上操作*/
while (queue.front != queue.rear) {
int temp = queue.array[queue.front];
bfs(temp);
queue.front = (queue.front + 1) % queue.MAX_LENGTH;
}
}
}
