数据结构(算法)-图(深度优先搜索 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
上一篇: C#图与图的算法之广度优先遍历
下一篇: 笑话集原创笑话精品展第七十一期
推荐阅读
-
python数据结构之图深度优先和广度优先实例详解
-
python深度优先搜索和广度优先搜索
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
数据结构与算法-----BFS与DFS(广度优先搜索与深度优先搜索)
-
数据结构与算法_深度优先搜索(DFS)与广度优先搜索(BFS)详解
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
Java数据结构与算法——深度优先搜索与广度优先搜索
-
数据结构与算法——广度和深度优先搜索