開発者ドキュメント

java-graph-has-a-cycle

Javaグラフにサイクルがあるかどうかを確認する

1. 概要

このクイックチュートリアルでは、特定の有向グラフのサイクルを検出する方法を学習します。*

2. グラフ表現

このチュートリアルでは、隣接リストlink:/java-graphs#graph_representations [グラフ表現]を使用します。
まず、Javaで_Vertex_を定義することから始めましょう。
public class Vertex {

    private String label;
    private boolean beingVisited;
    private boolean visited;
    private List<Vertex> adjacencyList;

    public Vertex(String label) {
        this.label = label;
        this.adjacencyList = new ArrayList<>();
    }

    public void addNeighbor(Vertex adjacent) {
        this.adjacencyList.add(adjacent);
    }
    //getters and setters
}
*ここで、頂点_v_の_adjacencyList_は、_v_に隣接するすべての頂点のリストを保持します。* _addNeighbor()_メソッドは、_v_の隣接リストに隣接する頂点を追加します。
また、2つの_boolean_パラメーター、* _ beingVisited_と_visited_を定義しました。これらは、ノードが現在アクセスされているか、既にアクセスされているかを表します。*
グラフは、エッジを介して接続された頂点またはノードのグループと考えることができます。
それでは、Javaで_Graph_をすばやく表現しましょう。
public class Graph {

    private List<Vertex> vertices;

    public Graph() {
        this.vertices = new ArrayList<>();
    }

    public void addVertex(Vertex vertex) {
        this.vertices.add(vertex);
    }

    public void addEdge(Vertex from, Vertex to) {
        from.addNeighbor(to);
    }

   // ...
}
_addVertex()_および_addEdge()_メソッドを使用して、グラフに新しい頂点とエッジを追加します。

3. サイクル検出

有向グラフのサイクルを検出するには、* _ DFS_トラバーサルのバリエーションを使用します:*
  • 未訪問の頂点_v_を選択し、その状態を_beingVisited_としてマークします

  • _v、_の隣接する各頂点_u_について以下を確認します。

  • _u_が既に_beingVisited_状態にある場合、それは明らかに
    後方エッジが存在するため、サイクルが検出されました

  • _u_がまだ訪問されていない状態の場合、再帰的に_u_にアクセスします
    深さ優先

  • 頂点_v_âs_beingVisited_フラグを_false_に更新し、その
    _true_への_visited_フラグ

    グラフのすべての頂点は、_beingVisited_フラグと_visited_フラグの両方が_false_で初期化されるため、最初は未訪問の状態にあることに注意してください。 *
    Javaソリューションを見てみましょう。
public boolean hasCycle(Vertex sourceVertex) {
    sourceVertex.setBeingVisited(true);

    for (Vertex neighbor : sourceVertex.getAdjacencyList()) {
        if (neighbor.isBeingVisited()) {
            // backward edge exists
            return true;
        } else if (!neighbor.isVisited() && hasCycle(neighbor)) {
            return true;
        }
    }

    sourceVertex.setBeingVisited(false);
    sourceVertex.setVisited(true);
    return false;
}
グラフ内の任意の頂点をソースまたは開始頂点として使用できます。
*切断されたグラフの場合、ラッパーメソッドを追加する必要があります:*
public boolean hasCycle() {
    for (Vertex vertex : vertices) {
        if (!vertex.isVisited() && hasCycle(vertex)) {
            return true;
        }
    }
    return false;
}
これは、サイクルを検出するために、切断されたグラフのすべてのコンポーネントに確実にアクセスするためです。

4. 実装テスト

以下の巡回有向グラフを考えてみましょう。
link:/uploads/DirectedGraph-100x83.png%20100w []
このグラフの_hasCycle()_メソッドを検証するJUnitをすばやく作成できます。
@Test
public void givenGraph_whenCycleExists_thenReturnTrue() {

    Vertex vertexA = new Vertex("A");
    Vertex vertexB = new Vertex("B");
    Vertex vertexC = new Vertex("C")
    Vertex vertexD = new Vertex("D");

    Graph graph = new Graph();
    graph.addVertex(vertexA);
    graph.addVertex(vertexB);
    graph.addVertex(vertexC);
    graph.addVertex(vertexD);

    graph.addEdge(vertexA, vertexB);
    graph.addEdge(vertexB, vertexC);
    graph.addEdge(vertexC, vertexA);
    graph.addEdge(vertexD, vertexC);

    assertTrue(graph.hasCycle());

}
ここで、_hasCycle()_メソッドは、グラフが周期的であることを示す_true_を返しました。

5. 結論

このチュートリアルでは、Javaの特定の有向グラフにサイクルが存在するかどうかを確認する方法を学びました。
いつものように、サンプル付きのコード実装はhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-3[Github上]で入手できます。
モバイルバージョンを終了