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

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

这是您算法的另一个版本（我想您将免费获得图形和各种算法的行业标准优化实现）：

我将这张图片称为图形模型。要点（来自这个post）

找到表达点
所有单出边的点都是关节点（提升图不会 return 这些）- 这些边缘自动桥接边缘
对于每个关节点- 遍历每个外边，如果外边已经没有桥接边-那么删除边缘并检查图形组件并将边缘添加回去再次

最后会打印出Edge(a,g) connects components in graph

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/biconnected_components.hpp>
#include <boost/graph/connected_components.hpp>

#include <functional>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

typedef boost::adjacency_list <boost::vecS, boost::vecS, boost::undirectedS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits<Graph>::edge_descriptor edge_t;

//  reference:
//  http://lists.boost.org/boost-users/2005/08/13098.php
//
struct edge_t_hasher
{
    std::size_t operator()(const edge_t& e) const
    {
        auto prop = e.get_property();
        std::hash<decltype(prop)> hasher;
        return hasher(prop);
    }
};

typedef std::unordered_set<edge_t, edge_t_hasher> UnorderedBoostEdgeSet;

Graph getGraph()
{
    Graph g;

    vertex_t aVtx = boost::add_vertex(g);
    vertex_t bVtx = boost::add_vertex(g);
    vertex_t cVtx = boost::add_vertex(g);
    vertex_t dVtx = boost::add_vertex(g);
    vertex_t eVtx = boost::add_vertex(g);
    vertex_t fVtx = boost::add_vertex(g);
    vertex_t gVtx = boost::add_vertex(g);
    vertex_t hVtx = boost::add_vertex(g);
    vertex_t iVtx = boost::add_vertex(g);

    boost::add_edge(dVtx, cVtx, g);
    boost::add_edge(dVtx, bVtx, g);
    boost::add_edge(cVtx, bVtx, g);
    boost::add_edge(aVtx, bVtx, g);
    boost::add_edge(bVtx, eVtx, g);
    boost::add_edge(eVtx, fVtx, g);
    boost::add_edge(aVtx, fVtx, g);
    boost::add_edge(aVtx, gVtx, g);// edge connecting components
    boost::add_edge(gVtx, iVtx, g);
    boost::add_edge(gVtx, hVtx, g);
    boost::add_edge(hVtx, iVtx, g);

    return g;
}

UnorderedBoostEdgeSet bridgingEdgesForGraph(const Graph& graph)
{
    UnorderedBoostEdgeSet bridgeEdges;

    std::unordered_set<vertex_t> articulationVertices;
    boost::articulation_points(graph, std::inserter(articulationVertices, articulationVertices.end()));

    //  add all the single connected vertices to the articulation vertices
    auto vtxIters = boost::vertices(graph);
    for (auto it = vtxIters.first, end = vtxIters.second; it != end; ++it)
    {
        if (boost::out_degree(*it, graph) == 1)
            bridgeEdges.insert(*(boost::out_edges(*it, graph).first));
    }

    std::vector<vertex_t> componentsInGraph(boost::num_vertices(graph));
    int numComponentsInGraph = boost::connected_components(graph, &componentsInGraph[0]);

    //  for each articulation vertex now get edges and check if removing that
    //  edge causes graph change in connected components
    //

    //  copy the graph- so we can iterate over the outeges of vertices
    //  we will be fiddling with the copy- since the vtx descriptors are
    //  ints- they stay same across copy and removing edge operation
    auto graph2 = graph;
    for (auto vtx : articulationVertices)
    {
        auto outEdges = boost::out_edges(vtx, graph);
        for (auto it = outEdges.first, end = outEdges.second; it != end; ++it)
        {
            auto edge = *it;
            if (bridgeEdges.find(edge) != bridgeEdges.end())
                continue;

            //  map this edge to graph2 edge- for removal and eventual addition
            auto src = boost::source(edge, graph);
            auto tgt = boost::target(edge, graph);

            auto edge2 = boost::edge(src, tgt, graph2).first;

            boost::remove_edge(edge2, graph2);
            std::vector<vertex_t> componentsInGraph2(boost::num_vertices(graph2));
            int numComponentsInGraph2 = boost::connected_components(graph2, &componentsInGraph2[0]);

            // bridging edge- graph #components changed
            if (numComponentsInGraph != numComponentsInGraph2)
                bridgeEdges.insert(edge);

            //  add the edge back to graph2
            boost::add_edge(src, tgt, graph2);
        }
    }

    return bridgeEdges;
}

int main()
{
    const Graph& graph = getGraph();
    const auto& bridgingEdges = bridgingEdgesForGraph(graph);

    const char* array = {"ABCDEFGHI"};
    for (auto edge : bridgingEdges)
    {
        std::cout << "Edge(" << array[boost::source(edge, graph)] << ", " << array[boost::target(edge, graph)] 
                  << ") is a bridging edge" << std::endl;
    }

    return 0;
}

Answer 2

与此同时，我发现了这些特殊边的名称：桥。

因此我找到了一个提供 DFS 算法的站点来查找所有桥。

对我来说足够快了。

DFS algorithm for finding Bridges in a undirected Graph

谢谢 Sarang，您的 post 让我找到了网站的正确搜索词。

Answer 3

删除两个连通分量的边称为a bridge and there are linear-time algorithms for finding all the bridges in a graph (usually based on depth-first search). The Wikipedia article lists one of them (due to Tarjan) as an example. This paper 也给出了一个简单的算法来列出图中的所有桥，似乎比Tarjan 的算法简单一些。

希望对您有所帮助！

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

Fast way to look if edge is important for graphs connectivity

c++

performance

graph

breadth-first-search

undirected-graph