nearest

半径范围内最近的邻点

全页折叠

语法

nodeIDs = nearest(G,s,d)
nodeIDs = nearest(G,s,d,Name,Value)
[nodeIDs,dist] = 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 = 3×1 cell
    {'b'}
    {'c'}
    {'d'}

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

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

输入参数

全部折叠

输入图，指定为 graph 或 digraph 对象。可使用 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)

名称-值参数

全部折叠

以 Name1=Value1,...,NameN=ValueN 的形式指定可选参量对组，其中 Name 是参量名称，Value 是对应的值。名称-值参量必须出现在其他参量之后，但对各个参量对组的顺序没有要求。

在 R2021a 之前，使用逗号分隔每个名称和值，并用引号将 Name 引起来。

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

注意

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

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

选项描述
'outgoing'（默认值）距离是使用源节点 s 的出向路径计算的。
'incoming'距离是使用源节点 s 的入向路径计算的。

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

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

选项描述
'auto'（默认值）

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

  • 'unweighted' 用于没有边权重的 graph 和 digraph 输入。

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

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

'unweighted'

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

'positive'

迪杰斯特拉算法，要求所有边权重均为非负数。

'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) 的距离。

扩展功能

全部展开

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2016a 中推出

另请参阅

| | | | |

主题