轉(zhuǎn)載請(qǐng)標(biāo)明出處诱担，謝謝！
http://www.reibang.com/p/cf03e51a3ca2
關(guān)聯(lián)文章
冒泡、選擇排序 http://www.reibang.com/p/176b0b892591
棧和隊(duì)列 http://www.reibang.com/p/8cb602ef4e21
順序表、單雙鏈表 http://www.reibang.com/p/3aeb5998e79e
二叉樹 http://www.reibang.com/p/de829eab944c
圖論 http://www.reibang.com/p/cf03e51a3ca2
圖
定義：圖(graph)是由一些點(diǎn)(vertex)和這些點(diǎn)之間的連線(edge)所組成的；其中稍走，點(diǎn)通常被成為”頂點(diǎn)(vertex)”，而點(diǎn)與點(diǎn)之間的連線則被成為”邊或弧”(edege)柴底。通常記為婿脸，G=(V,E)。
無向圖
有向圖
鄰接點(diǎn)
一條邊上的兩個(gè)頂點(diǎn)叫做鄰接點(diǎn)柄驻。 例如無向圖中的A點(diǎn)的B點(diǎn)就是鄰接點(diǎn)
在有向圖中狐树，除了鄰接點(diǎn)之外；還有”入邊”和”出邊”的概念鸿脓。
頂點(diǎn)的入邊抑钟，是指以該頂點(diǎn)為終點(diǎn)的邊。而頂點(diǎn)的出邊野哭，則是指以該頂點(diǎn)為起點(diǎn)的邊在塔。
度
在無向圖中，某個(gè)頂點(diǎn)的度是鄰接到該頂點(diǎn)的邊(或弧)的數(shù)目拨黔。
例如蛔溃，上面無向圖中頂點(diǎn)A的度是3。
在有向圖中篱蝇，度還有”入度”和”出度”之分贺待。
某個(gè)頂點(diǎn)的入度，是指以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目态兴。而頂點(diǎn)的出度狠持，則是指以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目疟位。
頂點(diǎn)的度=入度+出度瞻润。
例如，上面有向圖G2中甜刻，頂點(diǎn)B的入度是2绍撞，出度是2；頂點(diǎn)B的度=2+2=4得院。
路徑和回路
路徑：如果頂點(diǎn)(Vm)到頂點(diǎn)(Vn)之間存在一個(gè)頂點(diǎn)序列傻铣。則表示Vm到Vn是一條路徑。
路徑長度：路徑中”邊的數(shù)量”祥绞。
簡單路徑：若一條路徑上頂點(diǎn)不重復(fù)出現(xiàn)非洲，則是簡單路徑鸭限。
回路：若路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則是回路两踏。
簡單回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同败京，其它各頂點(diǎn)都不重復(fù)的回路則是簡單回路。
連通圖和連通分量
連通圖：對(duì)無向圖而言梦染，任意兩個(gè)頂點(diǎn)之間都存在一條無向路徑赡麦，則稱該無向圖為連通圖。 對(duì)有向圖而言帕识，若圖中任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑泛粹，則稱該有向圖為強(qiáng)連通圖。
連通分量：非連通圖中的各個(gè)連通子圖稱為該圖的連通分量肮疗。
權(quán)
在某些圖中晶姊，邊具有與之相關(guān)的數(shù)值，稱為權(quán)
鄰接矩陣
用一個(gè)一維數(shù)組存放圖中所有頂點(diǎn)數(shù)據(jù)伪货；用一個(gè)二維數(shù)組存放頂點(diǎn)間關(guān)系（邊或幻苯琛）的數(shù)據(jù)，這個(gè)二維數(shù)組稱為鄰接矩陣超歌。
無向圖
有向圖
帶權(quán)有向圖
鄰接表
鄰接表存儲(chǔ)的基本思想：對(duì)于圖的每個(gè)頂點(diǎn)vi砍艾，將所有鄰接于vi的頂點(diǎn)鏈成一個(gè)單鏈表，稱為頂點(diǎn)vi的邊表（對(duì)于有向圖則稱為出邊表）巍举，所有邊表的頭指針和存儲(chǔ)頂點(diǎn)信息的一維數(shù)組構(gòu)成了頂點(diǎn)表脆荷。
將節(jié)點(diǎn)存入數(shù)組中，并對(duì)節(jié)點(diǎn)的孩子進(jìn)行鏈?zhǔn)酱鎯?chǔ)懊悯，不管有多少孩子蜓谋，也不會(huì)存在空間按浪費(fèi)的問題，這個(gè)思路同樣適用于圖的存儲(chǔ)炭分。我們把這種數(shù)組與鏈表相結(jié)合的存儲(chǔ)方法稱為鄰接表
無向圖
有向圖
帶權(quán)
圖的遍歷
[參考:]（https://blog.csdn.net/zhangxiangdavaid/article/details/38323633）
深度遍歷
從圖的某個(gè)頂點(diǎn)出發(fā)桃焕，訪問圖中的所有頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次捧毛。這一過程叫做圖的遍歷观堂。
深度優(yōu)先搜索的思想：
①訪問頂點(diǎn)v；
②依次從v的未被訪問的鄰接點(diǎn)出發(fā)呀忧，對(duì)圖進(jìn)行深度優(yōu)先遍歷师痕；直至圖中和v有路徑相通的頂點(diǎn)都被訪問；
③若此時(shí)圖中尚有頂點(diǎn)未被訪問而账，則從一個(gè)未被訪問的頂點(diǎn)出發(fā)胰坟，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問過為止泞辐。
比如：
在這里為了區(qū)分已經(jīng)訪問過的節(jié)點(diǎn)和沒有訪問過的節(jié)點(diǎn)笔横，我們引入一個(gè)一維數(shù)組bool visited[MaxVnum]用來表示與下標(biāo)對(duì)應(yīng)的頂點(diǎn)是否被訪問過竞滓，
流程：
? 首先輸出 V1，標(biāo)記V1的flag=true;
? 獲得V1的鄰接邊 [V2 V3],取出V2吹缔，標(biāo)記V2的flag=true;
? 獲得V2的鄰接邊[V1 V4 V5],過濾掉已經(jīng)flag的虽界，取出V4，標(biāo)記V4的flag=true;
? 獲得V4的鄰接邊[V2 V8],過濾掉已經(jīng)flag的涛菠，取出V8莉御，標(biāo)記V8的flag=true;
? 獲得V8的鄰接邊[V4 V5],過濾掉已經(jīng)flag的，取出V5俗冻，標(biāo)記V5的flag=true;
? 此時(shí)發(fā)現(xiàn)V5的所有鄰接邊都已經(jīng)被flag了礁叔，所以需要回溯。（左邊黑色虛線迄薄，回溯到V1琅关，回溯就是下層遞歸結(jié)束往回返）
?image? 回溯到V1，在前面取出的是V2讥蔽，現(xiàn)在取出V3涣易，標(biāo)記V3的flag=true;
? 獲得V3的鄰接邊[V1 V6 V7]，過濾掉已經(jīng)flag的,取出V6冶伞，標(biāo)記V6的flag=true;
? 獲得V6的鄰接邊[V3 V7],過濾掉已經(jīng)flag的,取出V7新症，標(biāo)記V7的flag=true;
? 此時(shí)發(fā)現(xiàn)V7的所有鄰接邊都已經(jīng)被flag了，所以需要回溯响禽。（右邊黑色虛線徒爹，回溯到V1，回溯就是下層遞歸結(jié)束往回返）
圖例：
代碼：
public void depthTraverse() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果頂點(diǎn)沒被訪問過先打印*/
System.out.println("打印頂點(diǎn)" + 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);
}
/**
* 以下代碼會(huì)先壓入棧中芋类，在遞歸完成后會(huì)以先進(jìn)后出的
* 形式執(zhí)行隆嗅，達(dá)到從下往上把各個(gè)頂點(diǎn)的鄰接點(diǎn)打印的效果
* 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)先搜索的思想：
① 訪問頂點(diǎn)vi 坝锰；
② 訪問vi 的所有未被訪問的鄰接點(diǎn)w1 ,w2 , …wk 粹懒；
③ 依次從這些鄰接點(diǎn)（在步驟②中訪問的頂點(diǎn)）出發(fā)重付，訪問它們的所有未被訪問的鄰接點(diǎn); 依此類推顷级，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；
說明：
為實(shí)現(xiàn)③确垫，需要保存在步驟②中訪問的頂點(diǎn)弓颈，而且訪問這些頂點(diǎn)的鄰接點(diǎn)的順序?yàn)椋合缺４娴捻旤c(diǎn)帽芽，其鄰接點(diǎn)先被訪問。 這里我們就想到了用標(biāo)準(zhǔn)模板庫中的queue隊(duì)列來實(shí)現(xiàn)這種先進(jìn)現(xiàn)出的服務(wù)翔冀。
老規(guī)矩我們還是走一邊流程：
說明：
?將V1加入隊(duì)列导街，取出V1，并標(biāo)記為true(即已經(jīng)訪問)纤子，將其鄰接點(diǎn)加進(jìn)入隊(duì)列搬瑰，則 <—[V2 V3]
?取出V2，并標(biāo)記為true(即已經(jīng)訪問)控硼，將其未訪問過的鄰接點(diǎn)加進(jìn)入隊(duì)列泽论，則 <—[V3 V4 V5]
?取出V3，并標(biāo)記為true(即已經(jīng)訪問)卡乾，將其未訪問過的鄰接點(diǎn)加進(jìn)入隊(duì)列翼悴，則 <—[V4 V5 V6 V7]
?取出V4，并標(biāo)記為true(即已經(jīng)訪問)幔妨，將其未訪問過的鄰接點(diǎn)加進(jìn)入隊(duì)列鹦赎，則 <—[V5 V6 V7 V8]
?取出V5，并標(biāo)記為true(即已經(jīng)訪問)误堡，因?yàn)槠溧徑狱c(diǎn)已經(jīng)加入隊(duì)列古话，則 <—[V6 V7 V8]
?取出V6，并標(biāo)記為true(即已經(jīng)訪問)锁施，將其未訪問過的鄰接點(diǎn)加進(jìn)入隊(duì)列煞额，則 <—[V7 V8]
?取出V7，并標(biāo)記為true(即已經(jīng)訪問)沾谜，將其未訪問過的鄰接點(diǎn)加進(jìn)入隊(duì)列膊毁，則 <—[V8]
?取出V8，并標(biāo)記為true(即已經(jīng)訪問)基跑，將其未訪問過的鄰接點(diǎn)加進(jìn)入隊(duì)列婚温，則 <—[]
圖例
/**
* 廣度優(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]) {
/*如果頂點(diǎn)沒被訪問過先打印*/
System.out.println("打印頂點(diǎn)" + vertices[i]);
isVisited[i] = true;
bfs(i);
}
}
}
public void bfs(int i) {
/*自定義的隊(duì)列*/
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);
}
/*重復(fù)以上操作*/
while (queue.front != queue.rear) {
int temp = queue.array[queue.front];
bfs(temp);
queue.front = (queue.front + 1) % queue.MAX_LENGTH;
}
}
結(jié)果：
兩種算法的復(fù)雜度分析
深度優(yōu)先
數(shù)組表示：查找所有頂點(diǎn)的所有鄰接點(diǎn)所需時(shí)間為O(n2)，n為頂點(diǎn)數(shù)媳否，算法時(shí)間復(fù)雜度為O(n2)
廣度優(yōu)先
數(shù)組表示：查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n2)栅螟，n為頂點(diǎn)數(shù)，算法的時(shí)間復(fù)雜度為O(n2)
代碼
public class MyGraph {
/*頂點(diǎn)集*/
public String[] vertices;
/*圖的邊的信息*/
public int[][] matrix;
/*矩陣大小*/
public int verticesSize;
/*被訪問過的頂點(diǎn)集合*/
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;
}
}
/*獲取第一個(gè)鄰接點(diǎn)*/
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;
}
/**
* 獲取到頂點(diǎn)v的鄰接點(diǎn)index的下一個(gè)鄰接點(diǎn)
*/
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]) {
/*如果頂點(diǎn)沒被訪問過先打印*/
System.out.println("打印頂點(diǎn)" + 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);
}
/**
* 以下代碼會(huì)先壓入棧中篱竭，在遞歸完成后會(huì)以先進(jìn)后出的
* 形式執(zhí)行力图，達(dá)到從下往上把各個(gè)頂點(diǎn)的鄰接點(diǎn)打印的效果
* 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);
}
/**
* 以下代碼會(huì)先壓入棧中，在遞歸完成后會(huì)以先進(jìn)后出的
* 形式執(zhí)行掺逼，達(dá)到從下往上把各個(gè)頂點(diǎn)的鄰接點(diǎn)打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
// v = getNextBor(i,v);
}
}
public void bfs() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果頂點(diǎn)沒被訪問過先打印*/
System.out.println("打印頂點(diǎn)" + vertices[i]);
isVisited[i] = true;
bfs(i);
}
}
}
public void bfs(int i) {
/*自定義的隊(duì)列*/
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);
}
/*重復(fù)以上操作*/
while (queue.front != queue.rear) {
int temp = queue.array[queue.front];
bfs(temp);
queue.front = (queue.front + 1) % queue.MAX_LENGTH;
}
}
}
