java – 检查无向图中的奇数周期

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 检查无向图中的奇数周期，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6790字，纯文字阅读大概需要10分钟。

内容图文

我回来了另一个类似的问题.我目前正在研究一个Java程序,它将检查图形是否是2可着色的,即它是否包含没有奇数周期(奇数长度的周期).假设整个算法在O(V E)时间内运行(V是所有顶点,E是图中的所有边).我当前的算法执行深度优先搜索,记录它所采用的路径中的所有顶点,然后查找后边缘,然后记录边缘位于哪些顶点之间.接下来,它跟踪从后边缘的一端开始的路径,直到它到达边缘另一端的另一个顶点,从而回溯后边缘完成的循环.

我的印象是这种遍历可以在我的图中存在的所有周期的O(VE)时间内完成,但我必须遗漏一些东西,因为我的算法对于非常大的图形运行了非常长的时间( 10k节点,不知道有多少边缘).

我的算法完全错了吗？如果是这样,任何人都可以指出我正确的方向来更好地记录这些周期或可能告诉他们是否有奇数个顶点？感谢您提供的任何和所有帮助.如果您需要,代码如下.

另外：对不起,我忘了,如果图表不是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;
    }
}

解决方法:

I was under the impression that this kind of traversing could be done in O(V+E) time for all cycles that exist in my graph

图中可能存在比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(达到它们共同祖先的路径)就是你需要的循环.

请注意,在此版本中,您不必检查所有周期,只需输出第一个周期,其中树中的后边缘使两个顶点都以相同颜色着色.

内容总结

以上是互联网集市为您收集整理的java – 检查无向图中的奇数周期全部内容，希望文章能够帮你解决java – 检查无向图中的奇数周期所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端