Проверка на наличие нечетных циклов в неориентированном графе

Question

Я возвращаюсь к другому аналогичному вопросу.В настоящее время я работаю над Java-программой, которая будет проверять, является ли график двухцветным, т.е.если он не содержит нечетных циклов (циклов нечетной длины).Предполагается, что весь алгоритм должен выполняться за O (V + E) времени (V - все вершины, а E - все ребра графа).Мой текущий алгоритм выполняет поиск в глубину, записывая все вершины на пройденном пути, затем ищет заднее ребро, а затем записывает, между какими вершинами находится ребро.Затем он прослеживает путь от одного конца заднего ребра до тех пор, пока не достигнет другой вершины на другом конце ребра, таким образом повторяя цикл, который завершает задний ребро.

У меня сложилось впечатление, что такой обход может быть выполнен за O (V + E) время для всех циклов, которые существуют в моем графике, но я, должно быть, что-то упускаю, потому что мой алгоритм работает смехотворно долго для очень больших графиков (10 тыс. узлов, понятия не имею, сколько ребер).

Является ли мой алгоритм полностью неправильным?И если да, может ли кто-нибудь указать мне правильное направление для лучшего способа записи этих циклов или, возможно, сказать, имеют ли они нечетное количество вершин?Спасибо за любую помощь, которую вы, ребята, можете оказать.Код приведен ниже, если он вам нужен.

Дополнение:Извините, я забыл, если график не является двухцветным, мне нужно предоставить нечетный цикл, который доказывает, что это не так.

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

Класс вершин

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

У меня сложилось впечатление, что такой обход может быть выполнен за O (V + E) время для всех циклов, которые существуют на моем графике

На графике может быть гораздо больше циклов, чем O (V + E).Если вы повторите их все, вы будете работать долго.

Возвращаясь к вашей первоначальной идее, вы могли бы просто попытаться реализовать простой алгоритм для раскрашивания графика в два цвета (пометить произвольный узел черным, всех соседей белым, всех их соседей черным и т. Д;это был бы поиск вширь).Это действительно делается за O (V + E) время.Если вам это удастся, то график можно будет раскрасить в 2 цвета.Если вы потерпите неудачу, это не так.

Редактировать: Если вам нужен цикл, который доказывает, что график не является двухцветным, просто запишите для каждого узла вершину, из которой вы в него вошли.Когда вам случается перейти от черной вершины A к черной вершине B (таким образом, вам нужно покрасить черный B в белый и доказать, что ваш график не является двухцветным), вы получаете цикл, оглядываясь назад на родителей:

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

Тогда, A-B-E-D-V-P-Q (пути вплоть до их общего предка) - это цикл, который вам нужен.

Обратите внимание, что в этой версии вам не нужно проверять ВСЕ циклы, вы просто выводите первый цикл, где задний край в дереве имеет обе вершины, окрашенные в один и тот же цвет.

Answer 2

вы описываете двудольный граф.двудольный граф может быть раскрашен в 2 цвета и не содержит циклов нечетной длины.Вы можете использовать BFS, чтобы доказать, является граф двудольным или нет.Надеюсь, это поможет.