Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

nearest

半径范围内最近的邻点

说明

示例

nodeIDs = nearest(G,s,d) 返回图形 G 中与节点 s 的距离在 d 之内的所有节点。如果图进行了加权(即 G.Edges 包含变量 Weight),则这些权重用作沿图中各边的距离。否则,所有边距离都视为 1

示例

nodeIDs = nearest(G,s,d,Name,Value) 使用一个或多个名称-值对组参数指定的其他选项。例如,如果 G 是加权图,则 nearest(G,s,d,'Method','unweighted') 将忽略图 G 中的边权重,而将所有边权重视为 1

示例

[nodeIDs,dist] = nearest(___) 还返回与每个最近邻点之间的距离,因此 dist(j) 是从源节点 s 到节点 nodeIDs(j) 的距离。您可以使用上述语法中的任何输入参数组合。

示例

全部折叠

创建并绘制一个具有加权边的图。

s = [1 1 1 1 1 2 2 2 3 3 3 3 3];
t = [2 4 5 6 7 3 8 9 10 11 12 13 14];
weights = randi([1 10],1,13);
G = graph(s,t,weights);
p = plot(G,'Layout','force','EdgeLabel',G.Edges.Weight);

Figure contains an axes object. The axes object contains an object of type graphplot.

确定哪些节点在节点 1 周围半径为 15 的范围内。

nn = nearest(G,1,15)
nn = 9×1

     5
     7
     2
     3
     4
     6
     8
    12
     9

源节点以绿色突出显示,最近的邻点以红色突出显示。

highlight(p,1,'NodeColor','g')
highlight(p,nn,'NodeColor','r')

Figure contains an axes object. The axes object contains an object of type graphplot.

创建并绘制一个具有加权边的图。

s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8];
t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12];
weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1];
G = graph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Figure contains an axes object. The axes object contains an object of type graphplot.

确定哪些节点在节点 3 周围半径为 5 的范围内,并返回到每个节点的距离。

[nn,dist] = nearest(G,3,5)
nn = 9×1

     9
    10
     5
    11
     4
     7
    12
     6
     8

dist = 9×1

     1
     1
     2
     2
     3
     3
     3
     4
     4

创建并绘制一个具有加权边的有向图。

s = {'a' 'a' 'a' 'b' 'c' 'c' 'e' 'f' 'f'};
t = {'b' 'c' 'd' 'a' 'a' 'd' 'f' 'a' 'b'};
weights = [1 1 1 2 2 2 2 2 2];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Figure contains an axes object. The axes object contains an object of type graphplot.

确定节点 'a' 周围半径为 1 的范围内最近的节点,按照节点 'a' 的出向路径距离测量。

nn_out = nearest(G,'a',1)
nn_out = 3x1 cell
    {'b'}
    {'c'}
    {'d'}

通过将半径指定为 Inf,确定有入向路径通向节点 'a' 的所有节点。

nn_in = nearest(G,'a',Inf,'Direction','incoming')
nn_in = 4x1 cell
    {'b'}
    {'c'}
    {'f'}
    {'e'}

输入参数

全部折叠

输入图,指定为 graphdigraph 对象。可使用 graph 创建一个无向图,或使用 digraph 创建一个有向图。

示例: G = graph(1,2)

示例: G = digraph([1 2],[2 3])

源节点,以下表中的形式之一指定为节点索引或节点名称。

示例
标量节点索引1
字符向量节点名称'A'
字符串标量节点名称"A"

示例: nearest(G,3,1)

示例: nearest(G,'a',5)

邻点距离半径,指定为数值标量。

示例: nearest(G,3,1)

示例: nearest(G,'a',2.5)

名称-值参数

示例: [nodeIDs,dist] = nearest(G,s,5,'Method','unweighted','Direction','incoming')

指定可选的、以逗号分隔的 Name,Value 对组参数。Name 为参数名称,Value 为对应的值。Name 必须放在引号中。您可采用任意顺序指定多个名称-值对组参数,如 Name1,Value1,...,NameN,ValueN 所示。

注意

只能为有向图指定 'Direction' 选项。

距离测量的方向,指定为逗号分隔的对组,其中包含 'Direction' 和下表中的选项之一。

选项说明
'outgoing'(默认值)距离是使用源节点 s出向路径计算的。
'incoming'距离是使用源节点 s入向路径计算的。

示例: nearest(G,s,d,'Direction','incoming')

最短路径算法,指定为逗号分隔的对组,其中包含 'Method' 和下表中的选项之一。

选项说明
'auto'(默认值)

'auto' 选项会自动选择算法:

  • 'unweighted' 用于没有边权重的 graphdigraph 输入。

  • 'positive' 用于具有边权重的所有 graph 输入,并要求权重为非负数。此选项还用于具有非负边权重的 digraph 输入。

  • 'mixed' 用于其边权重包含某些负值的 digraph 输入。图不能包含负循环。

'unweighted'

广度优先计算,将所有边权重都视为 1

'positive'

Dijkstra 算法,要求所有边权重均为非负数。

'mixed'(仅适用于 digraph

适用于有向图的 Bellman-Ford 算法,要求图没有负循环。

尽管对于相同的问题,'mixed' 的速度慢于 'positive',但 'mixed' 更为通用,因为它允许某些边权重为负数。

注意

对于大多数图,'unweighted' 是速度最快的算法,然后是 'positive''mixed' 算法。

示例: nearest(G,s,d,'Method','positive')

输出参数

全部折叠

最近邻节点 ID,如果 s 是数值则以节点索引形式返回;如果 s 是节点名称则以节点名称形式返回。节点按照从最近到最远的方式排列。如果指定的距离内没有节点,则 nodeIDs 为空。即使图中包含自环,nodeIDs 也永远不会包含源节点 s

使用 H = subgraph(G,[s; nodeIDs]) 从原图形 G 中提取最近邻点的子图。

邻点距离,以向量形式返回。dist(j) 是从源节点 s 到相邻节点 nodeIDs(j) 的距离。

版本历史记录

在 R2016a 中推出