文档章节

数据结构(算法)-图(深度优先搜索 DFS和广度优先搜索BFS)

ashuo
 ashuo
发布于 2018/10/22 17:56
字数 795
阅读 29
收藏 0
#include <iostream>

using namespace std;



#define MaxVex 30
typedef char VertexType;
typedef struct vexNode adjList[MaxVex];

struct edgeNode{
	int adjvex;//邻接点序列
	VertexType data;//邻接点信息
	struct edgeNode *next;
};

struct vexNode{
	VertexType data ; //结点信息
	struct edgeNode *next; 
};

//创建邻接表
void creagraph(adjList g, int *n){
	int e ,i , s ,d ;
	struct edgeNode *p,*q ;
	printf("结点数(n),边数(e)");
	scanf("%d,%d",n , &e);
	for(i=1;i<=*n ; i++){
		getchar();
		printf("第%d个结点信息:",i);
		scanf("%c",&g[i].data);
		g[i].next=NULL;

	}
	for(i=1;i<=e;i++){
		printf("第%d条边起点,终点序号:",i);
		scanf("%d,%d",&s , &d);
		p=(struct edgeNode *)malloc(sizeof(struct edgeNode));
		q=(struct edgeNode *)malloc(sizeof(struct edgeNode));
		p->adjvex=d;
		p->data=g[d].data;

		q->adjvex=s;
		q->data=g[s].data;

		p->next=g[s].next;//*p插入顶点s的领接表
		g[s].next=p;

		q->next =g[d].next;//*q插入顶点d的领接表
		g[d].next=q;//**形成链表
	}
	
}

//打印邻接表
void dispgraph(adjList g ,int n ){
	int i;
	struct edgeNode *p;
	printf("图的邻接表:\n");
	for(i=1 ; i<=n ; i++){
		printf("[%d,%c] =>",i,g[i].data);//打印顶点
		p=g[i].next;
		while(p != NULL){//顶点下面的链表
			printf("(%d,%c) ->",p->adjvex,p->data);
			p=p->next;
		}
		printf("∧\n");
	}

}

//深度优先搜索 adj邻接表的图 ,v 顶点编号 , visited辅助数组
void dfs(adjList adj ,int v ,int visited[]){

	struct edgeNode *p;
	visited[v]=1;
	printf("[%d,%c] =>",v,adj[v].data); //取链的头元素
	p=adj[v].next;
	while(p != NULL){
		//寻找未找到的顶点
		if(visited[p->adjvex]  == 0 ) dfs(adj,p->adjvex,visited);//递归深度优先遍历
		p=p->next;//指向下一个结点
		
	}
}

int queue[MaxVex];
//广度优先搜索
void bfs(adjList adj,int vi, int visited[]){
	int front =0 ,rear=1, v;
	struct edgeNode *p;
	visited[vi]=1;//访问初始顶点
	printf("[%d,%c] ",vi,adj[vi].data); //取链的头元素
	queue[rear]=vi;//初始顶点队列
	while(front != rear){
		front =(front +1) % MaxVex;
		v=queue[front];//按访问次序依次出队列
		p=adj[v].next;//v的邻接点
		while(p != NULL){
			if(visited[p->adjvex] == 0){
				visited[p->adjvex]=1;
				printf("[%d,%c] ",p->adjvex,adj[p->adjvex].data); //入队列
				rear = (rear+1) % MaxVex;
				queue[rear] = p->adjvex;
			}
			p=p->next;// 找v的下一个邻接点
		}
	}
}

void main(){
	adjList g;
	int n, visited[MaxVex],i;
	creagraph(g,&n);
	dispgraph(g,n);
	for(i=1;i<=n;i++)visited[i]=0;
	printf("图的深度优先搜索dfs结果:\n");
	dfs(g,1,visited);
	
	for(i=1;i<=n;i++)visited[i]=0;
	printf("\n图的广度优先搜索bfs结果:\n");
	bfs(g,1,visited);
	
	
}

 

测试结果

D:\C++WorkSpace\DFS\Debug>DFS.exe
结点数(n),边数(e)5,7
第1个结点信息:1
第2个结点信息:2
第3个结点信息:3
第4个结点信息:4
第5个结点信息:5
第1条边起点,终点序号:1,2
第2条边起点,终点序号:2,3
第3条边起点,终点序号:1,5
第4条边起点,终点序号:5,3
第5条边起点,终点序号:5,4
第6条边起点,终点序号:2,4
第7条边起点,终点序号:4,3
图的邻接表:
[1,1] =>(5,5) ->(2,2) ->∧
[2,2] =>(4,4) ->(3,3) ->(1,1) ->∧
[3,3] =>(4,4) ->(5,5) ->(2,2) ->∧
[4,4] =>(3,3) ->(2,2) ->(5,5) ->∧
[5,5] =>(4,4) ->(3,3) ->(1,1) ->∧
图的深度优先搜索dfs结果:
[1,1] =>[5,5] =>[4,4] =>[3,3] =>[2,2] =>
图的广度优先搜索bfs结果:
[1,1] [5,5] [2,2] [4,4] [3,3]

 

© 著作权归作者所有

共有 人打赏支持
ashuo
粉丝 4
博文 63
码字总数 46928
作品 0
浦东
程序员
私信 提问
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0
深度优先搜索遍历与广度优先搜索遍历

深度优先遍历过程 1、图的遍历 和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历...

长平狐
2013/01/06
1K
0
JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名
2018/05/31
0
0
图的广度优先和深度优先遍历(BFS和DFS)

图是一种灵活的数据结构,一般作为一种模型用来定义对象之间的关系或联系。对象由顶点()表示,而对象之间的关系或者关联则通过图的边()来表示。 图可以分为有向图和无向图,一般用来表示...

Shuqing,Wang
2017/12/14
0
0
JavaScript 算法与数据结构

本仓库包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中组织和存储数据的...

a独家记忆
2018/06/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL的分表与分区

MySQL分表分区是解决大数据量导致MySQL性能低下的两种方法。 什么是MySQL分表 从表面意思上看,MySQL分表就是将一个表分成多个表,数据和数据结构都有可能会变。MySQL分表分为垂直分表和水平...

吴伟祥
23分钟前
1
0
MySQL查询执行

当我们希望MySQL能够以更高的性能运行查询时,最好的办法就是弄清楚MySQL是如何优化和执行查询的。一旦理解了这一点,很多查询优化工作实际上就是遵循一些原则让优化器能够按照预想的合理方式...

问题终结者
今天
1
0
CDH5动静态资源池配置与回滚

关于动态 静态资源池的配置以前都有提过,可以从以下几篇了解: YARN动态资源池配置案例 https://yq.aliyun.com/ziliao/346856# Hadoop YARN配置参数剖析(4)—Fair Scheduler相关参数 Hadoop...

hblt-j
今天
3
0
WordPress仿站实战教程

有一个月没有写blog了,一直在学习wordpress的知识,现在能够进行简单的政府企业门户网站的仿制,wordpress的主题订制,一般是对前端要求比较高,wordpress学会了,建站还是非常的快的。下面...

临江仙卜算子
今天
4
0
图像库stb_image

https://github.com/nothings/stb 目前一般主流的图像格式也就是bmp,jpg,png,tga,dds,除了DDS一般是给DX用的,虽然一堆OpenGL程序也有用的,但是我一般只用png和tga, png不用说了,带a...

robslove
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部