Path between 2 nodes in a graph
10 views (last 30 days)
Show older comments
Hari
on 28 Sep 2020
Commented: Christine Tobler
on 5 Oct 2020
How to check if a path exists between two nodes in a graph?
0 Comments
Accepted Answer
Michael Croucher
on 28 Sep 2020
Edited: Michael Croucher
on 28 Sep 2020
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
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.
More Answers (1)
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
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!