Suchen und drucken Sie den Zyklus in einem ungerichteten Graphen

Ich bin dabei eine Aufgabe in der ich müssen tun, um ein DFS ein ungerichteter graph, und drucken Sie dann ein Zyklus, wenn eine gefunden wird. Das Problem ist, dass alle algorithmen, die ich finden kann für die Suche nach Zyklus nicht speichern der Zyklus-Sie sind einfach „wahr/falsch“. Mein Aktueller code funktioniert nur für ein paar Grafiken, aber nicht für andere. Zum Beispiel, kann es nicht finden, ein 2-Knoten-Zyklus (4-5, 5-4). Auch, es funktioniert nur für die Regie, jetzt, wo es sein sollte ungerichtete.

Edit: ist das nicht ein Duplikat der anderen Fragen zu finden und Druck-Zyklen, weil soweit ich sehen kann, keine andere Probleme angesprochen, wie speichern und anschließend drucken Sie eine Zyklus-nur wie, um herauszufinden, ob oder nicht, es existiert und die Rückgabe true/false.

Edit: Formatierung

Anbei meine traversal code und meine main-Methode

— Main-Methode

    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");

    }

— Graph-Klasse

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

}

— Traversal und Zyklische Suche

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

}
InformationsquelleAutor | 2017-10-26



One Reply
  1. 1

    Eine Frage, die ich habe, ist, wie man bedenkt, 4-5 und 5-4, die als separate Kanten, wenn Ihr graph wird ungerichteter? Für mich, in einem ungerichteten Graphen, 4-5 und 5-4 sind die gleichen Kante, und damit nicht in einem Zyklus. Auf einem gerichteten Graphen, Sie sind Verschieden und daher einen Zyklus bilden. Außerdem sind alle LinkedList Objekte in der graph-array der Länge 2? Wenn Sie möchten, ungerichtete, die Sie ersetzen könnten die LinkedList Objekte in der Grafik mit einem Set – Implementierung, aber es würde die änderung einige Ihrer Logik.

    Sowieso, das scheint relevant: Am besten Algorithmus für die Erkennung von Zyklen in einem gerichteten Graphen

    • Vielen, vielen Dank! Ich werde schauen Sie in ändern, um einen Satz implimentation. Auch ich geirrt 4-5 und 5-4, sollten Sie nicht erkannt werden als ein Zyklus.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.