java遍历有向图_循环有向图的遍历

循环有向图的遍历可以使用拓扑排序算法。拓扑排序算法可以将有向无环图（DAG）中的节点按照一定的顺序排序，使得所有的有向边均从排在前面的节点指向排在后面的节点。如果图中存在环，则无法进行拓扑排序。

具体实现步骤如下：

1. 统计每个节点的入度（即有多少条边指向该节点），并将入度为0的节点加入队列中。

2. 从队列中取出一个节点，将该节点加入遍历结果中，并将该节点指向的节点的入度减1。

3. 如果某个节点的入度变为0，则将该节点加入队列中。

4. 重复步骤2和3，直到队列为空。

如果遍历结束后，遍历结果中的节点数小于原图中的节点数，则说明图中存在环。

以下是Java代码实现：

import java.util.*;

public class GraphTraversal {
    public static List<Integer> topologicalSort(int[][] graph) {
        int n = graph.length;
        int[] inDegree = new int[n];
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        // 统计入度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    inDegree[j]++;
                }
            }
        }

        // 将入度为0的节点加入队列中
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 拓扑排序
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int i = 0; i < n; i++) {
                if (graph[node][i] == 1) {
                    inDegree[i]--;
                    if (inDegree[i] == 0) {
                        queue.offer(i);
                    }
                }
            }
        }

        if (result.size() < n) {
            // 图中存在环
            return null;
        } else {
            return result;
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}};
        List<Integer> result = topologicalSort(graph);
        if (result == null) {
            System.out.println("该图存在环！");
        } else {
            System.out.println("拓扑排序结果：" + result);
        }
    }
}

上述代码中，输入的图以邻接矩阵的形式表示，0表示无边，1表示有边。输出结果为拓扑排序的结果，如果图中存在环，则输出“该图存在环！”。