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

基于图的深度/广度优先搜索策略(邻接表的创建与深搜/广搜)

程序员文章站 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;
}