UniqueVertices之间的区别是什么:路径和唯一顶点:全球?
根据ARANGO文件:
- path”-确保返回的路径中没有重复的顶点
1.“global”-保证每个顶点在遍历过程中最多只被访问一次,无论从起始顶点到这个顶点有多少条路径。如果你以最小深度〉1开始,那么在最小深度之前找到的顶点可能根本不会被返回(它仍然可能是路径的一部分)。注意:使用此配置,结果不再具有确定性。如果从startVertex到vertex有多条路径,则选择其中一条。需要设置bfs:true,因为使用深度优先搜索时,结果将不可预测。
UniqueVertices global的作用是什么?在遍历过程中,顶点最多被访问一次,这意味着什么?
1条答案
按热度按时间8yparm6h1#
考虑这个有5个顶点的图,它包含一个圈
B -> D -> E -> B
:没有唯一性限制的出站遍历将进入该循环,并在单个路径上多次访问某些顶点和边,直到达到最大遍历深度:
第一个
默认情况下,
uniqueVertices
为"none"
,uniqueEdges
为"path"
。这些选项可避免同一条路径两次遍历同一条边。这可防止遍历第二次进入循环(从B到D的边),但后两条路径仍两次包含B:第一次
通过将顶点和边的唯一性限制为
"path"
,每个路径将不会访问任何顶点或边两次。因为这是第一次在路径上遇到这条边(uniqueEdges
是"none"
还是"path"
对于这个特定的图来说并不重要),但是顶点B在开始时就已经被访问过了(A --> B --> D
),因此遍历在此停止并且第二次不包括B:第一个
需要一个不同的示例图来显示
uniqueVertices: "global"
的效果,该示例图具有菱形中的4个顶点:在F处开始的出站遍历经由G和H通向同一顶点I。没有顶点或边可能被访问两次,但是每个发现的路径可以包括I:
第一个
如果我们现在将顶点的唯一性改变为
"global"
,那么只有一条路径可以以I结束。选择哪条路径(经由G或H)是未定义的:请注意,
uniqueVertices: "global"
需要bfs: true
(广度优先搜索)。虽然它不能使遍历具有确定性,但它确实使遍历更具可预测性。使用深度优先搜索,它会沿着一条路径一直走到尽头(或直到达到最大深度)。然后,如果某些路径包含已经访问过的顶点,则在这些路径上的遍历将提前停止,但是发现路径的顺序是未定义的,并且这可能导致对于同一查询返回不同的顶点集合。另一方面,第一次搜索确保返回相同的顶点集,即使在运行之间跟随的边可能变化。