c++ - 检查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 和顶点 之间存在一条边code>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 中标记为已访问 (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;
}