One hop nearest neighbor in a graph

4 次查看（过去 30 天）
aasha verghese
aasha verghese 2022-6-27
回答： Steven Lord 2022-6-27
Hi,
nodeIDs = nearest( G , s , d ) returns all nodes in graph G that are within distance d from node s. But how do we find out one hop away neighbors (just closest nodes only) within a distance, in a graph? I mean the nearest neighbour of a vertex in a graph within a distance must be connected through an edge. (only one edge)
thanks!

请先登录，再回答此问题。

采纳的回答

Chunru
Chunru 2022-6-27
Ran in:
% Example graph
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);
% All edges from node 1
eid = outedges(G, 1)
eid = 5×1
1 2 3 4 5
% info for edges from the node
e = G.Edges(eid, :)
e = 5×2 table
EndNodes Weight ________ ______ 1 2 8 1 4 8 1 5 3 1 6 4 1 7 8
% min distance
[~, idx] = min(e.Weight)
idx = 3
e(idx, :)
ans = 1×2 table
EndNodes Weight ________ ______ 1 5 3
min_node = e(idx, 1).EndNodes(2)
min_node = 5
min_dist = e.Weight(idx, 1)
min_dist = 3

更多回答（1 个）

Steven Lord
Steven Lord 2022-6-27
Ran in:
Find the neighbors of the node in the undirected graph then compute the distances between the specified node and its neighbors. Let's take an example: the buckyball graph.
b = bucky;
Update the adjacency matrix with some random weights and make it symmetric.
b = b.*randi(10, size(b));
b = (b + b.')/2;
Make the graph.
g = graph(b);
Find the neighbors of node 42.
n = neighbors(g, 42)
n = 3×1
8 41 43
Find the distances from node 42 to the neighbor nodes.
d = distances(g, 42, n)
d = 1×3
6.0000 1.5000 7.0000
Check with the original sparse matrix.
b(n, 42)
ans =
(1,1) 6.0000 (2,1) 1.5000 (3,1) 7.0000
If you later want to use a directed graph you may need to use successors or predecessors instead of neighbors.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by