1

頂点は同じままですが、エッジが反対方向になるように、特定の有向グラフを逆にする必要があります。私のグラフは、頂点の ArrayList を含む Graph クラスで表され、各 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 が含まれている場合、5 の隣接リストに 1 を追加し、1 の隣接リストから 5 を削除することです。次に、ループが 5 に達すると、1' の隣接リストに 5 を追加し、5 の隣接リストから 1 を削除します。ループによって変更される前に、各リストの初期サイズを維持する必要があります。

4

4 に答える 4

8

目標:グラフ内のすべてのエッジでアトミック操作を 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

あなたがすべきこと:私はあなたが課題を抱えている学生だと思っているので (通常、「I have to...」で始まる質問の場合)、私の疑似コードを簡単に説明して、包括的なアイデアを理解してもらい、自分で実装する能力。

頂点をループして各エッジを反転することはできません。エッジを反転すると、他の頂点への出力エッジになるためです。ループで他の頂点をまだ見ていない場合は、反転することになりますこれにより、エッジは開始時と同じ方向になります。または、すでに他の頂点を見ている場合は、問題ありません。ただし、頂点をランダムにループしている場合は両方の可能性が存在するため、すべての頂点をランダムにループしても機能しません。

より直感的な解決策は、グラフ内の任意の頂点から始めて、それが訪れたラベルを付けることです。次に、頂点の未訪問の各隣接点について、隣接点をリストに追加し、隣接点に向かうエッジを逆にします (つまり、コードで行ったように削除して追加することにより)。次に、未訪問のネイバーのリスト内のすべてのネイバーでこの関数を再帰的に呼び出します。最終的に、再帰呼び出しは、すべての近隣が訪問された頂点またはリーフに到達すると終了します。このアルゴリズムの帰納的証明を思い付くのはそれほど難しくないと確信しています。

お役に立てれば！

于 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に記載されているアルゴリズムに基づく実装の 1 つを次に示します。

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 に答える