Path between 2 nodes in a graph
14 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Hari
am 28 Sep. 2020
Kommentiert: Christine Tobler
am 5 Okt. 2020
How to check if a path exists between two nodes in a graph?
0 Kommentare
Akzeptierte Antwort
Michael Croucher
am 28 Sep. 2020
Bearbeitet: Michael Croucher
am 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 Kommentare
Christine Tobler
am 5 Okt. 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.
Weitere Antworten (1)
Christine Tobler
am 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 Kommentare
Siehe auch
Kategorien
Mehr zu Directed Graphs finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!