c++ - 快速查看边缘是否对图形连接很重要的方法

Question

我有一组边 E，我想知道我是否可以安全地删除 E 中的边 i，这意味着如果我将它从图中删除，该图应该仍然是连通的。

根据我的理解，这意味着第 i 条边必须位于一个圆上。输出应该是我无法删除的所有边的索引列表。

问题:

我的不同解决方案似乎都在做正确的事情，但速度太慢(效率低下)。

我的一个解决方案是:

1. Loop through all edges i in E
  2. Loop through all edges x in V
    3. Add edge x to the graph (excluding edge i) until nodes of i are connected or end reached
  4. If no connection possible, edge is not removable and added to the list

这种方式太慢了。

然后我决定重写我的代码并使用广度优先搜索来查看是否可以在没有边 i 的情况下使用另一条路径。

我认为它的性能足够了，但似乎不是。要么我以非常糟糕的方式实现，要么这也是该任务的错误算法。

这是我的C++代码中的算法(删除了一些不重要的部分):

struct connection {
    int a, b;
};

void expand(int x, connection *&arr, std::set<int> &exp, int size) {

    for (int i = 0; i < size; i++) {
        if (x == arr[i].a) {
            exp.insert(arr[i].b);
        }
        else if (x == arr[i].b) {
            exp.insert(arr[i].a);
        }
    }

    return;
}

// recursive breadth-first-seach

bool BFSr(std::set<int> &group, std::set<int> &visited, int goal, connection *&arr, int size) {
    if (group.empty()) return false;
    if (group.find(goal) != group.end()) return true;
    std::set<int> tempa;

    for (std::set<int>::iterator it = group.begin(); it != group.end(); ++it) {
        expand(*it, arr, tempa size);
    }

    for (std::set<int>::iterator it = visited.begin(); it != visited.end(); ++it) {
        tempa.erase(*it);
    }

    tempb = visited;
    tempb.insert(group.begin(), group.end());
    return BFSr(tempa, tempb, goal, arr, size);
}

bool BFS(int start, int goal, connection *&arr, int size) {
    std::set<int> tempa;
    std::set<int> tempb;
    tempa.insert(start);
    return BFSr(tempa, tempb, goal, arr, size);
}

int main()
{

    connection *arr = new connection[m];
    connection *con = new connection[m - 1];

    // fill arr with connections arr.a < arr.b ....

    for (int j = 0; j < (m - 1); j++) {
        con[j] = arr[j + 1];
    }

    // 1. edge for performance reasons extra
    if (!BFS(arr[0].a, arr[0].b, con, (m - 1))) {
        // connection is important therefore add to list
        printf(" %d", 1);
    }

    // Look if nodes still connected after removing connection
    for (int s = 1; s < m; s++) {

        con[s - 1] = arr[s - 1];

        if (!BFS(arr[s].a, arr[s].b, con, (m-1))) {
            // connection is important therefore add to list
            printf(" %d", s + 1);
        }
    }

    printf("\n");


    free(arr);
    free(con);

    return 0;
}

你知道有什么解决方案可以让我更快，或者你知道更好的算法来解决我的问题吗？

Answer 1

删除断开两个连接组件的边称为 bridge 并且有用于查找图中所有桥梁的线性时间算法(通常基于深度优先搜索)。维基百科文章以其中一个(由于 Tarjan)为例。 This paper还给出了一个简单的算法，用于在图中列出所有的桥，似乎比 Tarjan 的算法简单一些。

希望这对您有所帮助!