美文网首页
算法与数据结构练习中常犯错误5——图论

算法与数据结构练习中常犯错误5——图论

作者: 王侦 | 来源:发表于2019-11-29 10:57 被阅读0次

    4.图论

    4.1 无向图

    4.1.1 DFS连通性与路径

    • 51)少了index等检查
        public Iterable<Integer> pathTo(int v) {
            // 少了检查和hasPathTo检查
            checkIndex(v);
            if (!hasPathTo(v)) {
                return null;
            }
            ArrayDeque<Integer>  stack = new ArrayDeque<>();
            // 这里计算路径时出了错误,越简洁越不容易处错误
            for (int w = v; w != s; w = edgeTo[w]) {
                stack.push(w);
            }
    

    4.1.2 DFS连通分量

    4.1.3 DFS检测环

    4.1.4 DFS检查二分图

    4.1.5 BFS最短路径

    • 52)忘记更新mark,循环不变量没搞清楚
           while (!queue.isEmpty()) {
                int v = queue.poll();
                for (int w : G.adj(v)) {
                    if (!marked[w]) {
                        // 严重的错误:这里忘记标记marked[w]!
                        marked[w] = true;
    

    4.2 最小生成树

    4.2.1 无向加权图

    • 53)不要忘了更新E
            // 不要忘了更新E
            E++;
    
    • 54)不要忘了对入参进行检查
        public Iterable<Edge> adj(int v) {
            // 不要忘了对入参进行检查
            checkIndex(v);
            return adj.get(v);
        }
    

    4.2.2 延时Prim算法

    4.2.3 即时Prim算法

    4.2.4 Kruskal算法

    4.3 有向图

    4.3.1 DFS单点连通性与路径

    4.3.2 拓扑排序

    • 55)递归代码最后的处理
        private void dfs(int v) {
            marked[v] = true;
            onStack[v] = true;
            for (int w : G.adj(v)) {
                if (hasCycle()) {
                    return;
                }
                if (!marked[w]) {
                    edgeTo[w] = v;
                    dfs(w);
                } else if (onStack[w]) {
                    cycle = new ArrayDeque<>();
                    cycle.push(w);
                    for (int u = v; u != w; u = edgeTo[u]) {
                        cycle.push(u);
                    }
                    cycle.push(w);
                }
            }
            // 特别注意,不要忘了这个,递归代码必须遵守的规则
            onStack[v] = false;
        }
    

    4.3.3 强联通分量

    4.3.4 BFS最短路径

    4.4 最短路径

    4.4.1 非负权重边Dijkstra算法

    4.4.2 无环

    4.4.3 普通情况(无负权重环)——Bellman-Ford

    • 54)正无穷
    // 之前未注意存在正无穷!
     Arrays.fill(distTo, Double.POSITIVE_INFINITY);
    

    4.5 最大流

    相关文章

      网友评论

          本文标题:算法与数据结构练习中常犯错误5——图论

          本文链接:https://www.haomeiwen.com/subject/xiuwwctx.html