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

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

#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;
}