首页 / 算法 / 第四章 图(二) - 《算法》读书笔记

第四章 图(二) - 《算法》读书笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了第四章 图(二) - 《算法》读书笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2516字，纯文字阅读大概需要4分钟。

内容图文

目录

第四章 图(二)

4.1.3 深度优先搜索

4.1.3.2 热身

  • 深度优先搜索(DFS)只需用一个递归方法来遍历所有顶点，在访问其中一个顶点时：
    • 将它标记为已访问
    • 递归地访问它的所有没有被标记过的邻居顶点
  • 具体实现如下：
public class DepthFirstSearch{
    private boolean[] marked;
    private int count;
    
    public DepthFirstSearch(Graph G, int s){
        marked = new boolean[G.V()];
        dfs(G, s);
    }
    public void dfs(Graph G, int v){
        marked[v] = true;
        count++;
        for(int w: G.adj(v))
            if(!marked[w])
                dfs(G, w);
    }
}

深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。

4.1.4 寻找路径

  • 路径的API：
public class Paths
Paths(Graph G, int s) 从G中找出所有起点为s的路径
boolean hasPathTo(int v) 是否存在从s到v的路径
Iterable<Integer> pathTo(int v) s到v的路径，如果不存在则返回null

4.1.4.1 实现

public class DepthFirstPaths{
    private boolean[] marked;
    private int[] edgeTo; //从起点到一个顶点的已知路径上的最后一个顶点
    private final int s;
    
    public DepthFirstPaths(Graph G, int s){
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }
    private void dfs(Graph G, int v){
        marked[v] = true;
        count++;
        for(int w: G.adj(v))
            if(!marked[w]){
                edgeTo[w] = v;
                dfs(G, w);
            }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v){
        if(!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        for(int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
}
  • 算法中，在由边v-w第一次访问任意w时，将edgeTo[w]设为v来记住这条路径，即v-w是从s到w的路径上的最后一条已知的边
  • 这样，搜索的结果是一棵以起点为根结点的树，edgeTo[]是一棵由父链接表示的树

使用深度优先搜索得到从给定起点到任意标记顶点的路径所需的时间与路径的长度成正比。

4.1.5 广度优先搜索

  • 广度优先搜索(BFS)使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将起点加入队列，然后重复以下步骤直到队列为空：

    • 取队列中的下一个顶点v并标记它
    • 将与v相邻的所有未标记过的顶点加入队列

  • 使用广度优先搜索查找图中的路径：

public class BreadthFirstPaths{
    pprivate boolean[] marked;
    private int[] edgeTo;
    private final int s;
    
    public BreadthFirstPaths(Graph G, int s){
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s); 
    }
    private void bfs(Graph G, int s){
        Queue<Integer> queue = new Queue<Integer>();
        marked[s] = true;
        queue.enqueue(s);
        while(!queue.isEmpty()){
            int v = queue.dequeue();
            for(int w : G.adj(v))
                if(!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.enqueue(w);
                }
        }
    }
}

对于从s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径。

广度优先搜索所需的时间在最坏情况下和V+E成正比。

内容总结

以上是互联网集市为您收集整理的第四章 图(二) - 《算法》读书笔记全部内容，希望文章能够帮你解决第四章 图(二) - 《算法》读书笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/606245.html

来源：【匿名】