文档章节

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

ashuo
 ashuo
发布于 10/22 17:56
字数 795
阅读 9
收藏 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
博文 62
码字总数 40987
作品 0
浦东
程序员
私信 提问
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

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

安然若知
07/13
0
0
JavaScript 算法与数据结构 - javascript-algorithms

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

匿名
05/31
0
0
深度优先搜索遍历与广度优先搜索遍历

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

长平狐
2013/01/06
1K
0
图的广度优先和深度优先遍历(BFS和DFS)

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

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

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

a独家记忆
06/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

利用cefSharp实现网页自动注册登录的需要注册的一些事项

最近朋友有个需要自动注册登录点击的事,我帮着写了写,好久没写过这东西了,在写的过程中总结了需要注意的一些事项。 一、换IP之后要测试一下速度,我目前用的最简单的测试方法就是20-30秒加...

我退而结网
33分钟前
1
0
Go语言中使用 BoltDB数据库

boltdb 是使用Go语言编写的开源的键值对数据库,Github的地址如下: https://github.com/boltdb/bolt boltdb 存储数据时 key 和 value 都要求是字节数据,此处需要使用到 序列化和反序列化。...

Oo若离oO
33分钟前
1
0
zookeeper分布式锁

//lock 锁 定义分布式锁public interface Lock {//获取锁public void getLock();//释放锁public void unLock();} public abstract class ZookeeperAbstractLock implements Loc......

熊猫你好
41分钟前
0
0
mysql_事务隔离机制

事务隔离机制 事务就是要保证一组数据库操作,要么全部成功,要么全部失败。在mysql中,事务支持是在引擎层实现的。mysql是一个支持多引擎的系统,但并不是所有引擎都支持事务,比如mysql...

grace_233
43分钟前
0
0
不学无数——Java中IO和NIO

JAVA中的I/O和NIO I/O 问题是任何编程语言都无法回避的问题,可以说 I/O 问题是整个人机交互的核心问题,因为 I/O 是机器获取和交换信息的主要渠道。在当今这个数据大爆炸时代,I/O 问题尤其...

不学无数的程序员
49分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部