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

C++图的操作(广度优先搜索、深度优先搜索、最短路径问题Dijkstra)--山东大学数据结构实验

程序员文章站 2022-05-22 19:22:06
...

一、实验内容:
1、创建图类,存储结构使用邻接矩阵。
2、输入图的节点数n(小于10个)、边数m,节点分别用1-n代表。
3、采用“起始节点,终止节点,权值”输入图的m条边,创建图。
4、输出从节点1开始的BFS遍历,在遍历过程中,如有多个可以选择的节点,则优先选择编号较小的节点。
5、输出从节点1开始的DFS遍历,在遍历过程中,如有多个可以选择的节点,则优先选择编号较小的节点。
6、输出从第1节点到第n节点最短路径的长度,如果没有路经,输出0。
二、输入输出样例:
C++图的操作(广度优先搜索、深度优先搜索、最短路径问题Dijkstra)--山东大学数据结构实验
三、实验代码:

#include<iostream>
#include<queue>
using namespace std;
int n,e;  			//节点个数为n边数为e 
int a[11][11];  	//邻接矩阵 (不能到达的节点用0表示;可以到达的节点存放权重w) 
int dis[11];		//存放各节点距离节点1的最短距离 
int reachbfs[10] = { 0 }; //广度优先遍历能够到达的节点,如果能够到达节点i,则reachbfs[i]=1; 
int rreach[10] = { 0 }; //按照遍历的先后存放顺序广度优先遍历能够到达的节点,如果第n次遍历到达节点i,则rreach[n]=i;
int reachdfs[10] = { 0 };	//深度优先遍历能够到达的节点,如果能够到达节点i,则reachdfs[i]=1; 
int reached[11];         	//寻找最短路径时用来标记已经到达过的节点 

void insert(int m, int n, int w)   //根据输入初始化邻接矩阵 
{
	if (a[m][n] == 0)
	{
		a[m][n] = w;
	}
}

void print() 				//打印输出邻接矩阵,用于验证邻接矩阵构造是否正确(可以不写此函数) 
{
	for (int i = 0; i < n + 1; i++)
	{
		for (int j = 0; j < n + 1; j++)
			cout << a[i][j] <<"  ";
		cout << endl;
	}
		
}
//广度优先搜索利用队列结构 
void bfs(int v, int reachbfs[],int rreach[])   //广度优先搜索,形参为起始节点v,标记数组reachbfs[],记录遍历顺序rreach[] 
{
	int m = 1;//用于记录遍历到达节点的先后顺序 
	queue<int> q;
	reachbfs[m] = v; 	//第一个到达v 
	rreach[v] = 1;		//标记v为已到达节点 
	m++;
	q.push(v);
	while (!q.empty())
	{
		int w = q.front();
		q.pop();

		for (int u = 1; u <= n; u++)
		{
			if (a[w][u] != 0 && rreach[u] == 0) //能够到达节点u,并且之前没有到达过u 
			{
				q.push(u);
				reachbfs[m] = u;   //记录到达的次序 
				rreach[u] = 1;		//标记为已到达 
				m++;
			}
		}
	}
}
//深度优先搜索利用递归的思想 
void dfs(int v, int reach[], int label)//label用于标记到达 
{
	reach[v] = label;
	for (int u = 1; u <= n; u++)
	{
		if (a[v][u] != 0 && reach[u] == 0)
		{
			reach[u] = label;
			dfs(u, reach, label);
		}
	}
}
//寻找最短路径利用Dijkstra算法 
void minPath()  
{
	for(int g=2;g<=n;g++)
	{
		if(a[1][g]!=0)
			dis[g]=a[1][g];
		else 
			dis[g]=99999;  
	}
	reached[1]=1;
    for(int g=1;g<=n;g++)
	{
	    int temp=99999,u=1;
	    for(int i=1;i<=n;i++)
		{
	        if(reached[i]==0&&dis[i]<temp)
			{
	            temp=dis[i];
	            u=i;
	        }
    	}
	    reached[u]=1;
	    for(int j=1;j<=n;j++)
	        if(reached[j]==0&&a[u][j]!=0)
	        	if(dis[j]>dis[u]+a[u][j])
					dis[j]=dis[u]+a[u][j];
	}
	cout<<dis[n]<<endl;
}

int main(void)
{
	int x,y,w;  
	char c;//用来存放输入的‘,’ 
	cout << "Input" << endl;
	cin >> n >>c>> e;
	for (int i = 1; i <= e; i++)   //构造邻接矩阵 
	{
		cin >> x >> c >> y >>c>> w;
		insert(x, y, w);
		insert(y, x, w);
	}
	cout << "Output" << endl;
	
	bfs(1, reachbfs,rreach); 
	int count = 0; //为了满足题目要求的输出格式 ,定义此变量 
	for (int i = 0; i < 10; i++)
		if (reachbfs[i] != 0)
			count++;
//输出bfs结果 
	for (int i = 0; i < 10; i++)
	{
		if (i != count)
		{
			if (reachbfs[i] != 0)
				cout << reachbfs[i]<<",";
		}
		else
			if (reachbfs[i] != 0)
				cout << reachbfs[i];
	}
	cout << endl;
//输出dfs结果	
	dfs(1, reachdfs, 1);
	for(int i=1,j=1;i<=n;i++){
		if(reachdfs[i]!=0){
			if(j==count){cout<<i<<endl;break;}
			else cout<<i<<",";
			j++;
		}
	}
//输出最短路径 
	if(reachdfs[n]==0)
		cout<<0<<endl;
	else 
		minPath();
	
	cout << "End0";
	return 0;
}