当前位置：首页 > news >正文

c语言数据结构--构造无向图（算法6.1），深度和广度遍历

news 来源：原创 2024/9/17 3:58:59

实验内容：

实现教材算法6.2利用邻接矩阵构造无向图的算法，提供从邻接矩阵获得邻接表的功能，在此基础上进行深度优先遍历和广度优先遍历。

实验步骤：

（1）按照实验要求编写代码，构造无向图。
创建所示无向图
屏幕输出邻接矩阵
0 1 0 0 0 1
1 0 1 1 0 0
0 1 0 1 1 0
0 1 1 0 1 0
0 0 1 1 0 1
1 0 0 0 1 0

深度优先遍历

屏幕输出： 1 2 3 4 5 6

广度优先遍历

屏幕输出：1 2 6 3 4 5
（2）输入验收用例，验证其输出结果。

#include <iostream>
#ifndef DATA_STRUCTURE_STATUS_H
#include <stdio.h>
//状态码
#define TRUE              1
#define FALSE            0
#define OK                  1
#define ERROR           0
#endif
#ifndef OVERFLOW
#define OVERFLOW    -2
#endif // OVERFLOW
#ifndef NULL
#define NULL((void*) 0)
#endif // NULL
typedef int Status;
#define MaxInt 32767  //表示极大值
#define MVNum 100     //表示最大顶点数
using namespace std;//图的邻接矩阵存储表示：
typedef int VerTexType;//顶点字符类型
typedef int ArcType;    //边的权值
typedef struct
{VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum,arcnum;//图的当前点数和边数
}AMGraph;typedef string OtherInfo;//图的邻接表存储表示：
typedef struct ArcNode//边结构
{int adjvex;struct ArcNode *nextarc;OtherInfo info;//其他信息
}ArcNode;typedef struct VNode//顶点结构
{VerTexType data;//存储顶点信息ArcNode *firstarc;
}VNode,AdjList[MVNum];typedef struct
{AdjList vertics;//邻接表int vexnum,arcnum;//顶点数和弧数int kind;
}ALGraph;bool visited[MVNum];int LocateVex(AMGraph G,VerTexType u)
{//定位每个顶点的位置int i;for(i=0;i<G.vexnum;i++){if(u==G.vexs[i])return i;}return -1;
}//构建无向网：
Status CreateUDN(AMGraph &G)
{cout<<"请输入图的顶点数目，边数目:";cin>>G.vexnum>>G.arcnum;//输入当前的顶点数目和边的数目for(int i=0;i<G.vexnum;i++){cout<<"请输入第"<<i<<"个顶点：";cin>>G.vexs[i];//初始化点的信息}for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){G.arcs[i][j]=MaxInt;//初始化邻接矩阵}}int i,j;int v1,v2,w;for(int k=0;k<G.arcnum;k++){cout<<"边:";cin>>v1>>v2>>w;i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];}return OK;
}//邻接矩阵转换成邻接表
void change(AMGraph G,ALGraph &p)
{int i,j;ArcNode *q;for(i=0;i<G.vexnum;i++){p.vertics[i].firstarc=NULL;}for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(G.arcs[i][j]){q=new ArcNode;q->adjvex=j;q->nextarc=p.vertics[j].firstarc;p.vertics[j].firstarc=q;}}}
}//深度优先遍历：
void DFS_AM(AMGraph G,int v)
{cout<<v+1;visited[v]=true;for(int w=0;w<G.vexnum;w++)//依次检查邻接矩阵所在的行{if(G.arcs[v][w]!=0&&(!visited[w]))DFS_AM(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS}
}//广度优先遍历：
void BFS(AMGraph G,int v)
{for(int i=0;i<G.vexnum;i++){visited[i]=false;}int Q[MaxInt];cout<<G.vexs[v];visited[v]=true;int w,u;int front=-1,rear=-1;Q[++rear]=v;while(front!=rear){u=Q[++front];for(w=0;w<G.vexnum;w++){if((!visited[w])&&(G.arcs[u][w]==1)){cout<<G.vexs[w];visited[w]=true;Q[++rear]=w;}}}
}int main()
{cout<<"无向网图"<<endl;cout<<"1.构建网图"<<endl;cout<<"2.输出邻接矩阵"<<endl;cout<<"3.深度优先遍历"<<endl;cout<<"4.广度优先遍历"<<endl;int n,a;AMGraph G;ALGraph P;while(1){cout<<"请输入你的选择："<<endl;cin>>n;if(n==1){CreateUDN(G);cout<<"操作完成！"<<endl;}else if(n==2){cout<<"邻接矩阵为：";for(int i=0;i<G.vexnum;i++){cout<<endl;for(int j=0;j<G.vexnum;j++){if(G.arcs[i][j]==MaxInt){cout<<"0 ";}else{cout<<G.arcs[i][j]<<" ";}}}cout<<"\n操作完成"<<endl;}else if(n==3){cout<<"深度优先遍历为：";DFS_AM(G,0);cout<<"\n操作完成！"<<endl;}else if(n==4){cout<<"广度优先遍历为：";BFS(G,0);cout<<"\n操作完成"<<endl;}else if(n==5){cout<<"本次操作结束"<<endl;break;}}return 0;
}