Leetcode图

133. 克隆图

class Solution {
    Map<Node, Node> map = new HashMap<>();

    public Node dfs(Node node) {
        if (node == null) {
            return null;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }
        Node clone = new Node(node.val, new ArrayList<>());
        map.put(node, clone);
        for (Node n : node.neighbors) {
            clone.neighbors.add(dfs(n));
        }
        return clone;
    }

    public Node cloneGraph(Node node) {
        return dfs(node);
    }
}

207. 课程表

拓扑排序:
1.定义一个队列q，将所有入度为0的结点入队。
2.取队首结点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1。如果某个顶点入度减为0，则入队。
3.反复进行2操作，直到队列为空。如果队列为空时入过队的结点数目恰好为n，说明拓扑排序成功。否则，失败，说明有环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] G = new ArrayList[numCourses];//图的邻接矩阵
        for (int i = 0; i < numCourses; i++) {//初始化
            G[i] = new ArrayList<>();
        }
        int[] inDegree = new int[numCourses];//每个顶点的入度
        int num = 0;//记录加入拓扑排序的顶点数
        for (int[] arr : prerequisites) {
            int pre = arr[1], next = arr[0];
            inDegree[next]++;
            G[pre].add(next);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);//所有入度为0的顶点入队
            }
        }
        while (!queue.isEmpty()) {
            int front = queue.peek();//取队首顶点
            queue.poll();
            for (int i = 0; i < G[front].size(); i++) {
                int next = G[front].get(i);//front的后继顶点
                inDegree[next]--;//next顶点的入度减1
                if (inDegree[next] == 0) {//如果next入度减为0则入队
                    queue.offer(next);
                }
            }
            G[front].clear();//清空front的出边，可不写
            num++;//加入拓扑排序序列的顶点数加1
        }
        if (num == numCourses) {//加入拓扑排序的顶点数为n，说明排序成功
            return true;
        } else {
            return false;
        }
    }
}