1. 概要

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

2. グラフ表現

このチュートリアルでは、隣接リストグラフ表現を使用します。

まず、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の隣接リストはvに隣接するすべての頂点のリストを保持します。 addNeighbor()メソッドは、vの隣接リストに隣接する頂点を追加します。 ]。

また、2つの boolean パラメーターを定義しました。はVisitedおよびvisitedであり、ノードが現在訪問されているか、すでに訪問されているかを表します。

グラフは、エッジを介して接続された頂点またはノードのグループと考えることができます。

それでは、Javaでグラフを簡単に表現しましょう。

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に再帰的にアクセスします。
  • 頂点vbeingVisitedフラグをfalseに更新し、そのvisitedフラグをtrueに更新します。

ご了承くださいグラフのすべての頂点は、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. 実装テスト

以下の循環有向グラフを考えてみましょう。

このグラフの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の特定の有向グラフにサイクルが存在するかどうかを確認する方法を学びました。

いつものように、例を含むコード実装は、Github利用できます。