检查是否存在连接C ++中2个顶点的路径

Question

我正在尝试编写一个代码来检查给定图形中从顶点v1到v2的路径是否存在。它适用于某些测试用例，并为其他测试用例提供运行时错误（超出时间限制）。

bool HasPath(int V, int** edges, int* visited, int v1, int v2)
{
    if (edges[v1][v2] == 1)
    {
        return true;
    }

    for (int i = 0; i<V; i++)
    {
        if (visited[i] == 1)
            continue;

        if (edges[v1][i] == 1)
        {
            bool sa = HasPath(V, edges, visited, i, v2);
            visited[i] = 1;
            if (sa == false)
                continue;
            else
                return true;
        }
    }
    return false;
}

int main() {
    int V, E;
    cin >> V >> E;

    int** edges = new int*[V];
    for (int i = 0; i<V; i++)
    {
        edges[i] = new int[V];
        for (int j = 0; j<V; j++)
        {
            edges[i][j] = 0;
        }
    }

    for (int i = 0; i<E; i++)
    {
        int f, s;
        cin >> f >> s;
        edges[f][s] = 1;
        edges[s][f] = 1;
    }

    int* visited = new int[V];
    for (int i = 0; i<V; i++)
        visited[i] = 0;

    int v1, v2;
    cin >> v1 >> v2;
    bool ans = HasPath(V, edges, visited, v1, v2);
    if (ans == 1)
        cout << "true";
    else
        cout << "false";
    return 0;
}

边缘是邻接矩阵。图表是双向的。目的是找出从v1到v2的路径是否存在。输入格式： 第1行：V和E 下一个E线：两个整数a和b，表示在顶点a和顶点b（由空格分隔）之间存在边缘 线(E+2)：两个整数v1和v2（由空格分隔）

示例测试用例失败：

6 3
5 3
0 1
3 4
0 3 (these are the vertices between which we need to find path)

上述测试用例的图表：

通过的示例测试用例：

4 4
0 1
0 3
1 2
2 3
1 3

Answer 1

我做的主要改变是在递归调用之前递归函数HasPath标记为visit（visited[i] = 1;）。我还对您的代码进行了一些细微的更改。

另外，不要忘记删除动态分配的内存（即使它在这里不重要。）

#include <iostream>
using namespace std;

bool HasPath(int V, int** edges, int* visited, int v1, int v2)
{
    if (edges[v1][v2] == 1)
        return true;

    for (int i = 0; i<V; i++)
    {
        if (visited[i] != 1 && edges[v1][i] == 1)
        {
            visited[i] = 1;
            if (HasPath(V, edges, visited, i, v2))
                return true;
        }
    }
    return false;
}

int main() 
{
    int V, E;
    cin >> V >> E;

    int** edges = new int*[V];
    for (int i = 0; i<V; i++)
    {
        edges[i] = new int[V];
        for (int j = 0; j<V; j++)
        {
            edges[i][j] = 0;
        }
    }

    for (int i = 0; i<E; i++)
    {
        int f, s;
        cin >> f >> s;
        edges[f][s] = 1;
        edges[s][f] = 1;
    }

    int* visited = new int[V];
    for (int i = 0; i<V; i++)
        visited[i] = 0;

    int v1, v2;
    cin >> v1 >> v2;
    bool ans = HasPath(V, edges, visited, v1, v2);
    cout << (ans == 1 ? "true" : "false");

    for (int i = 0; i < V; i++)
        delete[] edges[i];

    delete[] edges;
    delete[] visited;

    return 0;
}