反转有向图

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));
        }
    }
}

这是Vertex类

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>();
    }
}

}

加上当然是吸气鬼和二传手.问题是,当循环从顶点编号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

你应该做什么:因为我认为你是一个有作业的学生(通常情况下以"我必须......"开头的问题),我会快速解释我的伪代码,这样你就可以得到最重要的想法并拥有能够自己实现它.

你不能只是遍历顶点并反转每个边缘,因为反转边缘使它成为其他顶点的外边缘,如果你还没有用你的循环查看那个其他顶点,你最终会反转它再次,这将导致边缘与它开始时的方向相同.或者,你已经看过另一个顶点,在这种情况下它会很好.但是,如果您在顶点中随机循环,则存在两种可能性,因此在所有顶点中随机循环不起作用.

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

希望这可以帮助!