圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來(lái)定義對(duì)象之間的關(guān)系或聯(lián)系。對(duì)象由頂點(diǎn)（V）表示，而對(duì)象之間的關(guān)系或者關(guān)聯(lián)則通過(guò)圖的邊（E）來(lái)表示螟加。
圖可以分為有向圖和無(wú)向圖，一般用G=(V,E)來(lái)表示圖。經(jīng)常用鄰接矩陣或者鄰接表來(lái)描述一副圖捆探。
在圖的基本算法中然爆，最初需要接觸的就是圖的遍歷算法，根據(jù)訪問(wèn)節(jié)點(diǎn)的順序黍图，可分為廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）曾雕。
廣度優(yōu)先搜索（BFS）
廣度優(yōu)先搜索在進(jìn)一步遍歷圖中頂點(diǎn)之前，先訪問(wèn)當(dāng)前頂點(diǎn)的所有鄰接結(jié)點(diǎn)助被。
a .首先選擇一個(gè)頂點(diǎn)作為起始結(jié)點(diǎn)剖张，并將其染成灰色，其余結(jié)點(diǎn)為白色揩环。
b. 將起始結(jié)點(diǎn)放入隊(duì)列中搔弄。
c. 從隊(duì)列首部選出一個(gè)頂點(diǎn)，并找出所有與之鄰接的結(jié)點(diǎn)丰滑，將找到的鄰接結(jié)點(diǎn)放入隊(duì)列尾部顾犹，將已訪問(wèn)過(guò)結(jié)點(diǎn)涂成黑色，沒(méi)訪問(wèn)過(guò)的結(jié)點(diǎn)是白色吨枉。如果頂點(diǎn)的顏色是灰色蹦渣，表示已經(jīng)發(fā)現(xiàn)并且放入了隊(duì)列，如果頂點(diǎn)的顏色是白色貌亭，表示還沒(méi)有發(fā)現(xiàn)
d. 按照同樣的方法處理隊(duì)列中的下一個(gè)結(jié)點(diǎn)。
基本就是出隊(duì)的頂點(diǎn)變成黑色认臊，在隊(duì)列里的是灰色圃庭，還沒(méi)入隊(duì)的是白色。
用一副圖來(lái)表達(dá)這個(gè)流程如下：
從頂點(diǎn)1開(kāi)始進(jìn)行廣度優(yōu)先搜索：
- 初始狀態(tài)竖般，從頂點(diǎn)1開(kāi)始甚垦，隊(duì)列={1}
- 訪問(wèn)1的鄰接頂點(diǎn)，1出隊(duì)變黑，2,3入隊(duì)艰亮，隊(duì)列={2,3,}
- 訪問(wèn)2的鄰接結(jié)點(diǎn)闭翩，2出隊(duì)，4入隊(duì)迄埃，隊(duì)列={3,4}
- 訪問(wèn)3的鄰接結(jié)點(diǎn)疗韵，3出隊(duì)，隊(duì)列={4}
- 訪問(wèn)4的鄰接結(jié)點(diǎn)调俘，4出隊(duì)伶棒，隊(duì)列={ 空}
結(jié)點(diǎn)5對(duì)于1來(lái)說(shuō)不可達(dá)。
上面的圖可以通過(guò)如下鄰接矩陣表示：
int maze[5][5] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
BFS核心代碼如下：
#include <iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = { 0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << " ";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] && maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}
深度優(yōu)先搜索（DFS）
深度優(yōu)先搜索在搜索過(guò)程中訪問(wèn)某個(gè)頂點(diǎn)后彩库，需要遞歸地訪問(wèn)此頂點(diǎn)的所有未訪問(wèn)過(guò)的相鄰頂點(diǎn)肤无。
初始條件下所有節(jié)點(diǎn)為白色，選擇一個(gè)作為起始頂點(diǎn)骇钦，按照如下步驟遍歷：
a. 選擇起始頂點(diǎn)涂成灰色宛渐，表示還未訪問(wèn)
b. 從該頂點(diǎn)的鄰接頂點(diǎn)中選擇一個(gè)，繼續(xù)這個(gè)過(guò)程（即再尋找鄰接結(jié)點(diǎn)的鄰接結(jié)點(diǎn)）眯搭，一直深入下去窥翩，直到一個(gè)頂點(diǎn)沒(méi)有鄰接結(jié)點(diǎn)了，涂黑它鳞仙，表示訪問(wèn)過(guò)了
c. 回溯到這個(gè)涂黑頂點(diǎn)的上一層頂點(diǎn)寇蚊，再找這個(gè)上一層頂點(diǎn)的其余鄰接結(jié)點(diǎn)，繼續(xù)如上操作棍好，如果所有鄰接結(jié)點(diǎn)往下都訪問(wèn)過(guò)了仗岸，就把自己涂黑，再回溯到更上一層借笙。
d. 上一層繼續(xù)做如上操作扒怖，知道所有頂點(diǎn)都訪問(wèn)過(guò)。
用圖可以更清楚的表達(dá)這個(gè)過(guò)程：
從頂點(diǎn)1開(kāi)始做深度搜索：
- 初始狀態(tài)看成，從頂點(diǎn)1開(kāi)始
- 依次訪問(wèn)過(guò)頂點(diǎn)1,2,3后，終止于頂點(diǎn)3
- 從頂點(diǎn)3回溯到頂點(diǎn)2跨嘉，繼續(xù)訪問(wèn)頂點(diǎn)5川慌，并且終止于頂點(diǎn)5
- 從頂點(diǎn)5回溯到頂點(diǎn)2吃嘿，并且終止于頂點(diǎn)2
- 從頂點(diǎn)2回溯到頂點(diǎn)1，并終止于頂點(diǎn)1
- 從頂點(diǎn)4開(kāi)始訪問(wèn)梦重，并終止于頂點(diǎn)4
上面的圖可以通過(guò)如下鄰接矩陣表示：
int maze[5][5] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
DFS核心代碼如下（遞歸實(shí)現(xiàn)）：
#include <iostream>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
visited[start] = 1;
for (int i = 1; i <= N; i++)
{
if (!visited[i] && maze[start - 1][i - 1] == 1)
DFS(i);
}
cout << start << " ";
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
非遞歸實(shí)現(xiàn)如下兑燥，借助一個(gè)棧：
#include <iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
stack<int> s;
s.push(start);
visited[start] = 1;
bool is_push = false;
while (!s.empty())
{
is_push = false;
int v = s.top();
for (int i = 1; i <= N; i++)
{
if (maze[v - 1][i - 1] == 1 && !visited[i])
{
visited[i] = 1;
s.push(i);
is_push = true;
break;
}
}
if (!is_push)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
有的DFS是先訪問(wèn)讀取到的結(jié)點(diǎn)，等回溯時(shí)就不再輸出該結(jié)點(diǎn)琴拧，也是可以的降瞳。算法和我上面的區(qū)別就是輸出點(diǎn)的時(shí)機(jī)不同，思想還是一樣的蚓胸。DFS在環(huán)監(jiān)測(cè)和拓?fù)渑判蛑卸加胁诲e(cuò)的應(yīng)用挣饥。
PS: 圖文均為本人原創(chuàng)，畫(huà)了好幾個(gè)小時(shí)沛膳，轉(zhuǎn)載注明出處扔枫，尊重知識(shí)勞動(dòng)，謝謝~
