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

有向图的深度优先搜索

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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 已结题 (查看结题原因) 5月31日
    • 创建了问题 5月31日

    悬赏问题

    • ¥15 程序实在不会写,要秃了
    • ¥15 pycharm导入不了自己的包
    • ¥15 C#.net通过内网url地址获取文件并下载问题,浏览器postman可以正常下载,用程序不行
    • ¥15 本人本科机械,目前研一。没有深度学习基础,目前对研究生课题一片迷茫,请教各位!
    • ¥15 关于R语言单因素与多因素线性回归的平均值
    • ¥15 服务器清除BIOS之后引导不了
    • ¥15 CPLEX用OPL编写的混合整数线性优化问题。
    • ¥15 可以用EasyConnect连接实验室内网,但无法连接内网才能访问的服务器,为什么?
    • ¥15 前端预览docx文件,文件从后端传送过来。
    • ¥15 层次聚类和蛋白质相似度