java - 反转有向图

Question

我必须反转给定的有向图，以便顶点保持不变，但边的方向相反。我的图用一个 Graph 类表示，它包含一个顶点 ArrayList，每个 Vertex 对象都有它的编号和相邻顶点的 ArrayList。我的代码给出了错误的答案，因为在循环的每次迭代中，顶点的相邻列表的大小都会发生变化。如何修复我的代码？

public void reverse() {
    ArrayList < Vertex > adjacentOfi = new ArrayList < Vertex > ();
    int k;
    for (int i = 1; i < verticesSize; i++) {
        adjacentOfi = vertices.get(i).getAdjacent();
        for (int j = 0; j < adjacentOfi.size(); j++) {
            k = adjacentOfi.get(j).getNumber();
            adjacentOfi.remove(j);
            vertices.get(k).getAdjacent().add(vertices.get(i));
        }
    }
}

这是顶点类

public class Vertex {
    private int number;
    private boolean marked;
    private int finishingTime;
    private ArrayList<Vertex> adjacent;

    public Vertex(int num) {
        this.number = num;
        this.marked = false;
        this.finishingTime = 0;
        this.adjacent = new ArrayList<Vertex>();
    }
}

当然还有 getter 和 setter。 问题是，当循环从顶点编号 1 开始，并且它的邻接列表包含顶点 5 时，它会将 1 添加到 5 的邻接列表并从 1 的邻接列表中删除 5。下一次，当循环到达 5 时，它将 5 添加到 1 的邻接表中，并从 5 的邻接表中删除 1。在循环修改它之前，我需要维护每个列表的初始大小。

Answer 1

目标:对图中的每条边执行一次原子操作。

伪代码:

function reverse(graph G)
    v = any vertex in G
    reverseVertex(v)
end function

function reverseVertex(vertex v)
    mark v as visited
    E = set of all outward edges from v
    N = { } // empty set, will contain all neighbors
    for each edge e in E,
         q = vertex reached by e from v
         if q is not visited,
             add q to N
             reverse direction of e
         end if
    end for

    for each vertex q in N,
         reverseVertex(q)
end function

你应该做什么:因为我假设你是一个有作业的学生(通常情况下问题以“我必须......”开头)，我会快速解释我的伪代码，让您了解总体思路并有能力自行实现。

您不能只遍历顶点并反转每条边，因为反转边会使它成为其他顶点的出边，如果您还没有通过循环查看其他顶点，您将最终再次反转它，这将导致边缘与开始时的方向相同。或者，您已经查看了另一个顶点，在这种情况下就可以了。但是，如果您随机循环遍历顶点，则这两种可能性都存在，因此随机循环遍历所有顶点是行不通的。

一个更直观的解决方案是从图中的任何顶点开始，并标记它已访问。然后，对于顶点的每个 unvisited 邻居，将邻居添加到列表中并反转通往邻居的边(即删除它并像您在代码中所做的那样添加它)。然后，对未访问邻居列表中的所有邻居递归调用此函数。最终，一旦你到达一个所有邻居都被访问过的顶点，或者一个叶子，递归调用就会终止。我确信这个算法的归纳证明不会太难想出。

希望这对您有所帮助!