数据结构图的基本功能和遍历

Question

请大家帮帮忙，为什么遍历不出结果。我想要他输出深度遍历和广度遍历之后的结果

#include<stdio.h>
#include<stdlib.h>
#include"file.h"
#include"队列.h"
typedef int VertexType;
typedef int InfoType;  
typedef int VRType;
typedef enum{unvisited,visited}VisitIf;
typedef struct EBox{
    VisitIf mark;
    int ivex,jvex;
    struct EBox *ilink,*jlink;
    InfoType *info;
    int weight;//边的权值 
}EBox;
typedef struct VexBox{
    VertexType data;
    EBox *firstedge;
}VexBox;
typedef struct{
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum,edgenum;
}AMLGraph;
// 查找顶点在图中的位置（索引）
int LocateVex(AMLGraph G,int v)
{    int num;
    for(num=0;num<G.vexnum;num++)
    {    if(v==G.adjmulist[num].data)
        return num;
    }
    return -1;

}
// 创建图函数，根据顶点集V和边关系VR构建图
void CreateGraph(AMLGraph &G)
{    int i,j,k,vi,vj,aweight;
    EBox *p; 
    printf("请输入图的顶点数和边数：");
    scanf("%d %d",&G.vexnum,&G.edgenum);
    printf("请依次输入顶点的值：\n");
    for(i=0;i<G.vexnum;i++)
    {    printf("请输入第%d个顶点的值：",i+1); 
        scanf("%d",&G.adjmulist[i].data);
        G.adjmulist[i].firstedge=NULL;
    }
    printf("请依次输入边的信息：\n");
    for(k=0;k<G.edgenum;k++) 
    {    scanf("%d %d %d",&vi,&vj,&aweight);//得到边的两个端点的值和权值 
        i=LocateVex(G,vi);
        j=LocateVex(G,vj);//确定两个端点在g中的位置 
        p=(EBox *)malloc(sizeof(EBox));
        if(!p)
        exit(1);
        p->mark=unvisited;
        p->ivex=i;
        p->jvex=j;
        p->weight=aweight;
        p->ilink=G.adjmulist[i].firstedge;
        G.adjmulist[i].firstedge=p;
        p->jlink=G.adjmulist[j].firstedge;
        G.adjmulist[j].firstedge=p;
    }
    
}
// 销毁图函数，释放邻接多重表占用的内存空间
void DestroyGraph(AMLGraph &G) {
    for (int i = 0; i < G.vexnum; i++) {
        EBox* edge = G.adjmulist[i].firstedge;
        while (edge!= NULL) {
            EBox* next = edge->ilink;
            if (edge->ilink == edge) {
                next = edge->jlink;
            }
            free(edge);
            edge = next;
        }
    }
    G.vexnum = 0;
    G.edgenum = 0;
}

