无向图的处理算法（三）

JeOam 发布于2019-08-14 12:10 / 3049人阅读

摘要：那还有一个重要的问题就是，从到是否存在一条路径，如果有找出其中最短的那条。最短路径问题当然这路考虑的是每条边的都是权值为的情况。解决这个问题的算法就是广度优先搜索算法下面给出其实现代码，其中的使用了一个队列用来保存需要遍历的顶点。

上一篇讲了从一个顶点到另一个顶点是否存在路径，用的时深度优先搜索。那还有一个重要的问题就是，“从s到v是否存在一条路径，如果有找出其中最短的那条。”最短路径问题
当然这路考虑的是每条边的都是权值为1的情况。
解决这个问题的算法就是广度优先搜索算法
下面给出其实现代码，其中的使用了一个队列用来保存需要遍历的顶点。其实很上一篇中的代码结构差不多，只不过遍历的顶点是依次从队列中取出的

package Graph;

import java.util.Stack;

import Queue.Queue;

public class BreadthFirstPaths {
    private 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 queue = new Queue();
        marked[s] = true;
        queue.enqueue(s);
        while(!queue.isEmpty())
        {
            int v = queue.dequeue();//从队列中删除改顶点
            for(int w:G.adj(v))//对该顶点相邻的所有顶点进行遍历，标记为访问过，同时加入队列
            {
                edgeTo[w] = v;
                marked[w] = true;
                queue.enqueue(w);
            }
        }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable pathTo(int v)
    {
        Stack path = new Stack();
        while(edgeTo[v] != s)//同上一篇，通过该数组往上回溯
        {
            path.push(v);
            v = edgeTo[v];
        }
        path.push(s);
        return path;
    }
}

云服务器 GPU云服务器 webrtc agc算法三负载均衡支持三种调度算法字符串处理算法匹配算法 webrtc音频处理算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64339.html

无向图的实现和一些常用算法（一）

摘要：无向图的数据结构边数边的数目邻接表，存储与该节点相邻的节点，一个链表数组无向图的创建一个含有个节点但不含边的无向图从输入流中读取一幅图返回图中有多少个节点边数添加一条边节点相邻的所有顶点对象的字符串表示实现很简单邻接表既然实现了图这种数据结无向图的数据结构 Class Graph private final int V; 边数 private int E; 边的数目 privat...

Lsnsh 2019-08-14 12:08 评论0 收藏0
无向图的处理算法（四）连通分量

这篇讲的是连通分量，连通分量是深度优先搜索算法的一个应用。每进行了一次dfs，就会找到一条连通分量。定义如下的API public class CC CC(Graph g) 预处理构造函数 boolean connected(int v,in w) v和w连通吗 int count() 改图中的连通分量个数 int id(int v) ...

asce1885 2019-08-14 12:10 评论0 收藏0
无向图的处理算法（二）

摘要：在图中，我们很自然地会问这几个问题从一个顶点能否到达顶点以为顶点能到达的所有顶点解决能否到达问题的算法就是深度优先算法，使用深度优先算法获得的从到的路径的时间与路径的长度成正比。在图中，我们很自然地会问这几个问题从一个顶点s能否到达顶点v? 以s为顶点能到达的所有顶点? 解决能否到达问题的算法就是深度优先算法，使用深度优先算法获得的从s到v的路径的时间与路径的长度成正比。 ...

bluesky 2019-08-14 12:11 评论0 收藏0
算法（第4版） Chapter 4.1 无向图

摘要：边仅由两个顶点连接，并且没有方向的图称为无向图。用分隔符当前为空格，也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点，计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

kamushin233 2019-08-14 17:14 评论0 收藏0
算法之不定期更新（三）（2018-04-24）

摘要：实现这个想法之后就发现，时间复杂度真的太高了。本期算法小分享就到这里咯刚做完探索里的初级，还有好多已经说烂了的题就不分享了。如果有什么意见或者想法欢迎在评论区和我交流题目 input: n // 代表无向图的顶点数 // 从1开始 m // 无向图的边数 arr1 // 各边的情况，形如[[1, 2], [3, 4],...]（代表顶点0和顶点2相连，顶点3和顶点4相连） ...

darryrzhong 2019-08-22 16:40 评论0 收藏0