欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的深度优先搜索遍历

程序员文章站 2022-05-21 08:46:39
...

深度优先搜索遍历

深度优先搜索遍历类似与树的先序遍历,过程如下
(1) 从图中的某个顶点v出发,访问v
(2) 找出刚访问过的顶点的第一个未被访问的邻接点,访问该节点。以该节点为新顶点,重复此步骤,直至访问过的顶点没有未被访问的邻接点为止
(3) 返回前一个访问过的且仍有为被访问的邻接点的顶点,找出该顶点的下一个为被访问邻接点,访问该节点
(4) 重复 (2)(3) 步骤,直至图中所有结点都被访问过,搜索结束
图例演示(无向图):
图的深度优先搜索遍历
实现代码:

	/*
	深度优先搜索遍历类似与树的先序遍历,过程如下
	(1) 从图中的某个顶点v出发,访问v
	(2) 找出刚访问过的顶点的第一个未被访问的邻接点,访问该节点。以该节点为新顶点,重复此步骤,直至访问过的顶点没有未被访问的邻接点为止
	(3) 返回前一个访问过的且仍有为被访问的邻接点的顶点,找出该顶点的下一个为被访问邻接点,访问该节点
	(4) 重复 (2)(3) 步骤,直至图中所有结点都被访问过,搜索结束
	*/
	
	#include<iostream>
	#include<string>
	using namespace std;
	
	#define OK 1
	#define ERROR 0
	#define MAXint 32767 //表示无穷大
	#define MVNum 100	//最大顶点数
	
	bool visited[MVNum] = { false };//标识数组,初始值为false
	
	//邻接矩阵的结构
	typedef struct
	{
		string vexs[MVNum];//顶点表
		int arcs[MVNum][MVNum];//邻接矩阵,也就是表示边的权值
		int vexnum, arcnum;//图的顶点数和边的个数
	}AMGraph;
	//邻接矩阵的结构
	
	//邻接表的结构
	typedef struct ArcNode {//边结点
		int adjvex;//该边所指向的顶点的位置
		struct  ArcNode* nextarc;//指向下一条边的指针
		int info;//和边相关的信息
	}ArcNode;
	
	typedef struct {//顶点信息
		string data;
		ArcNode* firstarc;//指向第一条依附该顶点的边的指针
	}VNode, AdjList[MVNum];
	
	typedef struct//邻接表
	{
		AdjList vertices;//顶点信息
		int vexnum, arcnum;//图的当前顶点数和边数
	}ALGraph;
	//邻接表的结构
	
	//查询结点位置
	int Locate(AMGraph G, string v)
	{
		for (int i = 0; i < G.vexnum; i++)
		{
			if (G.vexs[i] == v)
			{
				return i;
			}
		}
		return -1;
	}
	//查询结点位置
	
	int Locate(ALGraph G, string v)//Locate重载
	{
		for (int i = 0; i < G.vexnum; i++)
		{
			if (G.vertices[i].data == v)
			{
				return i;
			}
		}
		return -1;
	}
	
	//创建邻接矩阵
	int CreateUDN(AMGraph& G)//无向图的构造
	{
		cout << "请输入图的顶点数和边数:";
		cin >> G.vexnum >> G.arcnum;
		cout << "各节点的信息:";
		for (int i = 0; i < G.vexnum; i++)
		{
			cin >> G.vexs[i];
		}
		for (int i = 0; i < G.vexnum; i++)//初始化边的权值为MAXINT
		{
			for (int j = 0; j < G.vexnum; j++)
			{
				G.arcs[i][j] = MAXint;
			}
		}
		cout << "各边的顶点和权值:";
		for (int k = 0; k < G.arcnum; k++)//构造邻接矩阵
		{
			string v1, v2;
			int w;//边的两个顶点以及权值
			cin >> v1 >> v2 >> w;
			int i = Locate(G, v1);//找到点的位置
			int j = Locate(G, v2);
			G.arcs[i][j] = w;//赋予权值
			G.arcs[j][i] = G.arcs[i][j];
		}
		return OK;
	}
	//创建邻接矩阵
	
	//创建邻接表
	int CreateUDG(ALGraph& G)
	{
		cout << "请输入图的顶点数和边数:";
		cin >> G.vexnum >> G.arcnum;//输入顶点数和边数
		cout << "输入各节点的信息:";
		for (int i = 0; i < G.vexnum; i++)//初始化顶点信息
		{
			cin >> G.vertices[i].data;//输入顶点的信息
			G.vertices[i].firstarc = NULL;//firstarc置空
		}
		cout << "输入各边的顶点和权值:";
		for (int k = 0; k < G.arcnum; k++)
		{
			string v1, v2;
			int weight;//权值
			cin >> v1 >> v2 >> weight;//输入一条边依附的两个顶点
			int i = Locate(G, v1);
			int j = Locate(G, v2);
			ArcNode* p1 = new ArcNode;
			p1->info = weight;
			p1->adjvex = j;
			p1->nextarc = G.vertices[i].firstarc;
			G.vertices[i].firstarc = p1;
			ArcNode* p2 = new ArcNode;
			p2->info = weight;
			p2->adjvex = i;
			p2->nextarc = G.vertices[j].firstarc;
			G.vertices[j].firstarc = p2;
		}
		return OK;
	}
	//创建邻接表
	
	
	//深度优先遍历邻接矩阵
	void DFS_AM(AMGraph G, int v)
	{
		cout << G.vexs[v];//输出节点的值
		visited[v] = true;//标志数组相应分量值为true
		for (int i = 0; i < G.vexnum; i++)//找到v的邻接点
		{
			if ((G.arcs[v][i] != MAXint)&& (!visited[i]))
			{
				DFS_AM(G, i);//遍历i的邻接点
			}
		}
	}
	//深度优先遍历邻接矩阵
	
	//深度优先遍历邻接表
	void DFS_AL(ALGraph G, int v)
	{
		cout << G.vertices[v].data;//输出结点值
		visited[v] = true;//标志置为true
		ArcNode* p = G.vertices[v].firstarc;//p是v的邻接点
		while (p)
		{
			int w = p->adjvex;//邻接点的序号
			if (!visited[w])
			{
				DFS_AL(G, w);
			}
			p = p->nextarc;//指向下一个邻接点
		}
	}
	
	//深度优先遍历邻接表
	
	int main()
	{
		ALGraph G;
		CreateUDG(G);
		cout << "你要遍历的起点:";
		int v;
		cin >> v;
		DFS_AL(G, v);
		return 0;
	}