图的存储与遍历
一．实验目的
掌握图的存储结构以及图的深度优先搜索遍历、最小生成树算法。
二．实验要求与内容
自构造一无向图，采用邻接矩阵或者邻接表存储，完成图的深度优先搜索遍历以及广度优先搜索遍历算法的实现。
算法参见课本P214-225
三．实验步骤
1．数据结构
图的储存与遍历的邻接矩阵方式，在图的深度优先搜索中采用的是栈的方式进行结点的储存，在图的广度优先搜索中用的是队列方式进行储存。队列和栈用的都是stl中所定义好的，需要头文件#include<queue>和#include<stack>
在最小生成树中采用合并集的思想，定义一个结构体来储存边的开始点，结束点，以及权值大小。
2．算法设计
在深度优先搜索中用栈的方式进行储存以访问过的结点，找到一个结点A后进行访问标记并压入栈，访问与它相连的另一个结点B标记并压入栈，再访问结点B相连的任一结点标记并压入栈，重复，，直至没有结点N没有可供访问的结点。则从栈中弹出头结点，寻找结点N-1的另外可供访问的结点，如果没有则再弹出头结点直至栈为空。
在广度优先搜索中用队列的方式进行储存访问过的结点，找到一个结点A后进行访问标记并进入队列，访问与它相连的所有结点标记并进入队列，当与它相连的所有结点都进入队列后头结点出队，访问队列头结点的所有可供访问的结点并进入队列，，重复，直至队列为空
在这两种访问方式中设置一个visited用来标记该结点是否被访问过，如果未被访问过visited[i]=0否则visited[i]=1;
合并集求最小生成树，将每一个结点都看作成一棵树，将权值进行排序，求最小权值的start和end是否在一棵树中，如果不在一棵树中则将两个结点并为一棵树，重复找最小权值和合并树这两个步骤直至所有结点都在一棵树上为止。
详细过程解析看代码注释
3．程序
void DFS1(int v)//深度优先搜索
{
cout<<b[v]<<" ";//访问第v个结点
visited[v]=1;//设置该结点已经被访问过；
s.push(v);
int count=1;
while(!(s.empty()&& count==n))
{
if(s.empty() && count!=n)//需要判断栈空但是结点并没有遍历完的情况
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)//如果该邻接结点都还没有被访问过
{
cout<<b[i]<<" ";
visited[i]=1;
s.push(i);
count++;
break;
}
}
}
int w=node1(s.top());//求该结点的邻接结点
while(w!=-1)//如果该结点存在邻接结点
{
if(!visited[w])
{
cout<<b[w]<<" ";
s.push(w);
visited[w]=1;
count++;
}
w=node1(w);
}
s.pop();
}
}
void DFS(int v)//广度优先搜索
{
cout<<b[v]<<" ";//访问第v个结点
visited[v]=1;//设置该结点已经被访问过；
q.push(v);
int count=1;
while(!(q.empty()&&count==n))
{
if(q.empty() && count!=n)//需要判断队列空但是结点并没有遍历完的情况
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
cout<<b[i]<<" ";
visited[i]=1;
q.push(i);
count++;
break;
}
}
}
int s=q.front();
q.pop();
int w=node1(s);//求该结点的邻接结点
while(w!=-1)//如果该结点存在邻接结点
{
if(!visited[w])//如果该邻接结点都还没有被访问过
{
cout<<b[w]<<" ";
q.push(w);
visited[w]=1;
count++;
}
w=node1(s);
}
}
}
int find(int x)
{
if(x!=pre[x])
pre[x]=find(pre[x]);
return pre[x];
}
void megre(int x,int y,int n)//查并集合并函数，n 用来记录最短路中应该加入哪个点
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
sum=edge[n].power+sum;
}
}
4．程序调试
测试数据、程序运行结果截图
四．结果与体会
在使用栈和队列的时候可以用stl中的栈的队列，，无需自己定义函数，但需要加头文件#include<queue>和#include<stack>
在求最小权值的时候可以用查并集的方法。
在广度优先搜索和深度优先搜索的时候要特别考虑如果栈或者队列为空时但是结点却没有遍历完。即输入的图并不是一棵树，可能是森林的情况下。
五．源程序
另附
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define M 100
int a[M][M];//邻接矩阵
int b[M];//顶点数据
int visited[M];
queue<int> q;
stack<int>s;
int pre[M];
int sum=0;
struct node
{
int start,end,power;
}edge[20];
int m,n;//无向图的顶点数和边数
int node1(int v)
{
for(int i=1;i<=n;i++)
{
if(a[v][i]!=0 && visited[i]==0)
return i;
}
return -1;//如果该结点的所有相连结点都被访问过
}
int cmp(node a,node b)//按权值排序
{
return a.power<b.power;
}
int find(int x)
{
if(x!=pre[x])
pre[x]=find(pre[x]);
return pre[x];
}
void megre(int x,int y,int n)//查并集合并函数，n 用来记录最短路中应该加入哪个点
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
sum=edge[n].power+sum;
}
}
void DFS1(int v)//深度优先搜索
{
cout<<b[v]<<" ";//访问第v个结点
visited[v]=1;//设置该结点已经被访问过；
s.push(v);
int count=1;
while(!(s.empty()&& count==n))
{
if(s.empty() && count!=n)//需要判断栈空但是结点并没有遍历完的情况
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)//如果该邻接结点都还没有被访问过
{
cout<<b[i]<<" ";
visited[i]=1;
s.push(i);
count++;
break;
}
}
}
int w=node1(s.top());//求该结点的邻接结点
while(w!=-1)//如果该结点存在邻接结点
{
if(!visited[w])
{
cout<<b[w]<<" ";
s.push(w);
visited[w]=1;
count++;
}
w=node1(w);
}
s.pop();
}
}
void DFS(int v)//广度优先搜索
{
cout<<b[v]<<" ";//访问第v个结点
visited[v]=1;//设置该结点已经被访问过；
q.push(v);
int count=1;
while(!(q.empty()&&count==n))
{
if(q.empty() && count!=n)//需要判断队列空但是结点并没有遍历完的情况
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
cout<<b[i]<<" ";
visited[i]=1;
q.push(i);
count++;
break;
}
}
}
int s=q.front();
q.pop();
int w=node1(s);//求该结点的邻接结点
while(w!=-1)//如果该结点存在邻接结点
{
if(!visited[w])//如果该邻接结点都还没有被访问过
{
cout<<b[w]<<" ";
q.push(w);
visited[w]=1;
count++;
}
w=node1(s);
}
}
}
int main()
{
//构造无向图，邻接矩形
cout<<"请输入无向图的顶点数和边数";
cin>>n>>m;
for(int i=1;i<=n;i++)//初始化邻接矩阵
for(int j=1;j<=n;j++)
a[i][j]=0;
cout<<"请输入顶点的顺序";
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
cout<<"依次输入每一条边两个顶点的序列号和权值"<<endl;
for(int i=1;i<=m;i++)
{
int x,y,weight;
scanf("%d %d %d",&x,&y,&weight);
edge[i].start=x;
edge[i].end=y;
edge[i].power=weight;
a[x][y]=weight;
a[y][x]=weight;
}
//图的广度优先搜索
cout<<"广度优先遍历的结点顺序为："<<endl;
DFS(1);
for(int i=1;i<=n;i++)
visited[i]=0;
//图的深度优先搜索
cout<<endl;
cout<<"深度优先遍历的结点顺序为："<<endl;
DFS1(1);
cout<<endl;
//求最小权值
for(int i=1;i<=m;i++)
pre[i]=i;
sort(edge+1,edge+m+1,cmp);
for(int i=1;i<=m;i++)
megre(edge[i].start,edge[i].end,i);
cout<<"最小权值为：";
cout<<sum<<endl;
return 0;
}
