我试图检测无向图中是否有任何循环 . 我试图在dfs方法中解决这个问题 . 我的逻辑是对于每个访问过的顶点'v'，如果有一个相邻的'u'使得你已经访问过u而你不是v的父亲，那么就有一个循环图表 . 如果我没有为任何顶点找到这样的相邻，我可以说没有循环 . 这是我的代码 .
import java.util.Scanner;
public class CheckCycle {
public static int nodeno;
public static int Matrix[][];
public static boolean Visited[];
//public static boolean hascycle=false;
public static int path[]=new int[50];
public static boolean returncycle(){
for(int i=0;i<nodeno;i++)
{
if(!Visited[i])
if( dfstocheck(i,-1))
return true;
}
return false;
}
public static boolean dfstocheck(int v,int parent){
Visited[v]=true;
for(int i=0;i<nodeno;i++) {
if (Matrix[v][i] == 1 && !Visited[i]) {
return (dfstocheck(i, v)) ;
}
else if (i != parent)
return true;
}
return false;
}
public static void main(String [] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
nodeno = in.nextInt();
Matrix = new int[nodeno][nodeno];
Visited = new boolean[nodeno];
Matrix = new int[nodeno][nodeno];
for (int i = 0; i < nodeno; i++) {
for (int j = 0; j < nodeno; j++) {
Matrix[i][j] = in.nextInt();
}
}
if(returncycle)
System.out.println("Contain cycle");
else
System.out.println("no cycle");
}
}
}
问题是我给出输入的邻接矩阵它没有返回循环 . 假设节点没有 5 第一个矩阵应该返回循环而第二个矩阵应该不返回循环 .
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 0 0 1
0 0 1 0 0
0 1 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
0 0 0 1 0
我只是找不到我的实施中的错误 . 有人可以帮忙吗？