参考
https://blog.csdn.net/login_sonata/article/details/78002042
自己根据题的意思算法
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Main {
//邻接矩阵
static int[][] graph;
//结点个数和边的个数
static int vNum,eNum;
//标记矩阵,0为当前结点未访问,1为访问过,-1表示当前结点后边的结点都被访问过。
static int[] color = new int[10];
//是否是DAG(有向无环图)
static boolean isDAG = true;
//图的深度遍历函数
static void DFS(int i){
System.out.println("正在访问结点"+i);
//结点i变为访问过的状态
color[i] = 1;
for(int j=1;j<=vNum;j++){
//如果当前结点有指向的结点
if(graph[i][j] != 0){
//并且已经被访问过
if(color[j] == 1){
isDAG = false;//有环
break;
}else if(color[j] == -1){
//当前结点后边的结点都被访问过,直接跳至下一个结点
continue;
}else{
DFS(j);//否则递归访问
}
}
}
//遍历过所有相连的结点后,把本节点标记为-1
color[i] = -1;
}
public static int graph_circle_checker(String graph_string){
List<Character> lists = new ArrayList<>();
for (int i = 0; i < graph_string.length(); i++) {
if(graph_string.charAt(i) == ','){
++eNum;
}
if(graph_string.charAt(i) >= 65 && graph_string.charAt(i) <= 90){
if(!lists.contains(graph_string.charAt(i))){
lists.add(graph_string.charAt(i));
}
}
}
eNum = eNum + 1;
vNum = lists.size();
graph = new int[vNum + 1][vNum + 1];
color = new int[vNum + 1];
//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
for(int i=1;i<=vNum;i++){
for(int j=1;j<=vNum;j++){
graph[i][j] = 0;
}
}
String[] sss =graph_string.split(",");
for(int k=1;k<=eNum;k++){
int i = -1;
int j = -1;
for (int m = 0; m < sss[k-1].length(); m++) {
if( sss[k-1].charAt(m) >= 65 && sss[k-1].charAt(m) <= 90){
if(i==-1){
i = sss[k-1].charAt(m)-64;
}else {
j = sss[k-1].charAt(m)-64;
graph[i][j] = 1;
}
}
}
}
//初始化color数组为0,表示一开始所有顶点都未被访问过
for(int i=1;i<=vNum;i++){
color[i] = 0;
}
//保证每个节点都遍历到,排除有的结点没有边的情况
for(int i=1;i<=vNum;i++){
//该结点后边的结点都被访问过了,跳过它
if(color[i] == -1){
continue;
}
DFS(i);
if(!isDAG){
System.out.println("有环!");
break;
}
}
if(isDAG){
System.out.println("没环。。。");
}
return 1;
}
public static void main(String[] args) {
System.out.println(graph_circle_checker("{(A - B),(B - C),(C - A)}"));
}
}