// 获取指定顶点的数据
VertexType GetVex(AMLGraph G, int v) {
    if (v >= 0 && v < G.vexnum) {
        return G.adjmulist[v].data;
    }
    // 此处可根据需求返回错误值或者进行错误处理等，暂返回默认构造的顶点类型值
    return (VertexType){0};
}
// 设置指定顶点的数据为新值
void PutVex(AMLGraph &G, int v, VertexType value) {
    if (v >= 0 && v < G.vexnum) {
        G.adjmulist[v].data = value;
    }
    // 可添加错误提示等逻辑，这里暂省略
}
// 获取指定顶点的第一个邻接顶点的索引
int FirstAdjVex(AMLGraph G, int v) {
    if (v >= 0 && v < G.vexnum) {
        EBox *edge = G.adjmulist[v].firstedge;
        if (edge!= NULL) {
            return (edge->ivex == v)? edge->jvex : edge->ivex;
        }
    }
    return -1;
}
// 获取指定顶点相对于另一个邻接顶点的下一个邻接顶点索引
int NextAdjVex(AMLGraph G, int v, int w) {
    if (v >= 0 && v < G.vexnum && w >= 0 && w < G.vexnum) {
        EBox *edge = G.adjmulist[v].firstedge;
        while (edge!= NULL) {
            if ((edge->ivex == v && edge->jvex == w) || (edge->ivex == w && edge->jvex == v)) {
                if (edge->ilink!= NULL && edge->ilink!= edge) {
                    return (edge->ilink->ivex == v)? edge->ilink->jvex : edge->ilink->ivex;
                }
                if (edge->jlink!= NULL && edge->jlink!= edge) {
                    return (edge->jlink->ivex == v)? edge->jlink->jvex : edge->jlink->ivex;
                }
            }
            edge = edge->ilink;
            if (edge == NULL && edge == edge->jlink) {
                edge = edge->jlink;
            }
        }
    }
    return -1;
}
// 插入一个新顶点到图中
void InsertVex(AMLGraph &G, VertexType v) {
    if (G.vexnum < MAX_VERTEX_NUM) {
        G.adjmulist[G.vexnum].data = v;
        G.adjmulist[G.vexnum].firstedge = NULL;
        G.vexnum++;
    }
    // 可添加图已满等错误处理逻辑，这里暂省略
}
// 删除指定顶点以及与之相关的边
void DeleteVex(AMLGraph &G, int v) {
    if (v >= 0 && v < G.vexnum) {
        // 先释放与该顶点相连的边
        EBox *edge = G.adjmulist[v].firstedge;
        while (edge!= NULL) {
            EBox *next = edge->ilink;
            if (edge->ilink == edge) {
                next = edge->jlink;
            }
            free(edge);
            edge = next;
        }
        // 将后面顶点往前移覆盖要删除的顶点位置
        for (int i = v; i < G.vexnum - 1; i++) {
            G.adjmulist[i] = G.adjmulist[i + 1];
        }
        G.vexnum--;
        // 更新其他顶点相关边中涉及该顶点的索引等信息（较复杂，这里简化示意未完整实现）
        for (int i = 0; i < G.vexnum; i++) {
            EBox *curEdge = G.adjmulist[i].firstedge;
            while (curEdge!= NULL) {
                if (curEdge->ivex > v) {
                    curEdge->ivex--;
                }
                if (curEdge->jvex > v) {
                    curEdge->jvex--;
                }
                curEdge = curEdge->ilink;
                if (curEdge == NULL && curEdge == curEdge->jlink) {
                    curEdge = curEdge->jlink;
                }
            }
        }
    }
    // 可添加错误处理逻辑，这里暂省略
}
// 插入一条边（弧）到图中
void InsertArc(AMLGraph &G, int v, int w,int weight) {
    printf("InsertArc函数，传入顶点v: %d, 顶点w: %d\n", v, w);
    if (v >= 0 && v < G.vexnum && w >= 0 && w < G.vexnum) {
        EBox *newEdge = (EBox *)malloc(sizeof(EBox));
        newEdge->mark = unvisited;
        newEdge->ivex = v;
        newEdge->jvex = w;
        newEdge->ilink = G.adjmulist[v].firstedge;
        newEdge->jlink = G.adjmulist[w].firstedge;
        newEdge->weight=weight;
        newEdge->info = NULL;  // 假设暂时无额外信息，可按需赋值
        G.adjmulist[v].firstedge = newEdge;
        G.adjmulist[w].firstedge = newEdge;
        G.edgenum++;
    }
    // 可添加错误处理逻辑，如顶点不存在等情况，这里暂省略
}
// 删除指定的边（弧）
void DeleteArc(AMLGraph &G, int v, int w) {
    if (v >= 0 && v < G.vexnum && w >= 0 && w < G.vexnum) {
        EBox *prevV = NULL;
        EBox *edgeV = G.adjmulist[v].firstedge;
        while (edgeV!= NULL && ((edgeV->ivex!= v || edgeV->jvex!= w) && (edgeV->ivex!= w || edgeV->jvex!= v))) {
            prevV = edgeV;
            edgeV = edgeV->ilink;
            if (edgeV == NULL && edgeV == edgeV->jlink) {
                edgeV = edgeV->jlink;
            }
        }
        if (edgeV!= NULL) {
            if (prevV == NULL) {
                G.adjmulist[v].firstedge = edgeV->ilink;
            } else {
                prevV->ilink = edgeV->ilink;
            }

            prevV = NULL;
            EBox *edgeW = G.adjmulist[w].firstedge;
            while (edgeW!= NULL && ((edgeW->ivex!= v || edgeW->jvex!= w) && (edgeW->ivex!= w || edgeW->jvex!= v))) {
                prevV = edgeW;
                edgeW = edgeW->ilink;
                if (edgeW == NULL && edgeW == edgeW->jlink) {
                    edgeW = edgeW->jlink;
                }
            }
            if (edgeW!= NULL) {
                if (prevV == NULL) {
                    G.adjmulist[w].firstedge = edgeW->ilink;
                } else {
                    prevV->ilink = edgeW->ilink;
                }
            }
            free(edgeV);
            G.edgenum--;
        }
    }
    // 可添加错误处理逻辑，这里暂省略
}
void DFS(AMLGraph *G, int v) {
    EBox *e;
    G->adjmulist[v].firstedge->mark = visited;
    printf("%d ", G->adjmulist[v].data);
    for (e = G->adjmulist[v].firstedge; e != NULL; e = e->ilink) {
        if (e->mark == unvisited) {
            DFS(G, e->ivex);
        }
    }
}

