Path between 2 nodes in a graph

1 次查看（过去 30 天）
Hari
Hari 2020-9-28
评论： Christine Tobler 2020-10-5
How to check if a path exists between two nodes in a graph?

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

采纳的回答

Michael Croucher
Michael Croucher 2020-9-28
编辑：Michael Croucher 2020-9-28
One way to proceed would be to use concomp.
Take this example graph
s = [1 2 2 3 3 3 4 5 5 5 8 8];
t = [2 3 4 1 4 5 5 3 6 7 9 10];
G = graph(s,t);
plot(G,'Layout','layered')
>> components=conncomp(G)
ans =
1 1 1 1 1 1 1 2 2 2
We can see that there are two connected components. To see it nodes 4 and 7 are connected (for example), just see if they are members of the same component.
components(4)==components(7)
ans =
logical
1
  2 个评论
Hari
Hari 2020-10-4
This did work for me. Thanks
Christine Tobler
Christine Tobler 2020-10-5
Note this works well for an undirected graph, but for directed graphs it would be more complicated: In that case, you'd want to look into digraph/transclosure to get connection between every pair of nodes.

请先登录，再进行评论。

更多回答（1 个）

Christine Tobler
Christine Tobler 2020-9-28
Compute a path between the nodes, then check if the result is empty (this is returned by shortestpath if no path exists):
path = shortestpath(G, firstNode, secondNode)
pathExists = ~isempty(path);
  2 个评论
Hari
Hari 2020-10-4
Will this be computationally intensive if I need to check paths between every node pair (say there 100 nodes)?
Bruno Luong
Bruno Luong 2020-10-4
Read Michael's answer that suggests using concomp

请先登录，再进行评论。

类别

在 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