账号密码登录
微信安全登录
微信扫描二维码登录

登录后绑定QQ、微信即可实现信息互通

手机验证码登录
找回密码返回
邮箱找回 手机找回
注册账号返回
其他登录方式
分享
  • 收藏
    X
    C语言实现深度优先搜索过程中的一个问题?
    20
    0
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    #define V_NUM 10        //定义顶点个数为10
    
    typedef struct node {
        int num;
        int index;
        struct node *next;
    } Node;                //定义顶点
    
    typedef struct {
        Node **v_arr;       //邻接表
        int size;           //图的大小,(顶点的个数),等于V_NUM
    } G;                   //图的邻接表表示
    
    void append(Node **l,Node *node)
    {
        Node *temp=*l;
        while(temp->next)
        {
            temp=temp->next;
        }
        temp->next=node;
    }
    
    void Init(G *g)
    {
        g->size=V_NUM;
        srand(time(NULL));
        if(g->v_arr=(Node **)malloc(V_NUM*sizeof(Node *)))
        {
            Node *temp;
            for(int i=0;i<V_NUM;i++)
            {
                if(g->v_arr[i]=(Node *)malloc(sizeof(Node)))
                {
                    g->v_arr[i]->num=rand()%15;              //建立图,顶点内填入随机数
                    g->v_arr[i]->index=i;                    //顶点的索引
                    g->v_arr[i]->next=NULL;
                }
                else
                {
                    printf("Init v error!\n");
                    exit(1);
                }
            }
            for(int i=0;i<V_NUM;i++)
            {
                for(int j=0;j<V_NUM;j++)
                {
                    if(((g->v_arr[i]->num-g->v_arr[j]->num)%3==0||(i==0&&j<3)||(i==1&&j==0)||(i==2&&j==0))&&i!=j)              //将对3同余的顶点连起来,并连接0-1,0-2(保证图连通)
                    {
                        if(temp=(Node *)malloc(sizeof(Node)))
                        {
                            temp->num=g->v_arr[j]->num;
                            temp->index=g->v_arr[j]->index;
                            temp->next=NULL;
                            append(&g->v_arr[i],temp);
                        }
                    }
                }
            }
        }
        else
        {
            printf("Init error!\n");
            exit(1);
        }
    }
    
    void visit(Node *node)
    {
        printf("%d--%d  ",node->index,node->num);
    }
    
    int visited[V_NUM]={0};
    
    void __traverse(Node *l,void (*visit)(Node *))
    {
        visit(l);
        visited[l->index]=1;
        Node *temp;
        for(temp=l->next;temp;temp=temp->next)
        {
            if(!visited[temp->index])
            {
                __traverse(temp,visit);
            }
        }
    }
    
    void traverse(G *g,void (*visit)(Node *))            //深度优先遍历(递归),但是只有与0号顶点相连才能被访问到,为什么?
    {
        __traverse(g->v_arr[0],visit);
    }
    
    int main(void)
    {
        G g;
        Init(&g);
        for(int i=0;i<V_NUM;i++)
        {
            for(Node *temp=g.v_arr[i];temp;temp=temp->next)
            {
                printf("%d--%d  ",temp->index,temp->num);
            }
            putchar('\n');
        }
        putchar('\n');
        traverse(&g,visit);
        putchar('\n');
        for(int i=0;i<V_NUM;i++)
        {
            printf("%d  ",visited[i]);
        }
        putchar('\n');return 0;
    }

    这段代码运行时出现了问题,只有与0号顶点相连的顶点才能被访问到,请好心人帮忙指出问题。

    0
    打赏
    收藏
    点击回答
        全部回答
    • 0
    • 喪风 普通会员 1楼

      在深度优先搜索(DFS)过程中,可能会出现问题,比如一些节点可能已经被访问过,或者可能无法访问。这些问题可以通过在深度优先搜索时添加一个标记变量来解决。此外,还可以使用记忆化搜索技术来避免重复搜索。

    更多回答
    扫一扫访问手机版
    • 回到顶部
    • 回到顶部