所以下面是我的代码,用于查找图是否在有向图中具有欧拉循环。该代码适用于多种情况(我的main方法中的注释行有效)。但这确实适用于g1图(我的main方法中未注释的代码)。它说图形(g1)并非应该是欧拉回路。请帮助我找出错误,谢谢
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
public class EulerianCirlsDirected {
int v;
Set<Integer> visitedDFS;
int in[];
HashMap<Integer,List<Integer>> adjList;
public EulerianCirlsDirected(int v){
this.visitedDFS = new HashSet<Integer>();
this.adjList = new HashMap<Integer,List<Integer>>();
this.v = v;
in = new int[v];
}
//add edge
public void addEdge(int src, int dest){
List<Integer> srcNeighbour = this.adjList.get(src);
if(srcNeighbour == null){
this.adjList.put(src, srcNeighbour = new ArrayList<Integer>());
}
srcNeighbour.add(dest);
in[dest]++;
}
//get neighbours of vertex
public Iterable<Integer> getNeighbours(Integer vertex){
List<Integer> neighbours = this.adjList.get(vertex);
if(neighbours == null){
return Collections.emptyList();
}
else{
return Collections.unmodifiableList(neighbours);
}
}
public int sizeNeighbours(Integer vertex){
List<Integer> list = (List<Integer>) this.getNeighbours(vertex);
return list.size();
}
//depth first search
public Iterable<Integer> DFS(Integer src){
Stack<Integer> stack= new Stack<Integer>();
List<Integer> paths = new ArrayList<Integer>();
stack.add(src);
visitedDFS.add(src);
paths.add(src);
while(!stack.isEmpty()){
int ref = stack.pop();
for(int neig : this.getNeighbours(ref)){
if(!visitedDFS.contains(neig)){
stack.add(neig);
visitedDFS.add(neig);
paths.add(neig);
}
}
}
return Collections.unmodifiableSet(visitedDFS);
}
public int numVertices(){
return this.v;
}
//transpose of graph
public EulerianCirlsDirected getTranspose(){
int v = this.numVertices();
EulerianCirlsDirected gr = new EulerianCirlsDirected(v);
for(int i=0; i<v;i++){
for(int neig:this.getNeighbours(i)){
gr.addEdge(neig, i);
}
}
return gr;
}
//checks if graph has a eulerian cycle
public boolean isEulerianCycle(){
int v = this.numVertices();
//check if graph is connect
//that is every non zero degree vertex is part
//of a strongly connected component
if(!isConnected()){
return false;
}
//check for indegree and out degree
for(int i=0;i<v;i++){
if(in[i] != this.adjList.get(i).size()){
return false;
}
}
return true;
}
//method to verify for strongly connected component
public boolean isConnected(){
int v =this.numVertices();
int i;
//get the first non zero degre vertex
for( i=0; i<v;i++){
if(this.sizeNeighbours(i)>0){break;}
}
//first run dfs for original graph at the first non
//zero degree vertex
this.DFS(i);
//check if all vertices where visited during dfs
for(int j=0;j<v;j++){
if(!visitedDFS.contains(j)){
System.out.println("first " +visitedDFS.contains(j));
return false;
}
}
//get transpose of graph and run dfs
//so we have to reset visitedDFS
visitedDFS.clear();
EulerianCirlsDirected gr = this.getTranspose();
//update visitedDFS to be that of the
//transpose
visitedDFS= (Set<Integer>) gr.DFS(i);
//check again if all vertices are visited in the
//transposed graph
int grV = gr.numVertices();
for(int j=0;j<grV;j++){
if(!visitedDFS.contains(j)){
return false;
}
}
return true;
}
public static void main(String[]args){
// EulerianCirlsDirected g = new EulerianCirlsDirected(2);
// g.addEdge(0, 1);
// g.addEdge(1, 0);
// g.addEdge(2, 3);
// g.addEdge(3, 0);
// g.addEdge(2, 4);
// g.addEdge(4, 2);
EulerianCirlsDirected g1 = new EulerianCirlsDirected(26);
g1.addEdge(6, 10);
g1.addEdge(10, 6);
System.out.println(g1.isEulerianCycle());
//System.out.println(g.sizeNeighbours(1));
}
}
输出为假。请帮忙
最佳答案
当您用26构造EulerianCirlsDirected时,您的代码预期将有26个顶点,并且DFS都将触及它们。
更换
EulerianCirlsDirected g1 = new EulerianCirlsDirected(26);
g1.addEdge(6, 10);
g1.addEdge(10, 6);
与
EulerianCirlsDirected g1 = new EulerianCirlsDirected(2);
g1.addEdge(0, 1);
g1.addEdge(1, 0);
它会工作。
或者,每次从0迭代到v时都要检查
this.sizeNeighbours(i) > 0
。在isConnected()
中两次,在isEurlerianCycle()
中一次关于java - 有向图中欧拉循环的问题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25236331/