Great Big Storm 2022-05-31 22:55 采纳率: 57.1%
浏览 47
已结题

有向图的深度优先搜索

样例输出应该是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;
}

  • 写回答

2条回答 默认 最新

  • 关注

    你题目的解答代码如下:

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

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

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 6月9日
  • 已采纳回答 6月1日
  • 创建了问题 5月31日

悬赏问题

  • ¥15 App的会员连续扣费
  • ¥15 不同数据类型的特征融合应该怎么做
  • ¥15 用proteus软件设计一个基于8086微处理器的简易温度计
  • ¥15 用联想小新14Pro
  • ¥15 multisim中关于74ls192n和DSWPK开关仿真图分析(减法计数器)
  • ¥15 基于8255的交通灯设计
  • ¥15 w3wp,exe 中发生未处理的 Microsoft ,NETFramework 异常。
  • ¥20 C51单片机程序及仿真(加减器)
  • ¥15 AQWA | 水动力分析 二阶波浪力
  • ¥15 c语言题目:成绩管理系统