(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

这篇具有很好参考价值的文章主要介绍了(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题引入

        根据下图,编写代码实现图的深度优先遍历和广度优先遍历。

        按照英文字母顺序,以邻接表为存储结构,实现图的深度优先和广度优先遍历。遍历的顺序从顶点a开始。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 文章来源地址https://www.toymoban.com/news/detail-481454.html

一、代码实现

#include<iostream>
#include<malloc.h>
using 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<<endl; //换行 
	cout<<"输入图的各顶点(存储序号从0开始):"<<endl;
	for(i=0;i<G.n;i++){  //生成有n个顶点的顶点表
		cout<<"第"<<i<<"个顶点信息:";
		cin>>G.adjlist[i].data; //顶点数据存入表头 
		G.adjlist[i].firstal=NULL; //边表头指针域置为空 
	}
	cout<<endl; //换行 
	cout<<"输入图中的边,顶点序号从0开始:"<<endl;
	for(k=0;k<G.e;k++){
		cout<<endl; //换行 
		cout<<"输入第"<<k+1<<"条边:"<<endl;
		cout<<"输入出发顶点的序号:";
		cin>>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<<"邻接表中的存储内容如下所示:"<<endl;
	for(i=0;i<G.n;i++){
		cout<<i<<' '<<G.adjlist[i].data; //输出表头结点的数据 
		p=G.adjlist[i].firstal; //指向下一结点 
		while(p!=NULL){
			cout<<"--->"<<p->adjvex<<' '; //顺次输出结点信息 
			p=p->next;
		}
		cout<<endl; //换行 
	}
} 

//深度优先遍历
void DFSTraverse(Graph G,int v){
	ALnode *p; //辅助结点 
	cout<<"("<<v<<","<<G.adjlist[v].data<<")"<<' '; //输出顶点信息 
	visited[v] = 1;  
	p=G.adjlist[v].firstal; //访问第v个顶点
	while(p!=NULL){
		if(visited[p->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;i<G.n;i++){  
		visited[i]=0; //标志数组信息初始化 
	} 
	cout<<"("<<v<<","<<G.adjlist[v].data<<")"<<' '; //输出顶点信息 
	visited[v]=1; //对应顶点的标志置为1 
	rear=(rear+1)%MAX; //队尾指针后移 
	queue[rear]=v; //查找的顶点对应序号入队列 
	//循环遍历 
	while(front!=rear){
		front=(front+1)%MAX; //队头指针后移
		j=queue[front]; //从队列中取出顶点对应序号 
		p=G.adjlist[j].firstal; //取对应序号的顶点信息 
		while(p!=NULL){ 
			if(visited[p->adjvex]==0){
				visited[p->adjvex]=1;
				cout<<"("<<p->adjvex<<","<<G.adjlist[p->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-广度优先遍历"<<endl;
	cin>>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<G.n;i++){ 
					visited[i]=0; //标志数组信息初始化
				}
				cout<<endl;
				break;
			}
			case 3:{
				cout<<"输入从哪个顶点开始遍历(序号从0开始):";
				cin>>v2;
				BFSTraverse(G,v2);
				cout<<endl;
				break;
			}
			default:cout<<"输入错误,请重新选择!"<<endl;
		}
		cout<<"请选择:0-退出;1-创建有向图(采用邻接表存储结构);2-深度优先遍历;3-广度优先遍历"<<endl;
		cin>>choose;
	}
}

二、运行结果(一定要按照图的顺序看,避免疑惑)

        1.创建有向图

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

        2.图的深度优先遍历、广度优先遍历

(1)从顶点a,即序号0开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

(2)从顶点b,即序号1开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

(3)从顶点c,即序号2开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

(4)从顶点d,即序号3开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

(5)从顶点e,即序号4开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

(6)从顶点f,即序号5开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

(7)从顶点g,即序号6开始:

(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

 

到了这里,关于(超详细)C++图的深度优先遍历、广度优先遍历(数据结构)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) ,其中: 顶点集合V = {x|x属于某

    2024年02月04日
    浏览(73)
  • 【数据结构】图的创建和深度(DFS)广度(BFS)优先遍历

    图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图, V是图G中 顶点的集合 , E是图G中 边的集合 。 图分为 无向图 和 有向图 无向图: 若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用序偶对(Vi,Vj)表示。 有向图: 若从

    2024年02月05日
    浏览(61)
  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(67)
  • 数据结构与算法基础-学习-24-图的遍历之DFS(深度优先搜索)和BFS(广度优先搜索)

    目录 一、遍历定义 二、遍历实质 三、DFS 四、BFS 五、宏定义 六、自定义类型 七、函数实现 1、DFS(邻接矩阵实现) 2、DFS(邻接表实现) 3、BFS(邻接矩阵实现) 4、BFS(邻接表实现) 5、打印邻接矩阵遍历顺序  6、打印邻接表遍历顺序 八、遍历算法效率分析 1、DFS 2、BFS 九

    2024年02月03日
    浏览(74)
  • 【数据结构】图的广度优先遍历

    广度优先遍历,类似于树的层次遍历,又是熟悉的队列实现。首先将第一个顶点添加到队列中,然后讲该顶点的所有邻接顶点都加入队列中,再将该顶点输出。如此重复直到遍历完整个图。 Q:队列,用于存放顶点。 front,rear:队头和队尾指针,用于入队和出队。 p:工作指针,用

    2024年02月05日
    浏览(49)
  • 数据结构--5.3图的遍历(广度优先遍历)

    广度优先遍历:         广度优先遍历(BreadthFirstSearch),又称为广度优先搜索,简称BFS。 要实现对图的广度遍历,我们可以利用队列来实现。  (参考队列)(上述为结构)

    2024年02月10日
    浏览(47)
  • 【数据结构与算法】图的搜索——广度优先遍历、最小生成树

    邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍. 邻接矩阵:用于最短路径算法. 该数据结构维护一个不相交动态集的集合,每个集合有一个代表,不关心谁做代表。 支持三种操作: MAKE_SET(x) FIND_SET(x) UNION(x,y

    2024年02月19日
    浏览(50)
  • 图的遍历——深度优先遍历与广度优先遍历

    目录 何谓遍历? 图的遍历特点 图的遍历方式 深度优先搜索 过程分析 案例分析: 算法的代码实现  测试案例: 测试结果如下: 遍历非连通图 算法复杂度分析 额外补充 广度优先搜索 过程分析 辅助队列 算法的代码实现 队列部分 广度搜索部分 测试案例: 测试结果: 非连

    2024年02月04日
    浏览(41)
  • 图的广度优先遍历和深度优先遍历

    前言:在上一篇博客我们学习了图的基本操作,包括图的建立、结点插入与删除等操作,怎么判断我们建立的图是否正确,很简单把它输出出来就是,但是如何输出它,这就是图的遍历问题了。 图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所

    2024年02月11日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包