무디 그래프의 사이클 찾기 및 인쇄

Question

무향 그래프의 DFS를 수행해야하는 과제를 수행하고있는 경우 사이클을 인쇄합니다. 문제는 사이클을 찾기 위해 찾을 수있는 알고리즘은 사이클을 저장하지 않는다는 것입니다. 단순히 true/false입니다. 현재 코드는 일부 그래프에서만 작동하지만 다른 그래프에서는 작동하지 않습니다. 예를 들어 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; 
    } 

} 

- 순회 및 순환 검색

import java.util.*; 


public class DepthFirstTraversal { 

    //Each traversal has a graph 
    private Graph graph; 

    //Holds the nodes for each cycle 
    private List<Integer> cycle = new ArrayList<Integer>(); 


    public DepthFirstTraversal(Graph graph) { 

     this.graph = graph; 
    } 


    private void DFSRecursive(int current, boolean visited[], 
    LinkedList<Integer> edges[]) { 

     // Say you visited current node 
     visited[current] = true; 

     //Print the current node 
     System.out.print(current + " "); 

     // Look at all vertices connected to this one 
     Iterator<Integer> iterate = edges[current].listIterator(); 

     //Check to see everything this is connected to 
     while (iterate.hasNext()) { 

      //Check to see what the next one is 
      int connected = iterate.next(); 

      //check if you've already visited what it's connected to. 
      If you haven't, check that one out. 
      if (!visited[connected]) 

       //Check whatever the current one is connected to 
       DFSRecursive(connected, visited, edges); 
     } 


    } 

    public void DFS() { 

     //Check to see how many vertices graph has 
     int vertices = graph.getVertices(); 

     //Keeps track of which vertices have already been visited 
     boolean visited[] = new boolean[vertices]; 

     //Visits all of the nodes 
     for (int counter = 0; counter < vertices; ++counter) 

      //calls recursive method if this node has not been visited 
      if (!visited[counter]) 
       DFSRecursive(counter, visited, graph.getEdges()); 
    } 

    private Boolean isCyclicRecursive(int index, Boolean visited[], int 
    parent, LinkedList<Integer> edges[]) { 

     // Mark the current node as visited 
     visited[index] = true; 

     //Integer to hold what the node is connected to 
     Integer connection; 

     // Recur for all the vertices adjacent to this vertex 
     Iterator<Integer> iterator = edges[index].iterator(); 

     //Check to see if the current node has a connection 
     while (iterator.hasNext()) { 

      //Looks at what is connected to it. 
      connection = iterator.next(); 

      //If you haven't visited the connection, look at that. Sets the current as the parent of the connection. 
      if (!visited[connection]) { 
       cycle.add(index); 
       if (isCyclicRecursive(connection, visited, index, 
       graph.getEdges())) { 
        return true; 
       } else { 
        Integer item = new Integer(index); 
        cycle.remove(item); 
       } 
      } 

      //Checks to see if the thing it's connected to is its parent (you've completed a cycle) 
      else if (connection != parent) { 

       //Add parent and connection 
       cycle.add(index); 
       cycle.add(connection); 

       //Only find the things in current cycle 
       for (int i = 0; i < cycle.size(); i++) { 

        //Not a true cycle 
//     if (cycle.size() <= 1) 
//      return false; 

        int first = cycle.get(i); 
        int last = cycle.get(cycle.size() - 1); 

        if (first == last) { 
         System.out.print("Cycle Detected: "); 
         for (int j = 0; j < cycle.size(); j++) { 
          System.out.print(cycle.get(j).toString() + " "); 
         } 
         System.out.println(); 
         return true; 
        } else { 
         //only prints things actually in this cycle 
         cycle.remove(i); 
         i--; 
        } 
       } 
       return true; 
      } 
     } 

     return false; 
    } 

    /**************************************************************/ 
    /* Method: isCyclic 
    /* Purpose: Checks to see if graph is cyclic 
    /* Parameters: None 
    /* Returns: None 
    /**************************************************************/ 
    public Boolean isCyclic() { 

     //Mark all vertices as not visited 
     int vertices = graph.getVertices(); 

     Boolean visited[] = new Boolean[vertices]; 

     for (int counter = 0; counter < vertices; counter++) 
      visited[counter] = false; 

     //For every node, check if it is cyclic 
     for (int counter = 0; counter < vertices; counter++) 

      //Only check for cyclic if this has been visited 
      if (!visited[counter]) 
       if (isCyclicRecursive(counter, visited, -1, graph.getEdges())) 
        return true; 

     return false; 
    } 

} 

Answer 1

하나의 질문은 그래프가 간접적 인 경우 4-5 및 5-4를 별도의 가장자리로 간주하는 방법입니다. 나에게 방향이없는 그래프에서, 4-5와 5-4는 같은 모서리이므로주기가 아닙니다. 유향 그래프에서, 그것들은 구별되어 순환을 이룬다. 또한 그래프 배열의 길이가 2 인 객체는 모두 LinkedList입니까? 만약 당신이 방향을 바꾸고 싶다면 Set 구현으로 그래프의 LinkedList 오브젝트를 대체 할 수는 있지만 로직을 변경해야합니다.

어쨌든 관련성이있는 것 같습니다. Best algorithm for detecting cycles in a directed graph