无向图的处理算法（二）

bluesky 发布于2019-08-14 12:11 / 405人阅读

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

在图中，我们很自然地会问这几个问题

从一个顶点s能否到达顶点v?

以s为顶点能到达的所有顶点?

解决能否到达问题的算法就是深度优先算法，使用深度优先算法获得的从s到v的路径的时间与路径的长度成正比。

package Graph;

import java.util.Stack;

//基于深度优先算法，搜索查找图中的路径
//解决单点路径问题，即，从一点开始是否存在到另一个点的路径
public class DepthFirstPaths {
    private boolean[] marked;//这个顶点调用过dfs了吗
    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;
        for(int w: G.adj(V)){
            if(!marked[w]){
                edgeTo[w] = V;//表示这条路径上，w之前是v
                dfs(G,w);
            }
        }
    }

    public boolean hasPathTo(int V){
        return marked[V];
    }

    public Iterable pathTo(int V){
        if(!hasPathTo(V)) return null;
        Stack path = new Stack();
        for(int x = V;x != s; x = edgeTo[x])//从终点开始往上回溯
            path.push(x);
        path.push(s);
        return path;

    }
}

这样通过调用pathTo(v)就可以知道到任意顶点v的路径。

云服务器 GPU云服务器最小二乘法改进算法最小二乘法滤波算法最小二乘方算法解释最小二乘算法

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

转载请注明本文地址：https://www.ucloud.cn/yun/64340.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是否存在一条路径，如果有找出其中最短的那条。最短路径问题...

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

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

kamushin233 2019-08-14 17:14 评论0 收藏0
算法第四版4.1-无向图详解

摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：...

scola666 2019-08-14 17:53 评论0 收藏0