Path between 2 nodes in a graph

12 views (last 30 days)
How to check if a path exists between two nodes in a graph?

Accepted Answer

Michael Croucher
Michael Croucher on 28 Sep 2020
Edited: Michael Croucher on 28 Sep 2020
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 Comments
Hari
Hari on 4 Oct 2020
This did work for me. Thanks
Christine Tobler
Christine Tobler on 5 Oct 2020
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.

Sign in to comment.

More Answers (1)

Christine Tobler
Christine Tobler on 28 Sep 2020
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 Comments
Hari
Hari on 4 Oct 2020
Will this be computationally intensive if I need to check paths between every node pair (say there 100 nodes)?
Bruno Luong
Bruno Luong on 4 Oct 2020
Read Michael's answer that suggests using concomp

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!