Überprüfen auf ungeraden Zyklen in einem ungerichteten Graphen

Question

Ich bin wieder mit einer neuen ähnlichen Frage. Ich arbeite derzeit an einem Java-Programm, das überprüft, ob ein Graph 2-färbbar ist, das heißt, wenn es keine ungeradeen Zyklen (Zyklen der ungeraden Anzahl Länge) enthält. Der gesamte Algorithmus soll in O (V + E) Zeit (V wobei alle Ecken und E sind alle Kanten in dem Graphen) laufen. Mein aktueller Algorithmus hat eine Tiefensuche, Aufzeichnung alle Eckpunkt auf dem Weg es nimmt, sucht dann nach einer Hinterkante, und dann Datensätze zwischen dem Scheitel der Kante zwischen. es nächstes folgt einem Weg von einem Ende der Hinterkante, bis er den anderen Scheitelpunkt am anderen Ende der Kante trifft, wodurch der Zyklus zurückzuverfolgen, dass die hintere Kante abgeschlossen ist.

Ich hatte den Eindruck, dass diese Art der Verfahrgeschwindigkeit in O (V + E) Zeit für alle Zyklen, die in meinem Diagramm existieren getan werden könnte, aber ich muss etwas fehlt, weil mein Algorithmus für eine lächerlich lange Zeit läuft für sehr große Graphen (10k Knoten, keine Ahnung, wie viele Kanten).

Ist mein Algorithmus völlig falsch? Und wenn ja, kann mir jemand einen besseren Weg in die richtige Richtung weisen diese Zyklen aufzuzeichnen oder möglicherweise sagen, wenn sie ungerade Zahlen von Eckpunkten haben? Vielen Dank für jede und alle helfen ihr geben können. Code ist unten, wenn Sie es brauchen.

Zusatz: Leider habe ich vergessen, wenn der Graph nicht 2-färbbar ist, brauche ich einen ungeradeen Zyklus zu schaffen, der beweist, dass es nicht

.

package algorithms311;

import java.util.*;
import java.io.*;

public class CS311 {

public static LinkedList[] DFSIter(Vertex[] v) {
    LinkedList[] VOandBE = new LinkedList[2];
    VOandBE[0] = new LinkedList();
    VOandBE[1] = new LinkedList();

    Stack stack = new Stack();

    stack.push(v[0]);
    v[0].setColor("gray");

    while(!stack.empty()) {
        Vertex u = (Vertex) stack.peek();
        LinkedList adjList = u.getAdjList();
        VOandBE[0].add(u.getId());

        boolean allVisited = true;
        for(int i = 0; i < adjList.size(); i++) {
            if(v[(Integer)adjList.get(i)].getColor().equals("white")) {
                allVisited = false;
                break;
            }
            else if(v[(Integer)adjList.get(i)].getColor().equals("gray") && u.getPrev() != (Integer)adjList.get(i)) {
                int[] edge = new int[2]; //pair of vertices
                edge[0] = u.getId(); //from u
                edge[1] = (Integer)adjList.get(i); //to v
                VOandBE[1].add(edge);
            }
        }
        if(allVisited) {
            u.setColor("black");
            stack.pop();
        }
        else {
            for(int i = 0; i < adjList.size(); i++) {
                if(v[(Integer)adjList.get(i)].getColor().equals("white")) {
                    stack.push(v[(Integer)adjList.get(i)]);
                    v[(Integer)adjList.get(i)].setColor("gray");
                    v[(Integer)adjList.get(i)].setPrev(u.getId());
                    break;
                }
            }
        }
    }
    return VOandBE;
}

public static void checkForTwoColor(String g) { //input is a graph formatted as assigned

    String graph = g;

    try {

        // --Read First Line of Input File
        // --Find Number of Vertices

        FileReader file1 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + graph);
        BufferedReader bReaderNumEdges = new BufferedReader(file1);

        String numVertS = bReaderNumEdges.readLine();
        int numVert = Integer.parseInt(numVertS);

        System.out.println(numVert + " vertices");





        // --Make Vertices

        Vertex vertex[] = new Vertex[numVert];

        for(int k = 0; k <= numVert - 1; k++) {
            vertex[k] = new Vertex(k);
        }

        // --Adj Lists


        FileReader file2 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + graph);
        BufferedReader bReaderEdges = new BufferedReader(file2);
        bReaderEdges.readLine(); //skip first line, that's how many vertices there are

        String edge;

        while((edge = bReaderEdges.readLine()) != null) {

            StringTokenizer ST = new StringTokenizer(edge);

            int vArr[] = new int[2];
            for(int j = 0; ST.hasMoreTokens(); j++) {
                vArr[j] = Integer.parseInt(ST.nextToken());
            }


            vertex[vArr[0]-1].addAdj(vArr[1]-1);
            vertex[vArr[1]-1].addAdj(vArr[0]-1);

        }

        LinkedList[] l = new LinkedList[2];

        l = DFSIter(vertex);//DFS(vertex);

        System.out.println(l[0]);



        for(int i = 0; i < l[1].size(); i++) {
            int[] j = (int[])l[1].get(i);
            System.out.print(" [" + j[0] + ", " + j[1] + "] ");
        }



        LinkedList oddCycle = new LinkedList();
        boolean is2Colorable = true;


        //System.out.println("iterate through list of back edges");

