BFS

性价比之王，14, 47

构图具有一定的灵活性，需要多加联系（一开始可能并不是一个图）

bfs

• 拓扑排序
• 分层遍历
• 连通块

连通块相关的所有

1. bfs
2. UFS

能用bfs解决的问题就用bfs解决，不用考虑dfs因为，dfs潜在stackoverflow（iteration的dfs不好写，而且面试官看不懂）

java的队列用ArrayDeque，比较快，不需要距离的时候Distance可以用hashset vistied代替

在进入队列的时候就要立刻标记

一旦入队就要马上标记，否则会有元素重复入队

public void bfs(Node node) {
    Queue<Node> queue = new ArrayDeque<>();
    Set<Node> set = new HashSet<>();
    
    queue.offer(node);
    set.add(node);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        
        for (Node neighbor: node.getNeighbors()) {
            if (distance.containKeys(neighbor)) {
                continue;
            }
            
            queue.offer(neighbor);
            set.add(neighbor);
        }
    }
}

克隆图

劝分不劝和

1. bfs找所有的点
2. 复制所有的点
3. 复制所有的边

BFS分层 vs 不分层

（不分层的如上面的，分层的加一层for循环先取出来这一层多长）

// java的队列用ArrayDeque，比较快，不需要距离的时候Distance可以用hashset vistied代替
public void bfs(Node node) {
    Queue<Node> queue = new ArrayDeque<>();
    HashMap<Node, Integer> distance = new HashMap<>();
    
    queue.offer(node);
    distance.set(node, 0);
    
    while (!queue.isEmpty()) {
        // 队列内为当前层的所有节点，此时记录下队列大小对整层进行遍历
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            for (Node neighbor: node.getNeighbors()) {
                if (distance.containKeys(neighbor)) {
                    continue;
                }
                
                queue.offer(neighbor);
                distance.set(neighbor, distance.get(node) + 1);
            }
        }
        // 此处加对整层的操作
    }
}

图上的BFS：

定义偏移量，X_OFFSET，Y_OFFEST

拓扑排序

四种问法

1. 求任意一个拓扑排序

2. 问是否存在拓扑排序

   如果存在循环依赖（环），就没有拓扑排序（即最后的order的大小不等于节点数）

3. 求是否存在且仅存在一个拓扑排序

   （queue的size始终为1）

   在外层while里的第一句加上一句判queue的len是否>1

4. 求字典序最小的拓扑排序

   这个的时候queue用priorityQueue来存，同时改为在取出队列时放入order

（第一节课，所有数据结构的用法和复杂度）

入度( In-degree）:

有向图（Directed Graph）中指向当前节点的点的个数（或指向当前节点的边的条数 )

算法描述：

1. 统计每个点的入度
2. 将每个入度为0的点放入队列（Queue ) 中作为起始节点
3. 不断从队列中享出一个点，去掉这个点的所有连边(指向其他点的边），其他点的相应的度 - 1
4. 一旦发现新的入度为0的点，丢回队列中

拓扑排序并不是传统的排序算法

一个图可能存在多个拓扑序( Topological Order ) , 也可能不存在任何拓扑序

// 实际场景中图不可能用邻接矩阵，都在用邻接表
ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    ArrayList<DirectedGraphNode> order = new ArrayList<>();
    // topo 用indegree来判断是否可以入队，其实相当于普通的里面的set
    Map<DirectedGraphNode, Integer> indegree = new HashMap<>();
    for (DirectedGraphNode node: graph) {
        for (DirectedGraphNode neighbor: graph.neighbors) {
            indegree.put(neighbor, indgree.getOrDefault(neighbor, 0) + 1);
        }
    }
    
    Queue<DirectedGraphNode> queue = new ArrayDeque<>();
    for (DirectedGraphNode node: graph) {
        // 如果入度不存在（即入度为0），则没有前驱
        if (!indegree.containsKey(node)) {
            queue,offer(node);
            order.add(node);
        }
    }
    
    while (!queue.isEmpty()) {
        DirectedGraphNode node = queue.poll();
        for (DirectedGraphNode neighbor: graph.neighbors) {
            indegree.put(neighbor, indgree.get(neighbor) - 1);
            if (indegree.get(neighbor) == 0) {
                queue,offer(neighbor);
                order.add(neighbor);
            }
        }
    }
    
    return order;
}

字典序最小的topo

能用 BFS 的一定不要用 DFS (除非面试官特别要求）

BFS的三个使用场景

• 连通块问题
• 层级遍历问题
• 拓扑排序问题

是否需要层级遍历

• 需要多一重循环
• 或者使用 distance 哈希表记录到所有点的距离

矩阵坐标变换数组

• deltax, deltaY
• inBound / isValid 判断坐标是否越界

课程表