java - 查找并打印无向图中的循环

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;
    }

}

-- 遍历和循环搜索

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 是同一条边，因此不是循环。在有向图上，它们是不同的，因此确实形成了一个循环。另外，图形数组中的所有 LinkedList 对象的长度都是 2 吗？如果您想要无向，可以用 Set 实现替换图中的 LinkedList 对象，但这需要更改一些逻辑。

无论如何，这似乎相关:Best algorithm for detecting cycles in a directed graph