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

一、实验内容：
1、创建图类，存储结构使用邻接矩阵。
2、输入图的节点数n（小于10个）、边数m，节点分别用1-n代表。
3、采用“起始节点，终止节点，权值”输入图的m条边，创建图。
4、输出从节点1开始的BFS遍历，在遍历过程中，如有多个可以选择的节点，则优先选择编号较小的节点。
5、输出从节点1开始的DFS遍历，在遍历过程中，如有多个可以选择的节点，则优先选择编号较小的节点。
6、输出从第1节点到第n节点最短路径的长度，如果没有路经，输出0。
二、输入输出样例：

三、实验代码：

#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;
}