邻接表法

邻接矩阵法

public void bsf(Node node){
    Deque<Node> deque = new ArrayDeque<>();
    Set<Node> set = new HashSet<>();
    deque.offer(node);
    set.add(node);
    while(!deque.isEmpty()){
        Node temp = deque.poll();
        System.out.println("操作" + temp);
        for(Node n : temp.next){
            if(!set.contains(n)){
                deque.offer(n);
                set.add(n);
            }
        }
    }
}

public void dfs(Node node){
    Deque<Node> deque = new ArrayDeque<>();
    Set<Node> set = new HashSet<>();
    deque.push(node);
    set.add(node);
    while(!deque.isEmpty()){
        Node temp = deque.pop();
        System.out.println("操作" + temp);
        for(Node n : temp.next){
            if(!set.contains(n)){
                deque.push(temp);
                deque.push(n);
                set.add(n);
                break;
            }
        }
    }
}

• 存储节点之间的关系；
• 将节点存储到数组的对应下标的位置里，重复++；
• 将入度为0的节点加入队列，找到此节点对应的下一个节点，将下一个节点的入度--（也就是删除连接线）；
• 检查遍历的层数和给定的课程数是否一致，不一致则说明产生有向环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        // 数组下标对应每个节点
        int[] input = new int[numCourses];
        // 构造关系
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < numCourses; i++){
            list.add(new ArrayList<>());
        }

        for(int[] temp : prerequisites){
            list.get(temp[1]).add(temp[0]);
            // 存储入度的节点、以及对应的相连线的个数
            input[temp[0]]++;
        }

        // 保存入度为0
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < input.length; i++){
            if(input[i] == 0){
                deque.offer(i);
            }
        }

        int count = 0;
        while(!deque.isEmpty()){
            int node = deque.poll();
            count++;
            for(int j : list.get(node)){
                // 将每个与入度为0的节点的连接线删除
                input[j]--;
                if(input[j] == 0) {
                    deque.offer(j);
                }
            }
        }

        // 如何有向环的话就会小于
        return count == numCourses;
    }
}

剑指offer|| 113.课程顺序

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 构造关系
        List<List<Integer>> list = new ArrayList<>();
        // 每个课程对应一个list
        for(int i = 0; i < numCourses; i++){
            list.add(new ArrayList<>());
        }
        // 下标对应节点、存储个数？
        int[] input = new int[numCourses];
        for(int[] temp : prerequisites){
            list.get(temp[1]).add(temp[0]);
            input[temp[0]]++;
        }

        List<Integer> res = new ArrayList<>();
        // 将入度为0的放入列表
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < input.length; i++){
            if(input[i] == 0){
                deque.offer(i);
            }
        }

        while(!deque.isEmpty()){
            int node = deque.poll();
            res.add(node);
            for(int i : list.get(node)){
                input[i]--;
                if(input[i] == 0){
                    deque.offer(i);
                }
            }
        }

        int[] arr = new int[numCourses];
        int index = 0;
        for(int i : res){
            arr[index++] = i;
        }
        return res.size() == numCourses ? arr : new int[]{};
    }
}

• 深度优先遍历：寻找出度为0的节点，找到其对应的节点将其出度--
• 应用：可以减少spring启动循环依赖的事项

• 有向图：拓扑排序（根据入度）；
• 无向图：并查集（将每一个元素看成一个集合，如果当前边的两个元素没有在同一个集合中则将两个集合合并；如果在同一个集合中说明存在环则跳过。判断两个元素是否在同一个集合可以根据并查集的寻找祖先节点来判断，如果是一个祖先节点说明在同一个集合中；同时合并两个集合也可以通过并查集的合并两个集合实现）；

//    寻找父节点(路径压缩)
    public int find(int x){
        //隔代压缩
        while(x != fa(x)){
            fa(x) = fa(fa(x));
            x = fa(x);
        }
        return x;
        
        //完全压缩
        //return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }
 
//    根据根节点的深度进行合并
    public void merge(int i, int j){
        //普通合并
        int x = find(i), y = find(j);
        fa[x] = y;
        
        
        //按秩合并
        //if(rank[x] <= rank[y]){
            //fa[x] = y;
        //}else{
            //fa[y] = x;
        //}
        //if(rank[x] == rank[y] && x != y){
            //rank[y]++;
        //}
    }

• https://www.cnblogs.com/yoke/p/6697013.html
• https://blog.csdn.net/hzf0701/article/details/107933639

• 将边的权重由小到大排序（可以使用堆排）；使用set存储已经经历的节点，使用result存储结果；
• 遍历所有节点，如果节点不在set中，说明是新节点，将节点对应的边加入到优先队列中；
• 循环这个优先队列，弹出边，找到边的另一头节点，如果不在set中，说明是新节点，将新节点的边添加到优先队列中；
• 只有一个集合，所以可以使用set来避免出现环。

node为节点、edge为边，to、from是边对应的两个节点

Queue<Edege> queue = new PriorityQueue<>();

存储经历过的节点
Set<Node> set = new HashSet<>();

存储正确路径的边
Set<Node> result = new HashSet<>();

// 此循环处理森林问题，也就是不是全连通的；如果是全连通可以不加；
// for(Node node : graph.nodes.values()){
    if(!set.contains(node)){
        //新的节点
        set.add(node);
        for(Edge edge : node.edges){
            queue.offer(edge);
        }
        
        while(!queue.isEmpty()){
            //边的另一头的节点
            Edge edge = queue.poll();
            Node toNode = edge.to;
            
            //是新节点、添加这条边
            if(!set.contains(toNode)){
                set.add(toNode);
                result.add(edge);
                for(Edge nextEdge : toNode.edges){
                    queue.offer(nextEdge);
                }
            }
        }
    }
//}

Dijkstra算法（迪杰斯特拉）