有向图的广度优先搜索

Question

输入

样例如下：
4 4（有向图的结点数，边数）
1 2 3 4（顶点信息）
1 2（边信息）
1 3
1 4
2 1
2 4（要搜索路径是否存在的边信息）
实际输出：no
应输出：yes
应该是代码只能检索一层”右兄弟”导致的
以下是代码

#include <stdio.h>
#include <stdlib.h>
int visited[105];
typedef struct edge
{
    int adjvex;
    struct edge* next;
}edge;
typedef struct vertexnode
{
   int data;
   edge* firstedge;
}vnode,adjlist[105];
typedef struct graph
{
    int vm,em;
    adjlist a;
}LGraph;
LGraph* creategraph( )
{
    int i;
    int em,vm;
    LGraph*G=(LGraph*)malloc(sizeof(LGraph));
    scanf("%d %d\n",&vm,&em);
    G->em=em;
    G->vm=vm;
    for(i=1;i<=vm;i++)
    {
        int temp;
        scanf("%d",&temp);
        G->a[temp].data=temp;
        G->a[temp].firstedge=NULL;
        visited[temp]=0;
    }
    for(i=1;i<=em;i++)
    {
      int v1,v2;
      scanf("%d %d\n",&v1,&v2);
      edge*e=(edge*)malloc(sizeof(edge));
      e->adjvex=v2;
      e->next=G->a[v1].firstedge;
      G->a[v1].firstedge=e;
    }
    return G;
}
typedef struct queue
{
    int q[105];
    int front,rear;
}queue;
queue* createqueue()
{
    queue*Q;
    Q=(queue*)malloc(sizeof(queue));
    Q->front=0;
    Q->rear=0;
    return Q;
}
void enqueue(queue*paqu,int x)
{
    paqu->q[paqu->rear]=x;
    paqu->rear=((paqu->rear)+1)%105;
}
void dequeue(queue*paqu)
{
   paqu->front=((paqu->front)+1)%105;
}
int isempty(queue*paqu)
{
    return(paqu->front==paqu->rear);
}
int FLAG=0;
void BFS(LGraph*G,int v1,int v2)
{
    edge*p;
    queue*Q;
    Q=createqueue();
    visited[v1]=1;
    enqueue(Q,v1);
    int temp=v1;
    while(!isempty(Q))
    {
        dequeue(Q);
        p=G->a[temp].firstedge;
        while(p!=NULL)
        {
            if(visited[p->adjvex]!=1)
            {
                visited[p->adjvex]=1;
                if(v2==p->adjvex) FLAG=1;
                enqueue(Q,p->adjvex);
            }
            p=p->next;
        }
    }
}
int main()
{
    LGraph*G;
    G=creategraph();
    int v1,v2;
    scanf("%d %d",&v1,&v2);
    BFS(G,v1,v2);
    if(v1==v2)
        FLAG=1;
    if(FLAG==1)
        printf("yes");
    else
        printf("no");
    return 0;
}

Answer 1

题目中有边1->2, 1->3, 1->4 可以看出该图的出度可以用多个，但是在代码中的vertexnode, edge定义中。每个节点会连接一条边，每条边有指向一个next的边。这样每个节点都只有一个出度。在多个出度边的情况下会覆盖掉之前的出边。
可以重新考虑下结构的设计：

1. 节点和边职责分离，边有收尾两个节点组成。不应该直接连接一条边
2. 每个节点可以有多个边，可以将入边和出边分开，也可以在边中区分类型

下面是两处可能有问题的地方。

scanf("%d %d\n",&v1,&v2);
edge*e=(edge*)malloc(sizeof(edge));
e->adjvex=v2;
e->next=G->a[v1].firstedge; // 赋值无效，此时firstedge为初始值NULL,next并未更新
G->a[v1].firstedge=e;

if(visited[p->adjvex]!=1)
{
    visited[p->adjvex]=1;
    if(v2==p->adjvex) FLAG=1; // FLAG=1表示找到了路径，则可以直接返回。 无需继续添加边
    enqueue(Q,p->adjvex);
}

没法直接在代码基础上做更改，故只提供了思路。以供参考