? ? 深度優(yōu)先遍歷也稱為深度優(yōu)先搜索，簡(jiǎn)稱為DFS。

? ? 深度優(yōu)先遍歷的思路是從圖中某個(gè)頂點(diǎn)V出發(fā)，訪問此頂點(diǎn)，然后從V的未被訪問過的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有與V路徑相通的頂點(diǎn)都被訪問到

? ? 該遍歷過程用到遞歸。

? ? 深度優(yōu)先遍歷用到了一個(gè)輔助數(shù)組Graph_sign【】，該數(shù)組的下標(biāo)與頂點(diǎn)數(shù)組的下標(biāo)對(duì)應(yīng)，即當(dāng)Graph_sign【1】中儲(chǔ)存的標(biāo)記為true就表示頂點(diǎn)數(shù)組vexs【1】中儲(chǔ)存的頂點(diǎn)已被遍歷到

代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
typedef char VertexType;//頂點(diǎn)類型
typedef int EdgeType;//邊上的權(quán)值類型
#define MAXVEX 20//最大頂點(diǎn)數(shù)（開辟儲(chǔ)存頂點(diǎn)的一維數(shù)組的空間大?。?#define INFINITY 10000//用10000來代表無窮（在儲(chǔ)存邊的二維數(shù)組中，對(duì)沒有該邊存在的表格，權(quán)值設(shè)為無窮）
//定義圖的結(jié)構(gòu)體（圖由儲(chǔ)存頂點(diǎn)的一維數(shù)組和儲(chǔ)存邊的二維數(shù)組，以及記錄圖中結(jié)點(diǎn)數(shù)和邊數(shù)的int類型的變量組成）
struct MGraph
{
	VertexType vexs[MAXVEX];//儲(chǔ)存頂點(diǎn)的一維數(shù)組
	EdgeType arc[MAXVEX][MAXVEX];//儲(chǔ)存邊的二維數(shù)組
	int Num_vex, Num_arc;//圖中的頂點(diǎn)數(shù)和邊數(shù)
};

//無向網(wǎng)圖的創(chuàng)建
void Create_MGraph(MGraph& G)
{
	int m, n;
	cout << "請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù)" << endl;
	cin >> G.Num_vex >> G.Num_arc;
	cout << "請(qǐng)依次輸入圖的頂點(diǎn)：" << endl;
	for (int i = 0; i < G.Num_vex; i++)
	{
		cin >> G.vexs[i];
	}
	//初始化儲(chǔ)存邊的二維數(shù)組
	for (int i = 0; i < G.Num_vex; i++)
		for (int j = 0; j < G.Num_vex; j++)
		{
			G.arc[i][j] = INFINITY;
		}
	//向二維數(shù)組中輸入對(duì)應(yīng)邊的權(quán)值
	for (int k = 0; k < G.Num_arc; k++)
	{
		cout << "請(qǐng)依次輸入邊（Vm,Vn）的下標(biāo)m，n" << endl;
		cin >> m >> n;
		cout << "請(qǐng)輸入邊(" << G.vexs[m-1] << "," << G.vexs[n - 1] << ")的權(quán)值" << endl;
		cin >> G.arc[m - 1][n - 1];
		//由于是無向網(wǎng)圖，所以存在邊（m，n），就存在邊（n，m）所以我們還應(yīng)該向二維數(shù)組的（n，m）位置輸入權(quán)值
		G.arc[n - 1][m - 1] = G.arc[m - 1][n - 1];
	}
}

//深度優(yōu)先遍歷輸出所有頂點(diǎn)
//記錄頂點(diǎn)是否被遍歷過的標(biāo)志數(shù)組
bool Graph_sign[MAXVEX];
//鄰接矩陣的深度優(yōu)先算法
void DFS(MGraph& G,int i)//i是作為第一個(gè)遍歷的頂點(diǎn)的下標(biāo)
{
	cout << G.vexs[i] << " ";
	//下標(biāo)為i的頂點(diǎn)已經(jīng)遍歷到改變標(biāo)志
	Graph_sign[i] = true;
	//遍歷其余頂點(diǎn)，判斷由頂點(diǎn)i能到達(dá)的下一個(gè)頂點(diǎn)
	for (int j = 0; j < G.Num_vex; j++)
	{
		if (G.arc[i][j] != INFINITY && !Graph_sign[j])
		{
			DFS(G, j);
		}
	}
}

//鄰接矩陣的深度遍歷操作
void DFS_MGraph(MGraph& G)
{
	//初始化標(biāo)志數(shù)組
	for (int i = 0; i < G.Num_vex; i++)
	{
		Graph_sign[i] = false;
	}
	//圖不連通的情況要有多個(gè)頂點(diǎn)作為第一個(gè)遍歷的頂點(diǎn)
	for (int j = 0; j < G.Num_vex; j++)
	{
		if (!Graph_sign[j])
			DFS(G, j);
	}
}


int main()
{
	MGraph G;
	Create_MGraph(G);
	DFS_MGraph(G);
	system("pause");
	return 0;
}

? ? ? ? 鄰接表和鄰接矩陣大同小異：

代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#define MAXSIZE 20
//頂點(diǎn)類型
typedef char VetexType;
//權(quán)值類型
typedef int InfoType;
//邊表結(jié)點(diǎn)
struct EdgeNode
{
	//鄰結(jié)點(diǎn)域儲(chǔ)存頂點(diǎn)的下標(biāo)
	int adjvex;
	//權(quán)值
	InfoType m_info;
	//指向下一個(gè)邊表結(jié)點(diǎn)的指針
	EdgeNode* next;
};

