1

我必须反转给定的有向图，以便顶点保持不变，但边的方向相反。我的图用一个 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>();
    }
}

加上当然它是吸气剂和二传手。问题是当循环从顶点 1 开始，并且它的邻接列表包含顶点 5 时，它将 1 添加到 5 的邻接列表中并从 1 的邻接列表中删除 5。下一次，当循环到达 5 时，它将 5 添加到 1'a 邻接表中，并从 5 的邻接表中删除 1。在循环修改它之前，我需要保持每个列表的初始大小。

4

4 回答 4

8

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

伪代码：

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

你应该做什么：因为我假设你是一个有作业的学生（通常是问题以“我必须......”开头的情况），我将快速解释我的伪代码，以便你了解总体想法并掌握自己实施的能力。

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

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

希望这可以帮助！

于 2013-02-26T08:18:39.367 回答
1

不要改变你的图表表示，而是建立一个新的。

如果需要您实际更改 Graph 对象，您仍应创建一组新的邻接列表，并在最后一步用新列表替换原始列表

于 2013-02-26T08:06:14.243 回答
1

基本上，您必须为反转的顶点制作一个临时的新列表，并且只有在所有顶点都被反转后才能将它们交换为原始列表。只要 for 循环正在运行，用作 for 循环的迭代器的列表就永远不会改变。

另外，您从哪里获得 verticesSize 和 vertices 对象？它应该作为参数给出，即使它是一个类参数，在这种情况下至少应该由 this.vertices 和 this.verticesSize 调用。最后一个也应该避免，并且总是在使用当前列表对象之前计算...

于 2013-02-26T08:06:45.723 回答
0

这是基于https://stackoverflow.com/a/15084366/574776中提到的算法的一种实现

static class Vertex {
    final int data;
    final List<Edge> edges;
}

static class Edge {
    Vertex source, destination;

    public void reverse() {
        source.edges.remove(this);
        destination.edges.add(this);

        Vertex temp = source;
        source = destination;
        destination = temp;
    }
}

static class Graph {
    final Map<Integer, Vertex> vertices;

    public Vertex getVertex(Integer data) {
        if (!vertices.containsKey(data)) {
            vertices.put(data, new Vertex(data));
        } 

        return vertices.get(data);
    }

    public void addEdge(Vertex source, Vertex destination) {
        Edge e = new Edge(source, destination);
        source.edges.add(e);
    }

    public void reverse() {
        System.out.println("reversing graph ... ");
        BitSet visited = new BitSet(vertices.size() + 1);
        for (Vertex v : vertices.values()) {
            if (!visited.get(v.data)) {
                reverse(v, visited);
            }
        }
    }

    private void reverse(Vertex v, BitSet visited) {
        if (DEBUG)  System.out.println("reversing " + v);
        visited.set(v.data);
        List<Vertex> neigbors = new ArrayList<Vertex>();
        List<Edge> toReverse = new ArrayList<Edge>();
        for (Edge e : v.edges) {
            Vertex destination = e.destination;
            if (!visited.get(destination.data)) {
                neigbors.add(destination);
            }
            toReverse.add(e);
        }

        for (Vertex n : neigbors) {
            reverse(n, visited);
        }

        for (Edge e : toReverse) {
            e.reverse();
        }

        if (DEBUG)  System.out.println("reversed " + v);
    }
}
于 2013-08-04T20:11:32.360 回答