        for(int i = 0; i < l[1].size(); i++) { //iterate through the list of back edges
            //System.out.println(i);
            int[] q = (int[])(l[1].get(i)); // q = pair of vertices that make up a back edge
            int u = q[0]; // edge (u,v)
            int v = q[1];

            LinkedList cycle = new LinkedList();

            if(l[0].indexOf(u) < l[0].indexOf(v)) { //check if u is before v
                for(int z = l[0].indexOf(u); z <= l[0].indexOf(v); z++) { //if it is, look for u first; from u to v
                    cycle.add(l[0].get(z));
                }
            }
            else if(l[0].indexOf(v) < l[0].indexOf(u)) {
                for(int z = l[0].indexOf(v); z <= l[0].indexOf(u); z++) { //if it is, look for u first; from u to v
                    cycle.add(l[0].get(z));
                }
            }



            if((cycle.size() & 1) != 0) { //if it has an odd cycle, print out the cyclic nodes or write them to a file

                is2Colorable = false;

                oddCycle = cycle;

                break;
            }
        }
        if(!is2Colorable) {
            System.out.println("Graph is not 2-colorable, odd cycle exists");
            if(oddCycle.size() <= 50) {
                System.out.println(oddCycle);
            }
            else {
                try {
                    BufferedWriter outFile = new BufferedWriter(new FileWriter("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + graph + "OddCycle.txt"));
                    String cyc = oddCycle.toString();
                    outFile.write(cyc);
                    outFile.close();
                }
                catch (IOException e) {
                    System.out.println("Could not write file");
                }
            }
        }
    }
    catch (IOException e) {
        System.out.println("Could not open file");
    }
    System.out.println("Done!");
}

public static void main(String[] args) {
        //checkForTwoColor("smallgraph1");
        //checkForTwoColor("smallgraph2");
        //checkForTwoColor("smallgraph3");
        //checkForTwoColor("smallgraph4");
        checkForTwoColor("smallgraph5");

        //checkForTwoColor("largegraph1");
    }
}

Vertex Klasse

package algorithms311;

import java.util.*;

public class Vertex implements Comparable {

    public int id;
    public LinkedList adjVert = new LinkedList();
    public String color = "white";
    public int dTime;
    public int fTime;
    public int prev;
    public boolean visited = false;

    public Vertex(int idnum) {
        id = idnum;
    }

    public int getId() {
        return id;
    }

    public int compareTo(Object obj) {
        Vertex vert = (Vertex) obj;
        return id-vert.getId();
    }

    @Override public String toString(){
        return "Vertex # " + id;
    }

    public void setColor(String newColor) {
        color = newColor;
    }

    public String getColor() {
        return color;
    }

    public void setDTime(int d) {
        dTime = d;
    }

    public void setFTime(int f) {
        fTime = f;
    }

    public int getDTime() {
        return dTime;
    }

    public int getFTime() {
        return fTime;
    }

    public void setPrev(int v) {
        prev = v;
    }

    public int getPrev() {
        return prev;
    }

    public LinkedList getAdjList() {
        return adjVert;
    }

    public void addAdj(int a) { //adds a vertex id to this vertex's adj list
        adjVert.add(a);
    }

    public void visited() {
        visited = true;
    }

    public boolean wasVisited() {
        return visited;
    }
}

Answer 1

  

Ich hatte den Eindruck, dass diese Art der Verfahrgeschwindigkeit in O (V + E) Zeit für alle Zyklen, die in meinem Diagramm existieren getan werden könnte

Es kann viel mehr Zyklen als O (V + E) in einem Graph. Wenn Sie alle von ihnen durchlaufen, laufen Sie lang.

Zurück zu Ihrer ursprünglichen Idee, könnte man nur versuchen, einen einfachen Algorithmus, um Farbe Diagramm in zwei Farben zu implementieren (einen beliebigen Knoten als schwarze Markierung, alle Nachbarn in wissen, alle ihre Nachbarn in schwarz, etc., dass eine Breite wäre -first Suche). Das ist in der Tat in O (V + E) Zeit. Wenn Sie Erfolg haben, dann ist Graph 2-färbbar. Wenn Sie scheitern, ist es nicht.

Edit: Wenn Sie einen Zyklus benötigen, die für jeden Knoten den Scheitelpunkt Sie in sie durchquert von Graphen ist nicht 2-färbbar, nur aufzeichnen beweist. Wenn Sie von schwarzer Ecke A bis schwarzer Spitze B durchqueren passieren (um so schwarz B in weiß zu färben und Ihr Diagramm beweist nicht 2-färbbar), erhalten Sie den Zyklus von den Eltern im Rückblick:

X -> Y -> Z -> U -> V -> P -> Q -> A 
                     \-> D -> E -> B

Dann A-B-E-D-V-P-Q (die Pfade bis zu ihrem gemeinsamen Vorfahren) ist der Zyklus Sie benötigen.

Beachten Sie, dass in dieser Version müssen Sie nicht überprüfen alle Zyklen, die Sie gerade Ausgang einen ersten Zyklus, in dem Back-Kante im Baum beide Spitzen in der gleichen Farbe gefärbt hat.

Answer 2

Sie beschreiben einen zweiteiligen Graphen. ein zweiteiliger Graph ist 2 färbbar, und es enthält keine ungerader Länge Zyklen. Sie können BFS verwenden zu beweisen, dass ein Graph bipartit ist oder nicht. Hoffe, das hilft.