One hop nearest neighbor in a graph

10 次查看（过去 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 中查找有关 Directed Graphs 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by