在无向图检查奇数周期 [英] Checking for odd cycles in an undirected graph
问题描述
我回来了另一个类似的问题。我目前工作的一个Java程序，将检查如果一个图是2 - 着色，即，如果它不包含奇周期（奇数长周期）。整个算法应该运行在O（V + E）时（V为所有顶点和E是图中的所有边）。我现在的算法做了深度优先搜索，记录在它采取的路径上的所有顶点，然后查找后边缘，然后记录之间顶点的边缘之间。接着，它跟踪从后缘的一端的通路，直到遇到的边缘的另一端上的另一顶点，从而折回后缘完成该循环。
我下的是IM pression，这种遍历可以在O完成（V + E）的时间存在于我的图中的所有周期，但我一定是失去了一些东西，因为我的算法运行一个可笑的很长一段时间非常大图（10K节点，不知道有多少边）。
是我的算法完全错误的？如果是的话，任何人都可以点我在正确的方向一个更好的方式来记录这些周期也可能告诉我们，如果他们有顶点奇数？感谢您的任何和所有帮助你们可以给。 code以下是如果你需要它。
增加：对不起，我忘了，如果图不是2 - 着色，我需要提供一个奇怪的循环，证明它不是
。 包algorithms311;
导入的java.util。*;
进口java.io. *;
公共类CS311 {
公共静态LinkedList的[] DFSIter（顶点[] V）{
LinkedList的[] VOandBE =新的LinkedList [2];
VOandBE [0] =新链表（）;
VOandBE [1] =新链表（）;
堆栈堆栈=新的堆栈（）;
stack.push（ⅴ[0]）;
v [0] .setColor（灰色）;
而（！stack.empty（））{
顶点u =（顶点）stack.peek（）;
LinkedList的adjList = u.getAdjList（）;
VOandBE [0]。新增（u.getId（））;
布尔allVisited =真;
的for（int i = 0; I＆LT; adjList.size（）;我++）{
如果（ⅴ[（整数）adjList.get（ⅰ）]。的getColor（）。等于（白））{
allVisited = FALSE;
打破;
}
否则如果（ⅴ[（整数）adjList.get（ⅰ）]的getColor（）等于（灰色）及。＆安培;！u.get preV（）=（整数）adjList.get㈠ ）{
INT []边=新INT [2]; //对顶点的
边缘[0] = u.getId（）; //从u
边缘[1] =（整数）adjList.get（ⅰ）; //到v
VOandBE [1]。新增（边缘）;
}
}
如果（allVisited）{
u.setColor（黑）;
stack.pop（）;
}
其他 {
的for（int i = 0; I＆LT; adjList.size（）;我++）{
如果（ⅴ[（整数）adjList.get（ⅰ）]。的getColor（）。等于（白））{
stack.push（ⅴ[（整数）adjList.get（ⅰ）]）;
v [（整数）adjList.get（ⅰ）] setColor（灰色）。
v [（整数）adjList.get（一）集合preV（u.getId（））。
打破;
}
}
}
}
返回VOandBE;
}
公共静态无效checkForTwoColor（字符串G）{//输入格式的图形作为分配
字符串图=克;
尝试 {
中输入文件// --read第一线
顶点// --Find数
的FileReader文件1 =新的FileReader（W：\\文件\\的NetBeansProjects \\ algorithms311 \\ \\的src \\ algorithms311+图）
的BufferedReader bReaderNumEdges =新的BufferedReader（文件1）;
串numVertS = bReaderNumEdges.readLine（）;
INT numVert =的Integer.parseInt（numVertS）;
的System.out.println（numVert +顶点）;
// --make顶点
顶点顶点[] =新的顶点[numVert]
对于（INT K = 0; K＆LT; = numVert - 1; k ++）{
顶点[K] =新的顶点（K）;
}
// --Adj列表
的FileReader文件2 =新的FileReader（W：\\文件\\的NetBeansProjects \\ algorithms311 \\ \\的src \\ algorithms311+图）
的BufferedReader bReaderEdges =新的BufferedReader（文件2）;
bReaderEdges.readLine（）; //跳过第一行，那是多少个顶点有
字符串边缘;
而（（边= bReaderEdges.readLine（））！= NULL）{
StringTokenizer的ST =新的StringTokenizer（边）;
INT vArr [] =新INT [2];
为（诠释J = 0; ST.hasMoreTokens（）; J ++）{
vArr [J] =的Integer.parseInt（ST.nextToken（））;
}
顶点[vArr [0] -1] .addAdj（vArr [1] -1）;
顶点[vArr [1] -1] .addAdj（vArr [0] -1）;
}
LinkedList的[] L =新的LinkedList [2];
升= DFSIter（顶点）; // DFS（顶点）;
的System.out.println（升[0]）;
的for（int i = 0; I＆LT; L [1] .size（）;我++）{
INT [J] =（INT []）L [1]获得（一）;
System.out.print（[+ J [0] +，+ J [1] +]）;
}
LinkedList的oddCycle =新的LinkedList（）;
布尔is2Colorable =真;
通过对背部边缘）名单//System.out.println("iterate;
的for（int i = 0; I＆LT; L [1] .size（）;我++）{//遍历的背面边缘名单
//System.out.println(i）;
INT [] Q =（INT []）（升[1]。获得（i））的; // Q =对顶点构成的后缘
INT U = Q [0]; //边（u，v）的
INT V = Q [1];
LinkedList的周期=新的LinkedList（）;
如果（L [0] .indexOf（U）其中，L [0] .indexOf（V））{//检查是否u是v在
对于（INT Z = L [0] .indexOf（U）; Z＆LT; = L [0] .indexOf（V）; Z ++）{//如果是，则查找U第;从u到v
cycle.add（升[0]。获得（Z））;
}
}
否则如果（L [0] .indexOf（ⅴ）＆其中;升[0] .indexOf（U））{
对于（INT Z = L [0] .indexOf（V）; Z＆LT; = L [0] .indexOf（U），Z ++）{//如果是，则查找U第;从u到v
cycle.add（升[0]。获得（Z））;
}
}
如果（（cycle.size（）及！1）= 0）{//如果它有一个奇怪的循环，打印出的循环节点或把它们写入一个文件
is2Colorable = FALSE;
oddCycle =循环;
打破;
}
}
如果（！is2Colorable）{
的System.out.println（图不是2 - 着色，奇圈存在）;
如果（oddCycle.size（）＆其中; = 50）{
的System.out.println（oddCycle）;
}
其他 {
尝试 {
BufferedWriter将不过outFile =新的BufferedWriter（新的FileWriter（W：\\文件\\的NetBeansProjects \\ algorithms311 \\ \\的src \\ algorithms311+图形+OddCycle.txt））;
字符串CYC = oddCycle.toString（）;
outFile.write（CYC）;
outFile.close（）;
}
赶上（IOException异常E）{
的System.out.println（无法写入文件）;
}
}
}
}
赶上（IOException异常E）{
的System.out.println（无法打开文件）;
}
的System.out.println（完成！）;
}
公共静态无效的主要（字串[] args）{
// checkForTwoColor（smallgraph1）;
// checkForTwoColor（smallgraph2）;
// checkForTwoColor（smallgraph3）;
// checkForTwoColor（smallgraph4）;
checkForTwoColor（smallgraph5）;
// checkForTwoColor（largegraph1）;
}
}
顶点类
包algorithms311;
导入的java.util。*;
公共类顶点实现可比{
公众诠释ID;
公共LinkedList的adjVert =新的LinkedList（）;
公共串色=白;
公众诠释DTIME;
公众诠释FTIME;
公众诠释preV;
公共布尔走访= FALSE;
公共顶点（INT IDNUM）{
ID = IDNUM;
}
公众诠释的getId（）{
返回ID;
}
公众诠释的compareTo（obj对象）{
顶点VERT =（顶点）目标文件;
返回的id-vert.getId（）;
}
@覆盖公共字符串的toString（）{
返回顶点＃+ ID;
}
公共无效setColor（字符串newColor）{
颜色= newColor;
}
公共字符串的getColor（）{
返回的颜色;
}
公共无效setDTime（INT D）{
DTIME = D;
}
公共无效setFTime（INT F）{
FTIME = F;
}
公众诠释getDTime（）{
返回DTIME;
}
公众诠释getFTime（）{
返回FTIME;
}
公共无效套preV（INT V）{
preV = V;
}
公众诠释的get preV（）{
返回preV;
}
公共链表getAdjList（）{
返回adjVert;
}
公共无效addAdj（INT一）{//增加了一个顶点ID这个顶点的形容词名单
adjVert.add（一）;
}
公共无效访问（）{
走访= TRUE;
}
公共布尔wasVisited（）{
返回访问;
}
}
我下的是IM pression，这种遍历可以在O完成（V + E）的时间存在于我的图中的所有周期
可以存在为O得多周期（V + E）中的曲线图。如果你遍历所有的人，你会运行长。
回到你原来的想法，你可以只尝试实施两种颜色一个简单的算法，色彩图（标注任意节点为黑色，在黑色等白色，所有的邻居都邻国，这将是一个广度 - 第一搜索）。这是为O的确做到了（V + E）的时间。如果你成功了，那么图是2着色。如果你失败了，不是这样的。
编辑：如果你需要一个周期来证明图是不是2 - 着色，只为每个节点记录你走过进去的顶点。如果你碰巧从黑色顶点A以黑色顶点B至遍历（因此需要以色黑B为白色，并证明你的图形是不是2着色），你看回父母得到循环：
X - ＆GT; Ÿ - ＆GT; ž - ＆GT; ü - ＆GT; v - 输出＆GT;对 - ＆GT; Q - ＆GT;一个 \ - ＆GT; ð - ＆GT; Ë - ＆GT;乙
然后， ABEDVPQ （路径到他们共同的祖先）是你所需要的周期。
请注意，在这个版本中，你不需要检查的所有的周期，你只输出第一周期，其中，背缘树有颜色的同色两种顶点。
I'm back with another similar question. I am currently working on a Java program that will check if a graph is 2-colorable, i.e. if it contains no odd cycles (cycles of odd number length). The entire algorithm is supposed to run in O(V+E) time (V being all vertices and E being all edges in the graph). My current algorithm does a Depth First Search, recording all vertices in the path it takes, then looks for a back edge, and then records between which vertices the edge is between. Next it traces a path from one end of the back edge until it hits the other vertex on the other end of the edge, thus retracing the cycle that the back edge completes.
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, but I must be missing something, because my algorithm is running for a ridiculously long time for very large graphs (10k nodes, no idea how many edges).
Is my algorithm completely wrong? And if so, can anyone point me in the right direction for a better way to record these cycles or possibly tell if they have odd numbers of vertices? Thanks for any and all help you guys can give. Code is below if you need it.
Addition: Sorry I forgot, if the graph is not 2-colorable, I need to provide an odd cycle that proves that it is not.
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 class
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
There may be much more cycles than O(V+E) in a graph. If you iterate all of them, you will run long.
Back to your original idea, you could just try to implement a straightforward algorithm to color graph in two colors (mark an arbitrary node as black, all neighbors in white, all their neighbors in black, etc; that would be a breadth-first search). That is indeed done in O(V+E) time. If you succeed, then graph is 2-colorable. If you fail, it's not.
Edit: If you need a cycle that proves graph is not 2-colorable, just record for each node the vertex you traversed into it from. When you happen to traverse from black vertex A to black vertex B (thus needing to color black B into white and proving your graph is not 2-colorable), you get the cycle by looking back to parents:
X -> Y -> Z -> U -> V -> P -> Q -> A
\-> D -> E -> B
Then, A-B-E-D-V-P-Q (the paths up to their common ancestor) is the cycle you needed.
Note that in this version you don't have to check all cycles, you just output a first cycle, where back-edge in the tree has both vertexes colored in the same color.
这篇关于在无向图检查奇数周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
