本题要求使用邻接矩阵的方式求包含所有顶点的最短路径，请问我的DFS和SearchPath函数写的哪里有问题？看了好久也没搞明白。

Question

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

#define MVNum 100
#define Maxint 32767

typedef int Adjmatrix;

typedef struct {
    int vexs[MVNum];
    Adjmatrix arcs[MVNum][MVNum];
    int vexnum, arcnum;
} MGraph;

int visited[MVNum];  // 标记顶点是否被访问过，如果被访问过为1，未被访问为0
int pathV[MVNum];    // 用来临时存放遍历的路径的顶点信息
int ti = 0;          // pathV的数组下标
int count = 0;       // 统计路径经过的顶点数目，如果count和图的顶点总数相同，表示找到一条经过所有顶点的路径
int path[MVNum][10]; // 存放符合条件的路径
int pi = 0;          // path的数组下标   path[pi][]
int pathCount = 0;   // 统计符合条件的路径的个数

int MenuSelect() {
    int sn;
    printf("   求包含所有顶点的简单路径 \n");        //显示菜单
    printf("==============================\n");
    printf("   1、采用邻接矩阵表示法创建无向图\n");
    printf("   2、找出符合条件的简单路径\n");
    printf("   0、退出控制系统\n");
    printf("==============================\n");
    printf("  请选择0--2:  ");

    //菜单功能选择
    for (;;) {
        scanf("%d", &sn);
        getchar();
        if (sn < 0 || sn > 2)
            printf("\n\t 输入选择错误，请重新选择 0--2： ");
        else
            break;
    }
    return sn;
}

// 查找顶点所在的位置并返回
int LocateVex(MGraph *G, int u) {
    int i;
    for (i = 0; i < G->vexnum; ++i) {
        if (G->vexs[i] == u) {
            return i;
        }
    }
    return -1;
}

// 设定顶点信息
void setVInfo(MGraph *G) {
    int i;
    printf("输入顶点值\n");
    for (i = 0; i < G->vexnum; i++)
        scanf("%d", &G->vexs[i]);
}

/*TODO:采用邻接矩阵表示法构造无向图
 功能描述：调用方法setVInfo(MGraph *G)，设置图的顶点信息，循环设定边的信息，利用邻接矩阵建立无向图
 注：处理边的逻辑如下：
 printf("输入%d条边的顶点信息vi,vj: \n", 边数);
 for (循环条件) {
 scanf("%d,%d", 边对应的顶点vi，边对应的顶点vj);
 }
 参数说明：G-MGraph型指针参数
 返回值说明：无
*/
void CreateMGraph(MGraph *G)
{
    memset(G->arcs,0,sizeof(G->arcs));
    setVInfo(G);
    int i;
    //printf("%d\n",G->arcnum);
    for(i=1;i<=G->arcnum;i++)
    {
        int p,q;
        printf("输入%d条边的顶点信息vi,vj: \n", i);
        scanf("%d %d",&p,&q);
        G->arcs[p][q]=1;
        G->arcs[q][p]=1;
    }
    /*for(i=1;i<=G->vexnum;i++)
    {
        for(j=1;j<=G->vexnum;j++)
            printf("%d ",G->arcs[i][j]);
        printf("\n");
    }*/
}

/*TODO:深度优先遍历
 功能描述：采用递归方式遍历，利用数组visited标记顶点是否被访问过，利用pathCount统计经过所有顶点的路径的数目，把符合条件的路径存放到数组path[pi][]中。
 参数说明：G-MGraph型指针参数
 v0-int型顶点位置
 返回值说明：无
*/
void DFS(MGraph *G, int v)
{

    int j;
    visited[v] = 1;
    path[pi][pathCount++] = v;
    for(j=0;j<G->vexnum;j++)
        if(G->arcs[v][j]==1&&visited[j]==0)
            DFS(G, j); 
    if (j==G->vexnum)
    {
        visited[v] = 0;
        pathCount--;
    }
}

/*TODO：寻找经过所有顶点的路径
 功能描述：从图的第一个顶点，循环调用DFS(MGraph *G, int v0)方法，查找经过所有顶点的路径
 参数说明：G-MGraph型指针参数
 返回值说明：无
 */
void SearchPath(MGraph *G)
{
    memset(visited,0,G->vexnum);
    DFS(G,0);
}

int main() {
    MGraph G;
    int i, j;

    // 无限循环,选择0 退出
    for (;;) {
        // 调用菜单函数，按返回值选择功能函数
        switch (MenuSelect()) {
        case 1:
            printf("输入图中顶点的个数和边数n,e:");
            scanf("%d,%d", &G.vexnum, &G.arcnum);
            CreateMGraph(&G);
            printf("无向图的储存结构构建完毕！\n");
            printf("\n");
            break;
        case 2:
            printf(" 找出所有包含所有顶点的简单路径\n");
            for (i = 0; i < MVNum; i++) {
                for (j = 0; j < G.vexnum; j++) {
                    path[i][j] = -1;
                }
            }
            SearchPath(&G);
            if (pathCount > 0) {
                for (i = 0; i < pathCount; i++) {
                    for (j = 0; j < G.vexnum; j++) {
                        if (path[i][j] != -1) {

                        }
                        printf("%3d", path[i][j]);
                    }
                    printf("\n");

                }
            } else {
                printf(" 不存在包含所有顶点的简单路径\n");
            }
            printf("\n");
            break;
        case 0:
            printf(" 退出控制系统！\n");                // 退出系统
            return 0;
        } // switch语句结束
    } // for循环结束
} // main()函数结束

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，已经为您补发到账户，我们后续会持续优化，扩大我们的服务范围，为您带来更好地服务。