如何反转邻接表？

Question

假设我的邻接表如下：

0 : 1
1 : 0

它的反向应该是空的，因为在初始列表中有两条弧线：

0:
1:

或

0 : 1
1 :

变成

0 : 
1 : 0

另一个例子：

0 : 
1 :

变成

0 : 1
1 : 0

最后一个例子

0 : 1, 4
1 : 0, 4
2 : 0, 1, 3, 4
3 : 
4 : 3, 1

变成

0 : 2, 3
1 : 2, 3
2 : 
3 : 0, 1, 2, 4
4 : 0, 2

是否有算法可以做到这一点？

Graphe *Graphe::grapheInverse( void ){
    Graphe *r = new Graphe (_adjacences.size() );
    for (unsigned i = 0; i < _adjacences.size(); i++)
        for ( unsigned j = 0; j < _adjacences[i]->size(); j++ )
            if ( (*_adjacences[i])[j] == 1 ) // or 0 or 2 or 3 or 4 or ... like last example
                //r->addArcs( i, (*_adjacences[i])[j] ); //adds an arc from A to B
            
    return r;
}

Answer 1

只需反转邻接矩阵即可。

无论哪里有 0，请将其替换为 1，反之亦然。只排除对角线，总是在那里放一个 0。

如何反转邻接表？

How to reverse an Adjacency list?

c++

algorithm

graph

adjacency-list