一、圖的遍歷的定義：
從圖的某個(gè)頂點(diǎn)出發(fā)訪問遍圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次。（連通圖與非連通圖）
二、深度優(yōu)先遍歷（DFS）；
1、訪問指定的起始頂點(diǎn)；
2、若當(dāng)前訪問的頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的，則任選一個(gè)訪問之；反之，退回到最近訪問過的頂點(diǎn)；直到與起始頂點(diǎn)相通的全部頂點(diǎn)都訪問完畢；
3、若此時(shí)圖中尚有頂點(diǎn)未被訪問，則再選其中一個(gè)頂點(diǎn)作為起始頂點(diǎn)并訪問之，轉(zhuǎn) 2； 反之，遍歷結(jié)束。
連通圖的深度優(yōu)先遍歷類似于樹的先根遍歷
1、如何判別V的鄰接點(diǎn)是否被訪問？
解決辦法：為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問標(biāo)志”。首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE,? 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度
優(yōu)先遍歷，否則繼續(xù)檢查下一頂點(diǎn)。
訪問指定的起始頂點(diǎn)；若當(dāng)前訪問的頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的，則任選一個(gè)訪問之；
反之，退回到最近訪問過的頂點(diǎn)；直到與起始頂點(diǎn)相通的全部頂點(diǎn)都訪問完畢；
回退到1，發(fā)現(xiàn)了新的沒有被訪問的結(jié)點(diǎn)
繼續(xù)回退，回退到0
再也找不到新的結(jié)點(diǎn)了，那么回退，回退到起始頂點(diǎn)，結(jié)束搜索
頂點(diǎn)的訪問序列為：??? v0 , v1 , v4 , v5 , v6 , v2 , v3（不唯一）
2、實(shí)現(xiàn)過程：依靠棧，一維數(shù)組和圖的鄰接矩陣存儲(chǔ)方式
圖的鄰接矩陣存儲(chǔ)方式
使用一個(gè)一維數(shù)組存儲(chǔ)所有的頂點(diǎn)，對應(yīng)的下標(biāo)的元素為1（代表已經(jīng)被訪問），0（代表沒有被訪問）
先訪問 v1，0進(jìn)棧，0處置為1
繼續(xù)訪問 v2，1進(jìn)棧，1處置為1
繼續(xù)訪問v4（依據(jù)鄰接矩陣），3入棧，3處置為1
繼續(xù)訪問 v8，7入棧，7處置為1
繼續(xù)訪問 v5，4入棧，4處置為1
繼續(xù)訪問，發(fā)現(xiàn)沒有還沒訪問的結(jié)點(diǎn)了，那么好，退棧（也就是回退）開始，回退到 v1處，也就是0的時(shí)候，發(fā)現(xiàn)了沒有被訪問的結(jié)點(diǎn)，那么繼續(xù)訪問之
繼續(xù)訪問 v3，2進(jìn)棧，2處置為1，繼續(xù)訪問v6，5進(jìn)棧，5處置為1，繼續(xù)訪問v7，6進(jìn)棧，6處置為1
發(fā)現(xiàn)沒有還沒被訪問的結(jié)點(diǎn)了，那么好，繼續(xù)回退（也就是退棧的過程）
一直到棧空，說明深度優(yōu)先搜索完畢。結(jié)束程序。
遍歷圖的過程實(shí)質(zhì)上是對每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程，所耗費(fèi)的時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。
對圖中的每個(gè)頂點(diǎn)至多調(diào)用1次DFS算法，因?yàn)橐坏┠硞€(gè)頂點(diǎn)已訪問過，則不再從它出發(fā)進(jìn)行搜索。
鄰接鏈表表示：查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(e)，e為邊(弧)數(shù)，算法時(shí)間復(fù)雜度為O(n+e)。
數(shù)組表示：查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n2)，n為頂點(diǎn)數(shù)，算法時(shí)間復(fù)雜度為O(n2)。
3、代碼實(shí)現(xiàn)
//訪問標(biāo)志數(shù)組
int visited[MAX] = {0};
//用鄰接表方式實(shí)現(xiàn)深度優(yōu)先搜索(遞歸方式）
//v 傳入的是第一個(gè)需要訪問的頂點(diǎn)
void DFS(MGraph G, int v)
{
????????//圖的頂點(diǎn)的搜索指針
????????ArcNode *p;
????????//置已訪問標(biāo)記
????????visited[v] = 1;
????????//輸出被訪問頂點(diǎn)的編號
????????printf("%d ", v);
????????//p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)
????????p = G.vertices[v].firstarc;
????????while (p != NULL)
????????{
????????????????//若p->adjvex頂點(diǎn)未訪問,遞歸訪問它
????????????????if (visited[p->adjvex] == 0)
????????????????{
????????????????????????DFS(G, p->adjvex);
????????????????}
????????????????//p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)
????????????????p = p->nextarc;
????????}
}文章來源地址http://www.zghlxwxcb.cn/news/detail-797893.html
二、度優(yōu)先搜索（BFS）
方法：從圖的某一結(jié)點(diǎn)出發(fā)，首先依次訪問該結(jié)點(diǎn)的所有鄰接頂點(diǎn) Vi1, Vi2, …, Vin 再按這些頂點(diǎn)被訪問的先后次序依次訪問與它們相鄰接的所有未被訪問的頂點(diǎn)，重復(fù)此過程，直至所有頂點(diǎn)均被訪問為止。
頂點(diǎn)的訪問次序
1、實(shí)現(xiàn)過程：依靠隊(duì)列和一維數(shù)組來實(shí)現(xiàn)
2、代碼實(shí)現(xiàn)
#include <iostream>
#include<queue>
using namespace std;
const int MAX = 10;?
//輔助隊(duì)列的初始化，置空的輔助隊(duì)列Q，類似二叉樹的層序遍歷過程?
queue<int> q;
//訪問標(biāo)記數(shù)組
bool visited[MAX];?
//圖的廣度優(yōu)先搜索算法
void BFSTraverse(Graph G, void (*visit)(int v))?
{
????????int v = 0;?
????????//初始化訪問標(biāo)記的數(shù)組
????????for (v = 0; v < G.vexnum; v++)?
????????{
????????????????visited[v] = false;
????????}
????????//依次遍歷整個(gè)圖的結(jié)點(diǎn)
????????for (v = 0; v < G.vexnum; v++)
????????{
????????????????//如果v尚未訪問，則訪問 v
????????????????if (!visited[v])
????????????????{
????????????????????????//把 v 頂點(diǎn)對應(yīng)的數(shù)組下標(biāo)處的元素置為真，代表已經(jīng)訪問了
????????????????????????visited[v] = true;
????????????????????????//然后v入隊(duì)列，利用了隊(duì)列的先進(jìn)先出的性質(zhì)
????????????????????????q.push(v);
????????????????????????//訪問 v，打印處理
????????????????????????cout << q.back() << " ";
????????????????????????//隊(duì)不為空時(shí)
????????????????????????while (!q.empty())
????????????????????????{
????????????????????????????????//隊(duì)頭元素出隊(duì),并把這個(gè)出隊(duì)的元素置為 u，類似層序遍歷
????????????????????????????????Graph *u = q.front();
????????????????????????????????q.pop();
????????????????????????????????//w為u的鄰接頂點(diǎn)
????????????????????????????????for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G,u,w))
????????????????????????????????{
????????????????????????????????????????//w為u的尚未訪問的鄰接頂點(diǎn)
????????????????????????????????????????if (!visited[w])
????????????????????????????????????????{
????????????????????????????????????????????????visited[w] = true;
????????????????????????????????????????????????//然后 w 入隊(duì)列，利用了隊(duì)列的先進(jìn)先出的性質(zhì)
????????????????????????????????????????????????q.push(w);
????????????????????????????????????????????????//訪問 w，打印處理
????????????????????????????????????????????????cout << q.back() << " ";
????????????????????????????????????????}//end of if
????????????????????????????????}//end of for
????????????????????????}//end of while
????????????????}//end of if
????????}// end of for文章來源：http://www.zghlxwxcb.cn/news/detail-797893.html
}
到了這里，關(guān)于圖的遍歷（搜索）算法（深度優(yōu)先算法DFS和廣度優(yōu)先算法BFS）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
