鍍金池/ 問(wèn)答/C  Linux/ C語(yǔ)言實(shí)現(xiàn)深度優(yōu)先搜索過(guò)程中的一個(gè)問(wèn)題?

C語(yǔ)言實(shí)現(xiàn)深度優(yōu)先搜索過(guò)程中的一個(gè)問(wèn)題?

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define V_NUM 10        //定義頂點(diǎn)個(gè)數(shù)為10

typedef struct node {
    int num;
    int index;
    struct node *next;
} Node;                //定義頂點(diǎn)

typedef struct {
    Node **v_arr;       //鄰接表
    int size;           //圖的大小,(頂點(diǎn)的個(gè)數(shù)),等于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;              //建立圖,頂點(diǎn)內(nèi)填入隨機(jī)數(shù)
                g->v_arr[i]->index=i;                    //頂點(diǎn)的索引
                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)              //將對(duì)3同余的頂點(diǎn)連起來(lái),并連接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 *))            //深度優(yōu)先遍歷(遞歸),但是只有與0號(hào)頂點(diǎn)相連才能被訪問(wèn)到,為什么?
{
    __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;
}

這段代碼運(yùn)行時(shí)出現(xiàn)了問(wèn)題,只有與0號(hào)頂點(diǎn)相連的頂點(diǎn)才能被訪問(wèn)到,請(qǐng)好心人幫忙指出問(wèn)題。

回答
編輯回答
只愛(ài)你

是我在創(chuàng)建圖的時(shí)候出錯(cuò)了,鄰接鏈表里的節(jié)點(diǎn)并非圖的頂點(diǎn)

2017年8月5日 03:03