logo logo
您的位置 :首页 > 新闻中心
可访问性的基本介绍
发布时间 : 2021-04-01 14:15:17 浏览: 97次 来源:【jake推荐】 作者:-=Jake=-

0个有用+1票

可访问性讨论

该条目已通过“中国科学”《科学百科全书》条目编译和应用工作项目进行了审查。

在图论中,可达性指的是从图中一个顶点到另一个顶点的难易程度。在无向图中,所有顶点对之间的可达性可以通过识别图的连接分量来确定。常用的算法有:Floyd-Warshall凤凰彩票官网 ,Thorup亚博全站 ,Kameda这三种算法。

中文名

可访问性

外来名称

可达性

说明

从一个地方到另一个地方有多容易

算法

弗洛伊德·沃舍尔,索鲁普,卡梅达

内容

123

可访问性的基本介绍

在图论中,可达性是指从一个顶点到另一个顶点的难易程度。如果存在一系列相邻的顶点万狗体育 ,则顶点s可以到达顶点t(并且t也可以到达s),从s开始到t结束。

在无向图中,所有对顶点之间的可达性可以通过识别图的连接分量来确定。这种图的任意一对顶点都可以且仅当它们属于同一连接的组件时才可以相互到达。可以在线性时间内识别无向图的连通分量。

可访问性算法

用于确定可达性的算法分为两类:需要预处理的算法和不需要预处理的算法。

如果仅要查询一个(或几个)数据,则放弃使用更复杂的数据结构并直接计算可达性可能更有效。这可以使用诸如广度优先搜索或迭代加深深度优先搜索的算法在线性时间内完成。 [1]

如果您要查询大量数据凤凰彩票代理 ,则可以使用更复杂的方法;方法的选择取决于所分析图的性质。为了交换预处理时间和一些额外的存储空间,我们可以创建一个数据结构,然后它可以对任意一对顶点执行可达性查询。

以下概述了三种不同的算法和数据结构。

Floyd-Warshall算法

Floyd-Warshall算法(Floyd-Warshall算法)是一种用于求解任意两点之间最短路径的算法。它可以正确处理有向图或负权重的最短路径问题,还可以用于计算有向图。传递闭包。 Floyd-Warshall算法的时间复杂度为O(N),空间复杂度为O(N * N)。

Thorup算法

对于平面有向图,一种更快的方法是Mikkel Thorup在2004年提出的算法。计算复杂度为

可达矩阵的物理意义,其中

是逆阿克曼函数沐鸣娱乐2 ,具有非常慢的增长率。该算法还可以提供近似的最短路径距离和路由信息。

Kameda算法

如果图形是平坦的,无环的,并且还具有以下附加属性可达矩阵的物理意义,则可以使用T. Kameda在1975年提出的更快的预处理方法:出现所有0度顶点和所有0度顶点(通常假定为面的边界可以分为两部分,因此所有0个不等点的顶点都出现在一个部分上,而0度以外的所有顶点都出现在另一部分上(也就是说,两种类型的顶点不会交替出现)。

与可访问性相关的问题

一个相关的问题是解决具有数量为k的顶点失败的可达性查询。可以将相似的问题视为边缘故障,而不是顶点故障,或者将两者混合使用。广度优先搜索技术对此类查询同样有效。 [2]

与可及性查询有关的另一个问题是,当图形的某些部分发生变化时,可及性关系的变化会迅速重新计算。

输入地图集和更多地图集

参考资料

返回新闻资讯