//頂點(diǎn)表結(jié)點(diǎn)
struct VertexNode
{
	//頂點(diǎn)
	VetexType vetex;
	//指向邊表的頭指針
	EdgeNode* FirstEdge;
};

//鄰接表
struct GraphAdiList
{
	//頂點(diǎn)數(shù)組
	VertexNode Adjext[MAXSIZE];
	//頂點(diǎn)個(gè)數(shù)，邊條數(shù)
	int numVertex, numEdges;
};

//創(chuàng)建鄰接表
void CreaterADGraph(GraphAdiList& G)
{
	int m, n, info;
	cout << "請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和邊條數(shù)" << endl;
	cin >> G.numVertex >> G.numEdges;
	//初始化頂點(diǎn)表
	for (int i = 0; i < G.numVertex; i++)
	{
		cout << "請(qǐng)輸入第" << i + 1 << "個(gè)頂點(diǎn)" << endl;
		//初始化頂點(diǎn)表中的兩個(gè)屬性
		cin >> G.Adjext[i].vetex;
		G.Adjext[i].FirstEdge = NULL;
	}
	//創(chuàng)建邊表
	for (int k = 0; k < G.numEdges; k++)
	{
		EdgeNode* p;
		p = new EdgeNode;
		cout << "請(qǐng)輸入邊（vm,vn）上的頂點(diǎn)序號(hào)（m，n）和權(quán)值" << endl;
		cin >> m >> n >> info;
		//初始化創(chuàng)建的邊表結(jié)點(diǎn)p
		p->adjvex = n - 1;
		p->m_info = info;
		//將邊表結(jié)點(diǎn)p按頭插法插入鄰接表
		p->next = G.Adjext[m - 1].FirstEdge;
		G.Adjext[m - 1].FirstEdge = p;
		//由于該圖是無向圖所以還要考慮（n，m）的情況
		p = new EdgeNode;
		p->adjvex = m - 1;
		p->m_info = info;
		p->next = G.Adjext[n - 1].FirstEdge;
		G.Adjext[n - 1].FirstEdge = p;
	}
	cout << "鄰接表創(chuàng)建完成" << endl;
}

//深度優(yōu)先遍歷輸出所有頂點(diǎn)
//鄰接表的深度優(yōu)先遍歷算法
bool Graph_sign[MAXSIZE];//標(biāo)志數(shù)組，用來判斷頂點(diǎn)是否被遍歷過，被遍歷過的為true，否則為false
void DFS(GraphAdiList& G, int i)//i是頂點(diǎn)在頂點(diǎn)表中的下標(biāo)
{

	//說明下標(biāo)為i的頂點(diǎn)已經(jīng)被遍歷
	Graph_sign[i] = true;
	cout << G.Adjext[i].vetex;
	EdgeNode* p;
	p = G.Adjext[i].FirstEdge;
	if (!Graph_sign[p->adjvex])
	{
		DFS(G, p->adjvex);
	}
}

//鄰接表的深度遍歷操作
void ADGraph(GraphAdiList& G)
{
	//初始化標(biāo)志數(shù)組
	for (int i = 0; i < G.numVertex; i++)
	{
		Graph_sign[i] = false;
	}
	//找到未被遍歷到的頂點(diǎn)作為第一個(gè)遍歷的頂點(diǎn)進(jìn)行遍歷（要是圖是全部連通的就只會(huì)遍歷一次）
	for (int j = 0; j < G.numVertex; j++)
	{
		if (!Graph_sign[j])
		{
			DFS(G, j);
		}
	}
}

int main()
{
	GraphAdiList G;
	CreaterADGraph(G);
	ADGraph(G);
}

? ? 以上兩個(gè)代碼都是完整的可調(diào)式的程序，相應(yīng)的關(guān)于鄰接矩陣和鄰接表的創(chuàng)建可以看這里：

鄰接表創(chuàng)建，鄰結(jié)矩陣的創(chuàng)建。

? ? 深度優(yōu)先遍歷的流程圖如下：

?

? ps：以上圖來自于大話數(shù)據(jù)結(jié)構(gòu)

? ? 我們注意到在深度遍歷操作中我們還要利用for循環(huán)遍歷所有頂點(diǎn)，再將其傳入深度優(yōu)先遍歷算法DFS中，其實(shí)我們的深度優(yōu)先遍歷算法DFS只要傳入一個(gè)頂點(diǎn)就已經(jīng)可以遍歷完一個(gè)連通圖了，那為什么我們還要遍歷所有頂點(diǎn)判斷出沒有遍歷到的頂點(diǎn)再調(diào)用DFS函數(shù)呢：-------因?yàn)槲覀兊膱D不一定是連通的，要是圖不連通的話就會(huì)分為幾個(gè)連通的部分，而深度優(yōu)先遍歷算法DFS只會(huì)遍歷出與傳入的首個(gè)頂點(diǎn)連通的所有頂點(diǎn)，而未與首個(gè)頂點(diǎn)連通的頂點(diǎn)是遍歷不出來的。所以要再對(duì)所有頂點(diǎn)進(jìn)行遍歷，找出其他連通部分的頂點(diǎn)作為該連通部分的首個(gè)頂點(diǎn)，傳入到DFS算法中

? ? （若圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)DFS算法直到圖中所有頂點(diǎn)都被訪問到為止）

? ??文章來源地址http://www.zghlxwxcb.cn/news/detail-473333.html

到了這里，關(guān)于深度優(yōu)先遍歷(鄰接矩陣，鄰接表)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！