// 深度优先遍历函数
void DFSTraverse(AMLGraph *G) {
    int v;
    for (v = 0; v < G->vexnum; v++) {
        G->adjmulist[v].firstedge->mark = unvisited;
    }
    for (v = 0; v < G->vexnum; v++) {
        if (G->adjmulist[v].firstedge->mark == unvisited) {
            DFS(G, v);
        }
    }
}
void visit(VertexType v) {
    printf("%d", v);
}

int main() {
    AMLGraph G;
    CreateGraph(G);
    printf("图创建成功，当前图的顶点数: %d，边数: %d\n", G.vexnum, G.edgenum);
    // 获取并打印某个顶点的数据
    int vertexIndex = 0;
    VertexType vertexData = GetVex(G, vertexIndex);
    printf("顶点 %d 的数据为: %d\n", vertexIndex, vertexData);

    // 插入一个新顶点
    int v, v1, v2;
    printf("插入新结点的值：");
    scanf("%d", &v);
    InsertVex(G, v);
    printf("插入新顶点后，图的顶点数: %d\n", G.vexnum);
    printf("插入的新边的起点和终点以及权重分别是：");
    scanf("%d %d %d", &v1, &v2, &vertexData);
    InsertArc(G, v1, v2, vertexData);
    printf("插入边后，图的边数: %d\n", G.edgenum);
    // 深度优先遍历图
    printf("深度优先遍历：");
    DFSTraverse(&G);
    printf("广度优先遍历：");
//BFS(&G,0); 

    // 删除一个顶点及相关边
    int vertexToDelete = 0;
    DeleteVex(G, vertexToDelete);
    printf("删除顶点后，图的顶点数: %d，边数: %d\n", G.vexnum, G.edgenum);

    // 删除一条边
    int edgeV1 = 1, edgeV2 = 2;
    DeleteArc(G, edgeV1, edgeV2);
    printf("删除边后，图的边数: %d\n", G.edgenum);

    // 销毁图
    DestroyGraph(G);
    printf("图已销毁\n");

    return 0;
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

看起来你的代码主要实现了图的创建、插入顶点、插入边、删除顶点、删除边以及深度优先遍历等基本功能。但你的程序在运行深度优先遍历之后停止并返回错误代码的问题可能源于几个地方。我将基于你的代码给出一些可能的解决方案。

首先，深度优先遍历函数DFSTraverse中，你遍历了所有的顶点并标记为已访问，但是你没有提供递归调用的逻辑。你需要使用递归来实现深度优先遍历。以下是修改后的深度优先遍历函数：

void DFS(AMLGraph *G, int v) {
    printf("%d ", G.adjmulist[v].data); // 打印当前访问的顶点
    EBox *e;
    for (e = G.adjmulist[v].firstedge; e != NULL; e = e->ilink) {
        if (e->mark == unvisited) { // 如果相邻顶点未被访问，则进行递归访问
            DFS(G, e->ivex);
        }
    }
    e->mark = visited; // 将当前顶点标记为已访问
}

void DFSTraverse(AMLGraph *G) { // 注意这里没有传入v参数，因为在主函数中需要调用每个未访问的顶点进行遍历
    for (int v = 0; v < G.vexnum; v++) { // 对于每个顶点，开始深度优先遍历
        if (G.adjmulist[v].firstedge != NULL && G.adjmulist[v].firstedge->mark == unvisited) { // 如果顶点存在且未被访问过，则开始遍历
            DFS(G, v); // 从当前顶点开始深度优先遍历
        }
    }
}

其次，在图的深度优先遍历过程中，如果图的数据结构没有被正确初始化或者图的构建过程中存在问题（例如插入的边没有被正确连接），那么在遍历过程中可能会出现未定义的行为。请确保图的数据结构被正确初始化并且所有的边都被正确连接。如果图的结构存在问题，你需要检查图的创建和编辑函数（如CreateGraph, InsertArc等）。确保所有的顶点和边都被正确地插入和连接。

最后，如果你的编译器或运行环境有特殊的需求（例如内存管理或线程管理等），这也可能影响程序的运行。请确保你的运行环境满足程序的需求。如果问题仍然存在，你可能需要调试你的代码来找到具体的问题所在。