拓扑排序判断有向图是否有环的java代码

拓扑排序是一种算法，用于对有向无环图(DAG, Directed Acyclic Graph)的顶点进行线性排序，使得对于每条边u -> v，顶点u都在顶点v之前。如果图中有环，则无法进行有效的拓扑排序。下面是一个简单的Java代码示例，使用邻接表表示图，并利用深度优先搜索(DFS)辅助判断是否有环：

import java.util.*;

class Node {
    int value;
    List<Node> neighbors;

    public Node(int value) {
        this.value = value;
        neighbors = new ArrayList<>();
    }
}

public class TopSort {
    public static boolean hasCycle(Node[] nodes) {
        if (nodes == null || nodes.length == 0) return false;

        Set<Integer> visited = new HashSet<>();
        for (Node node : nodes) {
            if (!dfs(node, visited)) return true; // 如果找到环，直接返回true
        }

        return false; // 所有节点都检查过，表示无环
    }

    private static boolean dfs(Node node, Set<Integer> visited) {
        if (node == null) return true; // 非节点值视为已访问

        if (visited.contains(node.value)) return false; // 已访问过的节点，有环

        visited.add(node.value);
        for (Node neighbor : node.neighbors) {
            if (!dfs(neighbor, visited)) return false; // 对邻居递归调用
        }

        return true;
    }

    public static void main(String[] args) {
        // 创建节点并连接边
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.neighbors.add(n2);
        n2.neighbors.add(n3);

        // 判断是否有环
        boolean hasCycleResult = hasCycle(new Node[]{n1, n2, n3});
        System.out.println(hasCycleResult ? "图中有环" : "图中无环");
    }
}

在这个例子中，`hasCycle`方法首先遍历所有节点，如果发现某个节点已经被访问过，说明存在环。如果没有找到这样的节点，那么整个图就是有向无环图。