無向グラフのサイクルを見つけて印刷する

Question

無向グラフのDFSを実行する必要がある割り当てを実行していて、それが見つかった場合はサイクルを印刷します。問題は、サイクルを見つけるために見つけることができるアルゴリズムはサイクルを保存しないということです。それらは単に真偽です。私の現在のコードは、一部のグラフでのみ動作しますが、他のグラフでは動作しません。たとえば、2ノードサイクル（4-5,5-4）を見つけることはできません。また、それは無指向でなければならないときに指示された権利のためだけに機能します。

編集：これは、私が見る限り、サイクルを保存し、その後印刷する方法に対処した他の問題がないので、サイクルの検索と印刷に関する他の質問と重複しません。それは存在しないしtrue/falseを返します。

編集：フォーマット

添付が

私のトラバーサルコードと私の主な方法である - メインメソッド

public static void main(String args[]) { 
// 
//  Graph g = new Graph(8); 
// 
//  g.add(0, 2); 
//  g.add(2, 3); 
//  g.add(3, 1); 
//  g.add(1, 0); 
// 
//  g.add(4, 5); 
//  g.add(5, 6); 
//  g.add(6, 7); 
//  g.add(7, 4); 
// 

//  Graph g = new Graph(6); 
// 
//  g.add(0, 1); 
//  g.add(1, 3); 
//  g.add(2, 3); 
//  g.add(3, 4); 
//  g.add(3, 5); 
// 


//  Graph g = new Graph(7); 
// 
//  g.add(0, 1); 
//  g.add(0, 2); 
//  g.add(0, 3); 
//  g.add(3, 4); 
//  g.add(4, 3); 
//  g.add(4, 5); 
//  g.add(4, 6); 


     Graph g = new Graph(5); 


     g.add(0, 1); 
     g.add(2, 3); 
     g.add(2, 4); 
     g.add(3, 4); 





     DepthFirstTraversal dfs = new DepthFirstTraversal(g); 

     System.out.println("Following is Depth First Traversal"); 

     dfs.DFS(); 

     if (!dfs.isCyclic()) 
      System.out.println("This graph is acyclic"); 

    } 

- グラフクラス

import java.util.LinkedList; 


public class Graph { 

    //Number of Vertices 
    private int vertices; 

    //Linked List to hold edges 
    private LinkedList<Integer> edges[]; 


    public Graph(int verticesGiven) { 
     this.vertices = verticesGiven; 
     this.edges = new LinkedList[vertices]; 
     fillNodes(edges, vertices); 
    } 


    private static void fillNodes(LinkedList<Integer> edges[], int 
    vertices) { 
     for (int counter = 0; counter < vertices; ++counter) { 
      edges[counter] = new LinkedList(); 
     } 
    } 


    void add(int x, int y) { 
     edges[x].add(y); 
    } 

    public int getVertices() { 
     return vertices; 
    } 


    public LinkedList<Integer>[] getEdges() { 
     return edges; 
    } 

} 

- トラバーサルと巡回検索

​​

Answer 1

私の持つ1つの質問は、グラフが無向であれば4-5と5-4を別々のエッジとみなすことです。私にとって、無向グラフでは、4-5と5-4は同じエッジであり、したがってサイクルではありません。有向グラフでは、これらは区別され、したがってサイクルを形成します。また、グラフ配列の長さが2のオブジェクトはすべてLinkedListですか？無向にしたい場合は、グラフのLinkedListオブジェクトをSetの実装に置き換えることができますが、ロジックを変更する必要があります。

とにかく、これは関連性があるようです。Best algorithm for detecting cycles in a directed graph