深度优先遍历(邻接矩阵，邻接表)-Toy模板网

这篇具有很好参考价值的文章主要介绍了深度优先遍历(邻接矩阵，邻接表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

深度优先遍历也称为深度优先搜索，简称为DFS。

深度优先遍历的思路是从图中某个顶点V出发，访问此顶点，然后从V的未被访问过的邻接点出发深度优先遍历图，直到图中所有与V路径相通的顶点都被访问到

该遍历过程用到递归。

深度优先遍历用到了一个辅助数组Graph_sign【】，该数组的下标与顶点数组的下标对应，即当Graph_sign【1】中储存的标记为true就表示顶点数组vexs【1】中储存的顶点已被遍历到

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型
#define MAXVEX 20//最大顶点数（开辟储存顶点的一维数组的空间大小）
#define INFINITY 10000//用10000来代表无穷（在储存边的二维数组中，对没有该边存在的表格，权值设为无穷）
//定义图的结构体（图由储存顶点的一维数组和储存边的二维数组，以及记录图中结点数和边数的int类型的变量组成）
struct MGraph
{
	VertexType vexs[MAXVEX];//储存顶点的一维数组
	EdgeType arc[MAXVEX][MAXVEX];//储存边的二维数组
	int Num_vex, Num_arc;//图中的顶点数和边数
};

//无向网图的创建
void Create_MGraph(MGraph& G)
{
	int m, n;
	cout << "请输入图的顶点数和边数" << endl;
	cin >> G.Num_vex >> G.Num_arc;
	cout << "请依次输入图的顶点：" << endl;
	for (int i = 0; i < G.Num_vex; i++)
	{
		cin >> G.vexs[i];
	}
	//初始化储存边的二维数组
	for (int i = 0; i < G.Num_vex; i++)
		for (int j = 0; j < G.Num_vex; j++)
		{
			G.arc[i][j] = INFINITY;
		}
	//向二维数组中输入对应边的权值
	for (int k = 0; k < G.Num_arc; k++)
	{
		cout << "请依次输入边（Vm,Vn）的下标m，n" << endl;
		cin >> m >> n;
		cout << "请输入边(" << G.vexs[m-1] << "," << G.vexs[n - 1] << ")的权值" << endl;
		cin >> G.arc[m - 1][n - 1];
		//由于是无向网图，所以存在边（m，n），就存在边（n，m）所以我们还应该向二维数组的（n，m）位置输入权值
		G.arc[n - 1][m - 1] = G.arc[m - 1][n - 1];
	}
}

//深度优先遍历输出所有顶点
//记录顶点是否被遍历过的标志数组
bool Graph_sign[MAXVEX];
//邻接矩阵的深度优先算法
void DFS(MGraph& G,int i)//i是作为第一个遍历的顶点的下标
{
	cout << G.vexs[i] << " ";
	//下标为i的顶点已经遍历到改变标志
	Graph_sign[i] = true;
	//遍历其余顶点，判断由顶点i能到达的下一个顶点
	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)
{
	//初始化标志数组
	for (int i = 0; i < G.Num_vex; i++)
	{
		Graph_sign[i] = false;
	}
	//图不连通的情况要有多个顶点作为第一个遍历的顶点
	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
//顶点类型
typedef char VetexType;
//权值类型
typedef int InfoType;
//边表结点
struct EdgeNode
{
	//邻结点域储存顶点的下标
	int adjvex;
	//权值
	InfoType m_info;
	//指向下一个边表结点的指针
	EdgeNode* next;
};

//顶点表结点
struct VertexNode
{
	//顶点
	VetexType vetex;
	//指向边表的头指针
	EdgeNode* FirstEdge;
};

//邻接表
struct GraphAdiList
{
	//顶点数组
	VertexNode Adjext[MAXSIZE];
	//顶点个数，边条数
	int numVertex, numEdges;
};

//创建邻接表
void CreaterADGraph(GraphAdiList& G)
{
	int m, n, info;
	cout << "请输入顶点个数和边条数" << endl;
	cin >> G.numVertex >> G.numEdges;
	//初始化顶点表
	for (int i = 0; i < G.numVertex; i++)
	{
		cout << "请输入第" << i + 1 << "个顶点" << endl;
		//初始化顶点表中的两个属性
		cin >> G.Adjext[i].vetex;
		G.Adjext[i].FirstEdge = NULL;
	}
	//创建边表
	for (int k = 0; k < G.numEdges; k++)
	{
		EdgeNode* p;
		p = new EdgeNode;
		cout << "请输入边（vm,vn）上的顶点序号（m，n）和权值" << endl;
		cin >> m >> n >> info;
		//初始化创建的边表结点p
		p->adjvex = n - 1;
		p->m_info = info;
		//将边表结点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 << "邻接表创建完成" << endl;
}

//深度优先遍历输出所有顶点
//邻接表的深度优先遍历算法
bool Graph_sign[MAXSIZE];//标志数组，用来判断顶点是否被遍历过，被遍历过的为true，否则为false
void DFS(GraphAdiList& G, int i)//i是顶点在顶点表中的下标
{

	//说明下标为i的顶点已经被遍历
	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)
{
	//初始化标志数组
	for (int i = 0; i < G.numVertex; i++)
	{
		Graph_sign[i] = false;
	}
	//找到未被遍历到的顶点作为第一个遍历的顶点进行遍历（要是图是全部连通的就只会遍历一次）
	for (int j = 0; j < G.numVertex; j++)
	{
		if (!Graph_sign[j])
		{
			DFS(G, j);
		}
	}
}

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

以上两个代码都是完整的可调式的程序，相应的关于邻接矩阵和邻接表的创建可以看这里：

邻接表创建，邻结矩阵的创建。

深度优先遍历的流程图如下：

深度优先遍历(邻接矩阵，邻接表)

ps：以上图来自于大话数据结构

我们注意到在深度遍历操作中我们还要利用for循环遍历所有顶点，再将其传入深度优先遍历算法DFS中，其实我们的深度优先遍历算法DFS只要传入一个顶点就已经可以遍历完一个连通图了，那为什么我们还要遍历所有顶点判断出没有遍历到的顶点再调用DFS函数呢：-------因为我们的图不一定是连通的，要是图不连通的话就会分为几个连通的部分，而深度优先遍历算法DFS只会遍历出与传入的首个顶点连通的所有顶点，而未与首个顶点连通的顶点是遍历不出来的。所以要再对所有顶点进行遍历，找出其他连通部分的顶点作为该连通部分的首个顶点，传入到DFS算法中

（若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复DFS算法直到图中所有顶点都被访问到为止）

文章来源地址https://www.toymoban.com/news/detail-473333.html

到了这里，关于深度优先遍历(邻接矩阵，邻接表)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！