Question

数据结构C语言版 图的广度优先遍历和深度优先遍历 急急急 会查重

描述给出一个无向图顶点和边的信息，输出这个无向图的深度优先遍历序列和广度优先遍历序列。从一个顶点出发如果有2个以上的顶点可以访问时，我们约定先访问编号大的那个顶点。示例输入对应的图如下图所示：输入输入的第1行有2个整数m和n。表示图g有m个顶点和n条边。第2行是m个以空格隔开的字符串，依次是图中第1个顶点的名字，第2个顶点的名字.....第m个顶点的名字。此后还有n行，每行由2个字符串构成，分别是构成图中1条边的两个顶点。我们约定不会有重边。输出输出有2行。第1行是从第1个顶点出发对图g做深度优先遍历得到的顶点序列。第2行是从第1个顶点出发对图g做广度优先遍历得到的顶点序列。样例输入8 9v1 v2 v3 v4 v5 v6 v7 v8v1 v2v1 v3v1 v6v2 v3v2 v4v3 v4v4 v6v5 v6v7 v8样例输出v1 v6 v5 v4 v3 v2 v7 v8v1 v6 v3 v2 v5 v4 v7 v8

Answer 1

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int FirstAdjVex(int v);
int NextAdjVex(int v, int w);
void DFS(int v); //从顶点v开始对图做深度优先遍历, v是顶点数组的下标
void BFS(int v); //从顶点v开始对图做广度优先遍历，v是顶点数组的下标
int find(string a,int n);

int visited[10]={0};
int traver[10][10]={0};
string name[10];

int main()
{
	int n,m,i,j,k;
	string a,b;
	//freopen("Traver.txt","r",stdin);
	cin>>n;
	cin>>m;
	for(i=0; i<n; i++)
	{
		cin>>a;
		name[i] = a;
	}
	for(i=0; i<m;i++){
		cin>>a;
		cin>>b;
		j = find(a,n);
		k = find(b,n);
		traver[j][k] = 1;
		traver[k][j] = 1;
	}
	for(i=0; i<n; i++){
		if(visited[i] == 0)
			DFS(i);
	}
	cout<<"\n";
	for(i=0; i<n; i++){
		visited[i] = 0;
	}
	for(i=0; i<n; i++){
		if(visited[i] == 0)
			BFS(i);
	}
	cout<<"\n";
	return 0;
}
//寻找函数
int find(string a,int n){
	int i;
	for(i=0; i<n; i++){
		if(a == name[i])
			return i;
	}
	return -1;
}
int FirstAdjVex(int v)
{
	int i;
	//从编号大的邻接点开始访问
	for (i = 9; i >= 0; i--)
	{
		if (traver[v][i] == 1)
			return i;
	}
	return -1;
}
int NextAdjVex(int v, int w)
{
	int i;
	for (i = w - 1; i >= 0; i--)
	{
		if (traver[v][i] == 1)
			return i;
	}
	return -1;
}
void DFS(int v)
{
	int w;
	//访问顶点v(输出顶点v的名字)
	cout<<name[v]<<" ";
	visited[v] = 1;
	//找到顶点v的第一个邻接点w
	for (w = FirstAdjVex(v); w >= 0; w = NextAdjVex(v, w))
	{
		//如果w没有访问过，对顶点w做深度优先搜索
		if (visited[w] == 0)
			DFS(w);
	}
}
void BFS(int v) //从顶点v开始对图做广度优先遍历，v是顶点数组的下标
{
	int w, u;
	queue<int> myqueue; //定义一个队列，元素是顶点的下标
	//把顶点v入队
	myqueue.push(v);
	cout<<name[v]<<" ";
	visited[v] = 1;
	while (!myqueue.empty())
	{//当队列不为空时进入循环
		//取队头元素
		u = myqueue.front();
		//队头元素出队
		myqueue.pop();
		//把u的所有邻接点入队	
		w = FirstAdjVex(u);
		while (w >= 0)
		{
			if (visited[w] == 0)
			{
				//访问w
				cout<<name[w]<<" ";
				visited[w] = 1;
				//w入队
				myqueue.push(w);
			}
			w = NextAdjVex(u, w);
		}
	}
}