- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
下面是我的代码,用于查找图是否在有向图中具有欧拉循环。该代码适用于多种情况(我的主要方法中的注释行有效)。但它确实适用于 g1 图(我的主要方法中未注释的代码)。它说图(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/
在编程中,我只使用整数。不过这次要进行一些计算。我需要计算Euler-Mascheroni Constant γ .最多 n 位小数。{虽然 n ∈ [30, 150]对我来说已经足够了。 [x] =
有人可以帮忙处理这段代码吗?它应该得到第 10,001 个素数。我知道 is_prime 函数可以测试一个数字是否为素数,因为我成功地利用此代码解决了上一个问题。现在我只是尝试在 for 循环中调用它
我发现了几个与这个问题相关的主题,我只是想知道为什么我的代码返回不正确的数据。所以我们必须找到第一个除数超过 500 的三角形数。详情可在此处找到:http://projecteuler.net/pr
#include int main(void) { char *num = "73167176531330624919225119674426574742355349194934"
我正在尝试投影欧拉问题 8,但是我遇到了问题。1000位数字中相邻四位的乘积最大为9×9×8×9=5832。 731671765313306249192251196744265747423553491
这是针对 Project Euler 19 的。我几乎想出了代码,但由于某种原因我的输出是 +1。 #include #define SIZE 12 int main(void) {
int main(void) { int n, div, a, b; double phi; printf("Enter n:\n"); if (scanf("%d", &n) < 1
欧拉问题: 如果我们列出所有 10 以下的自然数,它们是 3 或 5 的倍数,我们得到 3、5、6 和 9。这些倍数的和是 23。 求 1000 以下的所有 3 或 5 的倍数之和。 我试图从 pro
我知道这可能会被否决,但我真的很沮丧 24 小时,查看其他 Euler 3 线程并没有帮助我解决这个问题。有人可以帮助我的代码吗?我认为我非常接近。 function is_prime(num) {
我卡在了Question 7欧拉计划。我有这段代码。 #include int main (void) { int contador = 0, i, n, variavel = 0;
我正在尝试使用 sympy 的 idiff 函数对某些表达式执行隐式微分。 在本例中,rdot 为 dr/ds,其中 s 是仿射参数。我想对相同的仿射参数对 Ltdot、Lphidot 和 Lrdot
我正在尝试解决我的第一个项目 Euler 问题,只是为了玩 Rust,但被困在似乎需要极长计算时间的问题上 问题: https://projecteuler.net/problem=757 我想出了这
我正在学习C编程,并制定了以下算法来解决这个问题: 代码实际上有效,但最初循环只有 10 次重复(rep int main() { float p; //the power for e
我之前曾尝试暴力破解它,但没有成功。这是我的递归尝试#2(第一次使用递归方法)。请帮忙! 发生的情况是这样的:代码运行良好,数字较小,但是当我们达到一百万时,代码就会运行,并且什么也不会发生。在 Ec
Given a number find the 5 digits before the trailing 0. 9! = 362880 so f(9)=36288 10! = 3628800 so f
我是一名优秀的程序员,十分优秀!