무방향 그래프에서 홀수 주기 확인

Question

또 다른 비슷한 질문으로 돌아왔습니다.저는 현재 그래프가 2색 가능한지 확인하는 Java 프로그램을 작성 중입니다.홀수 사이클(홀수 길이의 사이클)을 포함하지 않는 경우.전체 알고리즘은 O(V+E) 시간에 실행되어야 합니다(V는 그래프의 모든 정점이고 E는 모든 가장자리임).내 현재 알고리즘은 깊이 우선 검색을 수행하여 경로의 모든 정점을 기록한 다음 뒤쪽 가장자리를 찾은 다음 가장자리가 어느 정점 사이에 있는지 기록합니다.다음으로 뒤쪽 가장자리의 한쪽 끝에서 가장자리의 다른 쪽 끝의 다른 꼭지점에 도달할 때까지 경로를 추적하여 뒤쪽 가장자리가 완료되는 주기를 되돌립니다.

나는 내 그래프에 존재하는 모든 사이클에 대해 이런 종류의 순회가 O(V+E) 시간에 완료될 수 있다는 인상을 받았습니다. 그러나 내 알고리즘이 매우 큰 기간 동안 터무니없이 오랜 시간 동안 실행되기 때문에 뭔가 빠진 것이 틀림없습니다. 그래프(10,000개 노드, 가장자리 수는 알 수 없음)

내 알고리즘이 완전히 잘못된 걸까요?그렇다면 누구든지 이러한 주기를 기록하는 더 나은 방법을 위해 올바른 방향을 알려주거나 정점 수가 홀수인지 알려줄 수 있습니까?여러분이 줄 수 있는 모든 도움에 감사드립니다.필요한 경우 코드는 아래에 있습니다.

덧셈:죄송합니다. 그래프가 2색 색상이 아닌 경우 그렇지 않다는 것을 증명하는 홀수 주기를 제공해야 한다는 점을 잊어버렸습니다.

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색이 가능합니다.실패하면 그렇지 않습니다.

편집하다: 그래프가 2색을 지원하지 않음을 증명하는 사이클이 필요한 경우 각 노드에 대해 해당 노드로 이동한 정점을 기록하면 됩니다.검은색 정점 A에서 검은색 정점 B로 이동하는 경우(따라서 검은색 B를 흰색으로 채색하고 그래프가 2색 가능하지 않음을 증명해야 함) 부모를 다시 살펴봄으로써 순환을 얻습니다.

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

그 다음에, A-B-E-D-V-P-Q (공통 조상까지의 경로)는 필요한 순환입니다.

이 버전에서는 확인할 필요가 없습니다. 모두 사이클을 사용하면 트리의 뒤쪽 가장자리에 두 정점이 모두 동일한 색상으로 표시되는 첫 번째 사이클이 출력됩니다.

Answer 2

이분 그래프를 설명하고 있습니다.이분 그래프는 2개의 색상을 지정할 수 있으며 홀수 길이의 주기를 포함하지 않습니다.BFS를 사용하여 그래프가 이분형인지 아닌지 증명할 수 있습니다.도움이 되었기를 바랍니다.