tarjan(e)

버전 1.2.0.0 (2.79 KB) 작성자: Brandon Kuczenski
Tarjan's strongly connected component algorithm
다운로드 수: 401
업데이트 날짜: 2016/4/12

라이선스 보기

Implements Tarjan's algorithm for finding strongly connected components of directed graphs. In a strongly connected component (SCC), there is a path from every node to every other node. SCCs are disjoint. Nodes whose in-degree or out-degree are zero or are part of acyclic graphs form SCCs all by themselves.
Accepts an adjacency matrix as input. For best performance, the matrix should be sparse.
Also returns an index list reporting SCC membership for each node.
Example of use:
>> E = sparse([2 3 4 5 5 6 6 7 8 4 9 5 10 6 9], ...
[1 2 2 3 4 3 5 6 4 8 8 9 9 10 6], ...
ones(1,15));
>> figure; spy(E)
>> c = tarjan(E)

c =

[1x4 double] [1x2 double] [7] [3] [2] [1]

>> c{1}

ans =

5 6 9 10

>>
>>

In the example, E is an adjacency matrix for a directed graph (visualized in the screenshot image), and the nodes with indices 5, 6, 9, and 10 form the largest strongly connected component in the graph.

Implements the wikipedia pseudocode [1] more or less exactly. Matlab doesn't have an easy way to share private variables across recursive function calls so this function uses globals. (I know!)

[1] https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#The_algorithm_in_pseudocode

인용 양식

Brandon Kuczenski (2024). tarjan(e) (https://www.mathworks.com/matlabcentral/fileexchange/50707-tarjan-e), MATLAB Central File Exchange. 검색됨 .

MATLAB 릴리스 호환 정보
개발 환경: R2013b
모든 릴리스와 호환
플랫폼 호환성
Windows macOS Linux
카테고리
Help CenterMATLAB Answers에서 Directed Graphs에 대해 자세히 알아보기
도움

줌: LoopDetect

Community Treasure Hunt

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

Start Hunting!
버전 게시됨 릴리스 정보
1.2.0.0

Add example usage.

1.1.0.0

fixed a bug in the initial version- variable 'index' must also be global.

1.0.0.0