有向图的深度优先搜索

Question

样例输出应该是yes,但是输出no
样例如下：
4 4（结点数，边数）
1 2 3 4（顶点下标）
1 2（边信息）
1 3
1 4
2 3
2 3（要搜索是否存在的边信息）
以下是代码

#include <stdio.h>
#include <stdlib.h>
int visited[105];
typedef struct EdgeNode//边结点
{
    int adjvex;
    struct EdgeNode *next;
}edge;
typedef struct vertexnode//临界点
{
    int data;
    edge* firstedge;
}vertexnode,Adjlist[105];
typedef struct LGraph//图
{
    int edgenum,nodenum;
    Adjlist adjlist;
}LGraph;
LGraph* creategraph( )//创建图
{
    LGraph*G=(LGraph*)malloc(sizeof(LGraph));
    scanf("%d %d\n",&(G->nodenum),&(G->edgenum));
    int i,j;
    for(i=1;i<=(G->nodenum);i++)//填充顶点表
    {
        int temp;
        scanf("%d",&temp);
        G->adjlist[i].data=temp;
        G->adjlist[i].firstedge=NULL;//勿漏
    }
    for(j=1;j<=(G->edgenum);j++)//填充边表
    {
        int temp1,temp2;
        scanf("%d %d\n",&temp1,&temp2);//读入有向边的”入“，”出“
        edge*e=(edge*)malloc(sizeof(edge));
        e->adjvex=temp1;
        e->next=G->adjlist[temp2].firstedge;//头插法
        G->adjlist[temp2].firstedge=e;
    }
    return G;
}
int FLAG=0;//判断是否能通过v2的标志，全局变量
void DFS(LGraph*G,int adjvex,int v2)//深度搜索
{
    edge*p;
     visited[adjvex]=1;//标记已经访问过
    p=G->adjlist[adjvex].firstedge;
    if(visited[v2]==1) FLAG=1;
    while(p)
    {
        if(visited[adjvex]==0)
        DFS(G,p->adjvex,v2);
        p=p->next;
    }
}
int DFSTraverse(LGraph *G,int v1,int v2)
{
    int i;
    for(i=1;i<=(G->nodenum);i++)//首先都初始化为未访问过的状态
    {
        visited[i]=0;
    }
        DFS(G,v1,v2);//从v1点开始深度搜索
    return FLAG;
}

int main()
{
    LGraph*G;
    G=creategraph();
    int v1,v2,flag=0;
    scanf("%d %d",&v1,&v2);//要寻找的路径的两端下标
    flag=DFSTraverse(G,v1,v2);
    if(flag==1)
        printf("yes");
    else
        printf("no");
    return 0;
}

Answer 1

你题目的解答代码如下：

#include <stdio.h>
#include <stdlib.h>
int visited[105];
typedef struct EdgeNode//边结点
{
    int adjvex;
    struct EdgeNode *next;
}edge;
typedef struct vertexnode//临界点
{
    int data;
    edge* firstedge;
}vertexnode,Adjlist[105];
typedef struct LGraph//图
{
    int edgenum,nodenum;
    Adjlist adjlist;
}LGraph;
LGraph* creategraph( )//创建图
{
    LGraph*G=(LGraph*)malloc(sizeof(LGraph));
    scanf("%d %d\n",&(G->nodenum),&(G->edgenum));
    int i,j;
    for(i=1;i<=(G->nodenum);i++)//填充顶点表
    {
        int temp;
        scanf("%d",&temp);
        G->adjlist[i].data=temp;
        G->adjlist[i].firstedge=NULL;//勿漏
    }
    for(j=1;j<=(G->edgenum);j++)//填充边表
    {
        int temp1,temp2;
        scanf("%d %d\n",&temp1,&temp2);//读入有向边的”入“，”出“
        edge*e=(edge*)malloc(sizeof(edge));
        // 有向边的”入“，”出“弄反正了
        e->adjvex=temp2;     //temp1改成temp2
        e->next=G->adjlist[temp1].firstedge;//头插法  temp2改成temp1
        G->adjlist[temp1].firstedge=e;             //temp2改成temp1
    }
    return G;
}
int FLAG=0;//判断是否能通过v2的标志，全局变量
void DFS(LGraph*G,int adjvex,int v2)//深度搜索
{
    edge*p;
    visited[adjvex]=1;//标记已经访问过
    p=G->adjlist[adjvex].firstedge;
    if(visited[v2]==1) FLAG=1;
    while(p)
    {
        if(visited[p->adjvex]==0)      //adjvex 改成 p->adjvex
            DFS(G,p->adjvex,v2);
        p=p->next;
    }
}
int DFSTraverse(LGraph *G,int v1,int v2)
{
    int i;
    for(i=1;i<=(G->nodenum);i++)//首先都初始化为未访问过的状态
    {
        visited[i]=0;
    }
        DFS(G,v1,v2);//从v1点开始深度搜索
    return FLAG;
}

int main()
{
    LGraph*G;
    G=creategraph();
    int v1,v2,flag=0;
    scanf("%d %d",&v1,&v2);//要寻找的路径的两端下标
    flag=DFSTraverse(G,v1,v2);
    if(flag==1)
        printf("yes");
    else
        printf("no");
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!