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 的算法简单一些。

希望这有帮助!