欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 19:06:33
...
#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]

 

转载于:https://my.oschina.net/saulc/blog/2250844