Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit81323c4

Browse files
authored
Merge pull requestalgorithm-visualizer#227 from kopiro/pr-tarjan
Added Tarjan algorithm to find SCC
2 parentsfaa870f +f415cf5 commit81323c4

File tree

4 files changed

+124
-1
lines changed

4 files changed

+124
-1
lines changed

‎algorithm/category.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,8 @@
4141
"dijkstra":"Dijkstra",
4242
"floyd_warshall":"Floyd-Warshall",
4343
"page_rank":"PageRank Algorithm",
44-
"topological_sort":"Topological-Sort"
44+
"topological_sort":"Topological-Sort",
45+
"tarjan":"Tarjan"
4546
},
4647
"name":"Graph Search"
4748
},
Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
functionSCCVertex(u,disc,low,st,stackMember,carry)
2+
{
3+
graphTracer._visit(u)._wait();
4+
5+
disc[u]=++carry.time;
6+
discTracer._notify(u,carry.time)._wait();
7+
8+
low[u]=carry.time;
9+
lowTracer._notify(u,carry.time)._wait();
10+
11+
st.push(u);
12+
stTracer._setData(st)._wait();
13+
14+
stackMember[u]=true;
15+
stackMemberTracer._notify(u,true)._wait();
16+
17+
// Go through all vertices adjacent to this
18+
for(varv=0;v<G[u].length;v++){
19+
if(G[u][v]){
20+
21+
// If v is not visited yet, then recur for it
22+
if(disc[v]==-1){
23+
SCCVertex(v,disc,low,st,stackMember,carry);
24+
25+
// Check if the subtree rooted with 'v' has a
26+
// connection to one of the ancestors of 'u'
27+
low[u]=Math.min(low[u],low[v]);
28+
lowTracer._notify(u,low[u]);
29+
}
30+
31+
// Update low value of 'u' only of 'v' is still in stack
32+
// (i.e. it's a back edge, not cross edge).
33+
elseif(stackMember[v]==true){
34+
low[u]=Math.min(low[u],disc[v]);
35+
lowTracer._notify(u,low[u])._wait();
36+
}
37+
38+
}
39+
}
40+
41+
// head node found, pop the stack and print an SCC
42+
varw=0;// To store stack extracted vertices
43+
if(low[u]==disc[u]){
44+
45+
while(st[st.length-1]!=u){
46+
w=st.pop();
47+
stTracer._setData(st)._wait();
48+
49+
logger._print(w)._wait();
50+
51+
stackMember[w]=false;
52+
stackMemberTracer._notify(w,false)._wait();
53+
}
54+
55+
w=st.pop();
56+
stTracer._setData(st)._wait();
57+
58+
logger._print(w)._wait();
59+
logger._print('------');
60+
61+
stackMember[w]=false;
62+
stackMemberTracer._notify(w,false)._wait();
63+
}
64+
}
65+
66+
functionSCC()
67+
{
68+
vardisc=newArray(G.length);
69+
varlow=newArray(G.length);
70+
varstackMember=newArray(G.length);
71+
varst=[];
72+
varcarry={time:0};
73+
74+
for(vari=0;i<G.length;i++){
75+
disc[i]=-1;
76+
low[i]=-1;
77+
stackMember[i]=false;
78+
}
79+
80+
discTracer._setData(disc);
81+
lowTracer._setData(low);
82+
stackMemberTracer._setData(stackMember);
83+
stTracer._setData(st);
84+
85+
for(vari=0;i<G.length;i++){
86+
if(disc[i]==-1){
87+
SCCVertex(i,disc,low,st,stackMember,carry);
88+
}
89+
}
90+
}
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
varG=[
2+
[0,0,1,1,0,0],
3+
[1,0,0,0,0,0],
4+
[0,1,0,0,0,0],
5+
[0,0,0,1,0,0],
6+
[0,0,0,0,0,1],
7+
[0,0,0,0,1,0]
8+
];
9+
10+
vargraphTracer=newDirectedGraphTracer();
11+
graphTracer._setData(G);
12+
13+
vardiscTracer=newArray1DTracer('Disc');
14+
varlowTracer=newArray1DTracer('Low');
15+
varstackMemberTracer=newArray1DTracer('stackMember');
16+
varstTracer=newArray1DTracer('st');
17+
18+
varlogger=newLogTracer();
19+
20+
SCC();
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
{
2+
"Tarjan":"Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph",
3+
"Complexity": {
4+
"time":"worst $O(|V|+|E|)$"
5+
},
6+
"References": [
7+
"<a href='https://www.wikiwand.com/en/Tarjan%27s_strongly_connected_components_algorithm'>Wikipedia</a>"
8+
],
9+
"files": {
10+
"basic":"Find the strongly connected components of a graph"
11+
}
12+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp