基于图的深度/广度优先搜索策略(邻接表的创建与深搜/广搜)
程序员文章站
2022-03-26 10:35:47
...
基于图的深度/广度优先搜索策略(邻接表的创建与深搜/广搜)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef struct ArcNode
{
int adjvex; //adjvex是整型,不是地址。也就是说邻接点域是元素
struct ArcNode *nextarc;
int info; //这个在本题中没用
}ArcNode;
typedef struct VertexNode
{
int Data; //这存起来的数据只有输出时才有用,不然也就存存,因为可用数组映射找表头结点
ArcNode* firstarc;
}VertexNode;
typedef struct
{
VertexNode vertex[100]; //数组
int vexnum, arcnum;
}AdjList;
int visit[100] = {0};
void CreateAdjList(AdjList* L,int vex,int arc)
{
(*L).vexnum = vex;
(*L).arcnum = arc;
int v1, v2, i;
for(i=1;i<= vex;i++)
{
scanf("%d",&(*L).vertex[i].Data);
(*L).vertex[i].firstarc = NULL;//一开始让每个结点链域都为空
}
for(i=1;i<=arc;i++)
{
scanf("%d%d",&v1,&v2);
ArcNode* q = (ArcNode*)malloc(sizeof(ArcNode));
q->adjvex = v2;
q->nextarc =(*L).vertex[v1].firstarc;
(*L).vertex[v1].firstarc = q; //这就是头插法啊,所以书上才会从大到小排列
} //这是以每个表头结点建立的n个结点的n条链
}
int DFS(AdjList L, int i, int j) //i代表表头结点i.
{
visit[i] = 1;
ArcNode *p = L.vertex[i].firstarc; //这步就已经从头结点到元素结点了
while(p) //由表头结点到弧结点来做。
{
if(p->adjvex == j)
return 1; //如果是查1到3的话,先1到5,判断5是否来过,然后5成为新的起始位置递归
else if((visit[p->adjvex]==0)&&DFS(L, p->adjvex, j)) //为什么要用visit,因为弧结点的adjvex可能是之前已经走过的表头结点,避免循环
return 1;
p=p->nextarc; //因为visit[p->adjvex]==0不一定成立,所以用这个枚举全部
}
return 0;
}
int BFS(AdjList L, int i, int j) //i代表表头结点i.//如果用广搜的话,那一定是最短路径
{
int que[100];
int head=1,tail=1;
memset(visit,0,sizeof(visit));
ArcNode* cur;
que[tail]=i;
tail++;
visit[i]=1;
while(head<tail)
{
cur=L.vertex[que[head]].firstarc;
while(cur)
{
if(visit[cur->adjvex]==0)
{
que[tail]=cur->adjvex;
if(que[tail]==j)
return 1;
tail++;
visit[cur->adjvex]=1;
}
cur=cur->nextarc;
}
head++;
}
return 0;
}
int main()
{
int m, n;
int v1,v2;
scanf("%d%d",&n,&m);
AdjList L;
CreateAdjList(&L,n,m);
scanf("%d%d",&v1,&v2);
int flag=DFS(L, v1, v2);
//int flag=BFS(L, v1, v2);
if(flag)
printf("yes\n");
else
printf("no\n");
return 0;
}
上一篇: 喷水装置(一) 贪心
下一篇: mne绘制脑地形图