有向图顶点和边的反转

Question

所以我正在研究这个问题：

这是我目前所掌握的

a) Create a new graph with the same size 2-dimensional array, B. Iterate 
through the original graph's 2-dimensional array, A, which is of size VxV, 
where V is the number of vertices in the graph. If A[i][j] is true, then an 
edge exists there. Set B[j][i] true in the new reversed graph's matrix. 
The algorithm will be of complexity V^2 since it needs to iterate through 
all of the 2-dimensional array.

b) Create a new graph with an empty array, B, of size V, where V is the 
number of vertices. Iterate through the array of lists in the original 
graph, A. if there is a list  at A[i] then iterate through each one and i to
the corresponding B[x] where x is the integer in the list. The algorithm 
will be complexity of V + E since it needs to iterate through an array of 
size V, and then a total list elements of size E.

首先，我想对我的答案再作核实。我对有向图不是那么熟悉，对算法的效率/复杂度也不是特别熟练。我想我做得对，但如果我需要的话，我想要一些帮助。我也在寻找任何想法，使它更有效率。这些是我脑海中最先出现的算法，所以我觉得可能有更好的方法来实现它。

谢谢

Answer 1

你的a）是正确的。在矩阵语言中，你正在寻找矩阵a的转置。一个需要考虑的小细节是，你是否需要将B的非边项设置为false。这取决于语言，尽管大多数语言（我认为）会在内存初始化时将B的所有项设置为false或0。其复杂性确实是O(v^2)。

你的b）措词不好。但我想你有这个想法。你必须在b[x]处把一些东西推入列表。更好地描述x。复杂性确实是O(V+E)。

你没有什么办法让他们更有效率。你必须在第一种情况下处理每对顶点，在第二种情况下处理每条边。在邻接矩阵的情况下，你可以先交换顶点的顺序，然后再往上看，所以如果你被问到（x,y）是否有边，你会返回（y,x）的答案，但如果你做的次数超过v^2次，你就不会得到前面的结果。邻接列表也一样。