将无定向图转换为双定向图

Question

Given G=(V,E) be a connected, undirected graph.Is there a way to converted it to directed graph in both directions between two edges.so if there is A and B as vertex, then A->B and B->A should exist in directed graph.I want to know algorithm for it, so I can write a code for it. 我想知道它的算法，这样我就可以为它写一个代码了。

Answer 1

表示一个有10个节点的图的快速方法：把一个节点的相邻列表表示为一个集合。

set<int> G[10];

然后，只要做

for(int u = 0; u < 10; u++){    //for each node u
    for(int v : G[u]){          //for each node v where exists an edge (u → v)

        if(!G[v].contains(u)) G[v].insert(u);    //add the missing edge (v → u) 

   }
}

复杂度：O(V+E lg(V)) O(V+E lg(V))

如果你愿意，你可以使用 unordered_set 而不是 set 并使复杂度为O(V+E)。