C++无向图构造与深度优先遍历

Question

遍历的时候只会出现1

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

#define MAX_VERTEX_NUM 20

typedef int Infotype;
typedef int VertexType;

// 邻接表表示无向图
typedef struct ArcNode{
    int adjvex;
    struct ArcNode* nextarc;
    Infotype *info;
}ArcNode;
typedef struct VNode{
    VertexType data;
    ArcNode*firstarc;
}VNode,AdjList;
typedef struct{
    AdjList vertices[MAX_VERTEX_NUM];
    int vexnum,arcnum;
}UDG;
// 邻接表表示无向图

//构造无向图
void CreateUDG(UDG* udg){
    int vx,ac,dat;
    vx=0;
    ac=0;
    dat=0;
    printf("vexnum:");
    scanf("%d",&vx);
    udg->vexnum=vx;
    udg->arcnum=0;
    for(int i=0;i<vx;i++){
        udg->vertices[i].firstarc=NULL;
        printf("v%d:arcnum,data:",i);
        scanf("%d,%d",&ac,&dat);
        udg->vertices[i].data=dat;
        udg->arcnum+=ac;
        ArcNode* p;
        for(int j=0;j<ac;j++){
            p=(ArcNode*)malloc(sizeof(ArcNode));
            //输入边信息
            int adj,dat;
            printf("adjvex:");
            scanf("%d",&adj);
            p->adjvex=adj;
            p->nextarc=udg->vertices[i].firstarc;
            p->info=NULL;
            udg->vertices[i].firstarc=p;
        }
    }
    printf("Done!");
}
//构造无向图

//深度遍历无向图
void UDG_DFS_traverse(UDG udg,void(*visit)(VNode*)){ //可以换一个遍历函数
    void udg_dfs(UDG* udg,int v,int** visited,void(*visit)(VNode*));
    int visited[udg.vexnum];
    for(int i=0;i<udg.vexnum;i++){
        visited[i]=0;
    }
    for(int i=0;i<udg.vexnum;i++){
        if(visited[i]==0){
            udg_dfs(&udg.vertices[i],i,&visited,visit);
        }
    }
}

void udg_dfs(UDG* udg,int v,int** visited,void(*visit)(VNode*)){
    (*visit)(&udg->vertices[v]);
    *visited[v]=1;
    for(ArcNode* a=udg->vertices[v].firstarc;a;a=a->nextarc){
        if(*visited[a->adjvex]==0){
            udg_dfs(udg,a->adjvex,&visited,visit);
        }
    }
}

void traverse(VNode* v){
    printf("%d,",v->data);
}
//深度遍历无向图


int main(int argc,char** argv){
    UDG* udg=(UDG*)malloc(sizeof(UDG));
    CreateUDG(udg);
    UDG_DFS_traverse(*udg,traverse);
}

Answer 1

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

#define MAX_VERTEX_NUM 20

typedef int Infotype;
typedef int VertexType;

// 邻接表表示无向图
typedef struct ArcNode {
    int adjvex;
    struct ArcNode* nextarc;
    Infotype* info;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode* firstarc;
} VNode;

typedef struct {
    VNode vertices[MAX_VERTEX_NUM];
    int vexnum, arcnum;
} UDG;

//构造无向图
void CreateUDG(UDG* udg) {
    size_t vx, ac;
    VertexType dat;
    printf("vexnum:");
    scanf("%zu", &vx);
    udg->vexnum = vx;
    udg->arcnum = 0;
    for (int i = 0; i < vx; i++) {
        udg->vertices[i].firstarc = NULL;
        printf("v%d:arcnum,data:", i);
        scanf("%zu,%d", &ac, &dat);
        udg->vertices[i].data = dat;
        udg->arcnum += ac;
        ArcNode* p;
        for (int j = 0; j < ac; j++) {
            p = (ArcNode*)malloc(sizeof(ArcNode));
            //输入边信息
            int adj;
            printf("adjvex:");
            scanf("%d", &adj);
            p->adjvex = adj;
            p->nextarc = udg->vertices[i].firstarc;
            p->info = NULL;
            udg->vertices[i].firstarc = p;
        }
    }
    printf("Done!\n");
}

//深度遍历无向图
void UDG_DFS_traverse(UDG udg, void (*visit)(VertexType*)) {
    void udg_dfs(UDG* udg, int v, bool* visited, void (*visit)(VertexType*));
    bool visited[udg.vexnum];
    for (int i = 0; i < udg.vexnum; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < udg.vexnum; i++) {
        if (!visited[i]) {
            udg_dfs(&udg, i, visited, visit);
        }
    }
}

void udg_dfs(UDG* udg, int v, bool* visited, void (*visit)(VertexType*)) {
    visit(&udg->vertices[v].data);
    visited[v] = true;
    for (ArcNode* a = udg->vertices[v].firstarc; a; a = a->nextarc) {
        if (!visited[a->adjvex]) {
            udg_dfs(udg, a->adjvex, visited, visit);
        }
    }
}

void traverse(VertexType* v) {
    printf("%d,", *v);
}

int main() {
    UDG udg;
    CreateUDG(&udg);
    UDG_DFS_traverse(udg, traverse);
    return 0;
}