MATLAB Answers

Path between 2 nodes in a graph

조회 수: 31(최근 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
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
Bruno Luong
Bruno Luong 2020년 10월 4일
Read Michael's answer that suggests using concomp

댓글을 달려면 로그인하십시오.

Community Treasure Hunt

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

Start Hunting!

Translated by