判断图是否有环_判断dag是否存在环 c++

参考
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)}"));

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106