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

为什么80%的码农都做不了架构师？>>>   

#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