判断两顶点之前有路径吗？为什么错了

Question

PTA6-2 两顶点之前有路径吗？
分数 15
作者 周强
单位 青岛大学

对于给定的无向图及两个图中的顶点，请实现一个函数，分别打印包含这两个顶点的连通分量中的顶点数，并判断这两个顶点之间是否有路径。

函数接口定义：

int hasPath(struct Graph *g, int v, int w);

其中v和w是顶点
图定义如下:

#define MaxVertexNum 20   /* 最大顶点数 */
struct Graph{
    int v;    /*  顶点数量 */
    int Adj[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};

题目保证图至少有一个顶点
函数分别在第一行和第二行打印包含v和w的连通分量中顶点的数量。
如果 v和w之间有路径，函数返回1, 否则返回0.

提示:
你可以定义多个函数，也可以定义全局变量.
当v和w是同一个顶点时，认为v和w之间是有路径的。
裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 20   /* 最大顶点数设为20 */
struct Graph{
    int v;  // amount of vertices
    int Adj[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
int visited[MaxVertexNum]; /* 顶点的访问标记 */
struct Graph* CreateGraph(){
    int v;
    scanf("%d",&v);
    struct Graph* g;
    g = malloc(sizeof(struct Graph));
    if(!g) return NULL;
    g->v = v;
    for(int i=0; i<v; i++){
        visited[i] = 0;
        for(int j=0; j<v; j++)
            scanf("%d",&(g->Adj[i][j]));
    }
    return g;
}
int hasPath(struct Graph *g, int v, int w);
int main(){
    struct Graph* g;
    g = CreateGraph();
    int v,w;
    scanf("%d%d", &v, &w);
    printf("%s\n", hasPath(g,v,w) ? "Yes" : "No");
    return 0;
}
/* 你的代码将被嵌在这里 */

图为：

7-0-2-4  3-5  6
   \1/

对于此图及样例测试程序规定的输入格式：
输入样例：
8
0 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 3
Sample Output：
5
2
No
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

请问为什么下面的代码运行出来段错误？

int *pre;
int count=1;
int firstadj(struct Graph *g, int v)
{
    int i;
    for(i=0;i<g->v;i++)
    {
        if(g->Adj[v][i]==1) 
        {
            count=2;
            return i;
        }
    }
    if(i==g->v) //孤立点
    {
        count=1;
        return -1;
    }
}
int nextadj(struct Graph *g, int v, int w)
{
    int i;
    for(i=w+1;i<g->v;i++)
    {
        if(g->Adj[v][i]==1) 
        {
            count++;
            return i;
        }
    }
    if(i==g->v) return -1;//w是v的最后一个邻接点
}
void init(struct Graph *g, int v)
{
    int i;
    pre=(int*)malloc(g->v*sizeof(int));
    for(i=0;i<g->v;i++) pre[i]=-1;
    pre[v]=-2;
}
int hasPath(struct Graph *g, int v, int w)
{
    int j=firstadj(g,v);
    if(j==-1) return 0;//孤立点
    init(g,v);
    while(j>=0)
    {
        if(pre[j]==-1)
        {
            pre[j]=v;
            if(j==w)
            {
                printf("%d\n",count);
                return 1;//有路径
            }
            else if(hasPath(g,j,w)) 
            {
                printf("%d\n",count);
                return 1;//有路径
            }
        }
        j=nextadj(g,v,j);
        
    }
    count=0;
    j=firstadj(g,w);
    while(j>=0)
    {
        j=nextadj(g,w,j);
    }
    printf("%d\n",count);
    return 0;//无路径
}

Answer 1

本答案参考多次询问 ChatGPT-3.5 后选择的最佳回答，若是满意，还请采纳，谢谢。

代码中存在几个问题，导致运行时出现段错误。以下是代码的错误分析和修改建议：

1. 全局变量 pre 和 count 的使用：在 hasPath 函数中，你使用了全局变量 pre 和 count。全局变量在函数调用之间会保留状态，这可能导致在递归调用中出现错误。建议将这些变量作为函数参数传递，以避免状态混淆。

2. **递归调用 hasPath**：在 hasPath 函数中，你递归调用了 hasPath。这可能导致栈溢出，尤其是对于大型图。建议使用迭代方法代替递归。

3. 错误的邻接点遍历：在 hasPath 函数中，你使用了 firstadj 和 nextadj 来遍历邻接点。但是，这种方法可能不正确，因为它没有正确地处理所有邻接点。建议使用标准的深度优先搜索（DFS）或广度优先搜索（BFS）算法来遍历图。

4. 孤立点的处理：在 hasPath 函数中，你检查了孤立点的情况，但是没有正确地处理它。如果 v 或 w 是孤立点，那么它们之间不可能有路径。建议在函数开始时检查孤立点，并直接返回结果。

5. 内存分配：在 init 函数中，你为 pre 分配了内存，但是没有在函数结束时释放它。这可能导致内存泄漏。建议在函数结束时释放分配的内存。

以下是修改后的代码示例：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 20   /* 最大顶点数设为20 */
struct Graph{
    int v;  // amount of vertices
    int Adj[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
int visited[MaxVertexNum]; /* 顶点的访问标记 */

int hasPath(struct Graph *g, int v, int w) {
    int *pre = (int*)malloc(g->v * sizeof(int));
    int count = 0;
    int stack[MaxVertexNum], top = -1;
    int i;

    for (i = 0; i < g->v; i++) {
        visited[i] = 0;
        pre[i] = -1;
    }

    stack[++top] = v;
    visited[v] = 1;
    pre[v] = -2;

    while (top != -1) {
        int current = stack[top--];
        if (current == w) {
            count++;
            break;
        }
        for (i = 0; i < g->v; i++) {
            if (g->Adj[current][i] == 1 && !visited[i]) {
                stack[++top] = i;
                visited[i] = 1;
                pre[i] = current;
                count++;
            }
        }
    }

    if (top == -1) {
        count = 0;
        stack[++top] = w;
        visited[w] = 1;
        pre[w] = -2;

        while (top != -1) {
            int current = stack[top--];
            for (i = 0; i < g->v; i++) {
                if (g->Adj[current][i] == 1 && !visited[i]) {
                    stack[++top] = i;
                    visited[i] = 1;
                    pre[i] = current;
                    count++;
                }
            }
        }
    }

    printf("%d\n", count);
    free(pre);
    return (count > 0) ? 1 : 0;
}

这个修改后的代码使用了迭代的深度优先搜索（DFS）来遍历图，并正确地处理了孤立点和内存分配。希望这能解决你的问题。