从无向图中删除边

Question

我有一个无向图实现为

vector<int> G[V];

或

list<int> G[V];

，对我来说没什么区别，我需要在 O(1) 中从中删除边。连接矩阵是不可能的，顶点的数量是 10^5。问题如下：

for(int i = 0; i < G[w].size(); i++)
{
    int u = G[w][i];
    // erase G[w][i];
    // erase the edge (u, w) in G[u] in constant time
}

我该如何实现。

Answer 1

像这样混合 C 风格数组和 STL 容器

vector<int> G[V];

不被认为是好的风格。为什么不使用 vector< vector< int > >？

关于您要求 erase()-函数 O(1)，我认为您面临着权衡：要么访问速度非常快，但容器的频繁修改相当昂贵 (std::vector)，反之亦然 (std::map、std::list、...)。

以下示例提供了请求的常量 erase() 功能，但查找要删除的元素是对数的。但也许它可以帮助您找到想要的东西：

#include <vector>
#include <set>

typedef int Vertex;
typedef std::vector< Vertex > Vertices;

struct Edge
{
    int a;
    int b;

    Edge( int a, int b ) : a( a ), b( b ) {}

    // Needed for std::set.
    bool operator< ( const Edge & other ) const
    {
        if ( a < other.a ) return true;
        if ( a > other.a ) return false;

        return b < other.b;
    }
};

 typedef std::set< Edge > Edges;

struct Graph
{
    Vertices vertices;
    Edges edges;
};

int main( int argc, char ** argv )
{
    Graph graph;

    // Add vertices.
    graph.vertices.push_back( Vertex( 0 ) ); // Vertex 0
    graph.vertices.push_back( Vertex( 1 ) ); // Vertex 1
    graph.vertices.push_back( Vertex( 2 ) ); // Vertex 2
    graph.vertices.push_back( Vertex( 3 ) ); // Vertex 3

    // Connect vertices.
    graph.edges.insert( Edge( 0, 1 ) ); // Connect vertex 0 and vertex 1.
    graph.edges.insert( Edge( 0, 1 ) ); // Connect vertex 1 and vertex 2.
    graph.edges.insert( Edge( 1, 2 ) ); // Connect vertex 2 and vertex 3.
    graph.edges.insert( Edge( 2, 0 ) ); // Connect vertex 3 and vertex 0.

    // Remove the edge between vertices 1 and 2 again.
    Edges::iterator it = graph.edges.find( Edge( 1, 2 ) );

    if ( it != graph.edges.end() )
        graph.edges.erase( it ); // The complexity of erase() is constant, but find() logarithmic.
}

Answer 2

太好了，好久没问这个问题了，看到还是没人回答我来补充一下我当时用的一个方案。

因此，假设边存储在邻接列表数组中

std::list<Edge> G[V];

我们可以将边定义如下：

struct Edge {
    int vertex;
    std::list<Edge>::iterator siblingIterator;
}

然后删除例程很简单

for(auto &edge : G[w]) {
    G[edge.vertex].erase(edge.siblingIterator);
}

G[w].clear();

由于使用列表迭代器删除需要常数时间，因此删除一个无向边（因此有向边及其反向兄弟）需要 O(1)。

我不会沉迷于过去并修复我当时有限的 C++ 技能中的所有不良做法，但解决方案的要点很简单：只需保留对兄弟姐妹的引用。案件结案。

从无向图中删除边

Deleting edges from an undirected graph

c++

implementation

graph