(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)-创新互联
问题引入
当前文章:(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)-创新互联
本文来源:http://hbruida.cn/article/jpjeh.html
根据下图,编写代码实现图的深度优先遍历和广度优先遍历。
创新互联公司是一家专注于成都网站建设、做网站与策划设计,酒泉网站建设哪家好?创新互联公司做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:酒泉等地区。酒泉做网站价格咨询:18980820575按照英文字母顺序,以邻接表为存储结构,实现图的深度优先和广度优先遍历。遍历的顺序从顶点a开始。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。
一、代码实现#include#includeusing namespace std;
#define MAX 20 //定义常量值为20
int visited[MAX]; //定义标志数组(全局)
//定义主结点结构(边界点)
typedef struct Anode{
int adjvex; //邻接点域(数据域)
struct Anode *next; //指向下一邻接点的指针域
}ALnode;
//定义顶点表结点
typedef struct vexnode{
char data; //顶点域
ALnode *firstal; //指向第一条边结点
}VexHeadNode;
//定义图的邻接表存储结构
typedef struct{
VexHeadNode adjlist[MAX]; //邻接表头结点数组
int n; //图的当前顶点数
int e; //图的当前弧数,即边数
}Graph;
//建立图的邻接表
void createGraph(Graph &G){
int i,j,k; //辅助变量
ALnode *p; //辅助结点
cout<<"输入图的顶点数:";
cin>>G.n;
cout<<"输入图的边数:";
cin>>G.e;
cout<>G.adjlist[i].data; //顶点数据存入表头
G.adjlist[i].firstal=NULL; //边表头指针域置为空
}
cout<>i;
cout<<"输入指向顶点的序号:";
cin>>j;
//邻接表存储连接
p=(ALnode *)malloc(sizeof(ALnode)); //分配存储空间
p->adjvex=j; //指向顶点的序号存入邻接点数据域
p->next=G.adjlist[i].firstal; //新的结点的指针域置为空
G.adjlist[i].firstal=p; //新结点信息依次存入邻接表中
}
}
//输出邻接表
void printGraph(Graph G){
int i; //辅助变量
ALnode *p; //辅助结点
cout<<"邻接表中的存储内容如下所示:"<"<adjvex<<' '; //顺次输出结点信息
p=p->next;
}
cout<adjvex]==0){
DFSTraverse(G,p->adjvex);
}
p=p->next;
}
}
//广度优先遍历
void BFSTraverse(Graph G,int v){
int i,j,visited[MAX]; //辅助变量、标志数组
ALnode *p; //辅助结点
int queue[MAX],front=0,rear=0; //定义循环队列
for(i=0;iadjvex]==0){
visited[p->adjvex]=1;
cout<<"("<adjvex<<","<adjvex].data<<")"<<' '; //输出顶点信息
rear=(rear+1)%MAX; //队尾指针后移
queue[rear]=p->adjvex; //查找的顶点对应序号入队列
}
p=p->next;
}
}
}
//主函数
int main(){
Graph G; //定义图结构变量
int v1,v2,choose;
cout<<"请选择:0-退出;1-创建有向图(采用邻接表存储结构);2-深度优先遍历;3-广度优先遍历"<>choose;
while(choose!=0){
switch(choose){
case 1:{
createGraph(G); //创建有向图
printGraph(G); //输出
break;
}
case 2:{
cout<<"输入从哪个顶点开始遍历(序号从0开始):";
cin>>v1;
DFSTraverse(G,v1);
for(int i=0;i>v2;
BFSTraverse(G,v2);
cout<>choose;
}
}
二、运行结果(一定要按照图的顺序看,避免疑惑)1.创建有向图2.图的深度优先遍历、广度优先遍历
(1)从顶点a,即序号0开始:(2)从顶点b,即序号1开始:(3)从顶点c,即序号2开始:(4)从顶点d,即序号3开始:(5)从顶点e,即序号4开始:(6)从顶点f,即序号5开始:(7)从顶点g,即序号6开始:你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前文章:(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)-创新互联
本文来源:http://hbruida.cn/article/jpjeh.html