236:
also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and moves these vertices into a new component when it finishes expanding the final vertex of its component. However, in place of the stack
224:
The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.
233:
39:, one to keep track of the vertices in the current component and the second to keep track of the current search path. Versions of this algorithm have been proposed by
87:
contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices. Stack
91:
contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter
381:
346:
24:
462:
457:
36:
95:
of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices.
166:
has not yet been assigned to a strongly connected component (the edge is a forward/back/cross edge):
426:
317:
246:
152:
32:
277:
242:
418:
393:
361:
309:
373:
369:
342:
329:
28:
365:
451:
397:
295:
430:
321:
300:
20:
298:(1996), "Algorithms for dense graphs and networks on the random access computer",
245:
of preorder numbers, assigned in the order that vertices are first visited in the
384:(1971), "Efficient determination of the transitive closure of a directed graph",
60:
406:
249:. The preorder array is used to keep track of when to form a new component.
422:
313:
83:(in addition to the normal call stack for a recursive function). Stack
347:"Path-based depth-first search for strong and biconnected components"
207:
has been popped, and assign the popped vertices to a new component.
177:
has a preorder number less than or equal to the preorder number of
71:
The algorithm performs a depth-first search of the given graph
442:(3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216
438:
Sedgewick, R. (2004), "19.8 Strong
Components in Digraphs",
59:; of these, Dijkstra's version was the first to achieve
234:Tarjan's strongly connected components algorithm
52:
278:History of Path-based DFS for Strong Components
102:, the algorithm performs the following steps:
440:Algorithms in Java, Part 5 – Graph Algorithms
98:When the depth-first search reaches a vertex
8:
241:, Tarjan's algorithm uses a vertex-indexed
31:may be found using an algorithm that uses
265:
151:has not yet been assigned (the edge is a
48:
280:, Harold N. Gabow, accessed 2012-04-24.
258:
40:
56:
44:
7:
75:, maintaining as it does two stacks
14:
407:"A transitive closure algorithm"
336:, NJ: Prentice Hall, Ch. 25
386:Information Processing Letters
354:Information Processing Letters
53:Cheriyan & Mehlhorn (1996)
1:
366:10.1016/S0020-0190(00)00051-X
169:Repeatedly pop vertices from
25:strongly connected components
398:10.1016/0020-0190(71)90006-8
334:A Discipline of Programming
106:Set the preorder number of
479:
147:If the preorder number of
173:until the top element of
140:to a neighboring vertex
35:in combination with two
405:Purdom, P. Jr. (1970),
192:is the top element of
155:), recursively search
232:Like this algorithm,
136:For each edge from
463:Graph connectivity
423:10.1007/bf01940892
314:10.1007/BF01940880
247:depth-first search
228:Related algorithms
199:Pop vertices from
33:depth-first search
470:
458:Graph algorithms
443:
433:
400:
376:
360:(3–4): 107–114,
351:
343:Gabow, Harold N.
337:
330:Dijkstra, Edsger
324:
281:
275:
269:
266:Sedgewick (2004)
263:
114:, and increment
478:
477:
473:
472:
471:
469:
468:
467:
448:
447:
437:
404:
380:
349:
341:
328:
293:
290:
285:
284:
276:
272:
264:
260:
255:
230:
69:
49:Dijkstra (1976)
17:
16:Graph algorithm
12:
11:
5:
476:
474:
466:
465:
460:
450:
449:
446:
445:
435:
402:
378:
339:
326:
308:(6): 521–549,
294:Cheriyan, J.;
289:
286:
283:
282:
270:
257:
256:
254:
251:
229:
226:
222:
221:
220:
219:
208:
186:
185:
184:
183:
182:
162:Otherwise, if
160:
134:
129:and also onto
119:
68:
65:
29:directed graph
15:
13:
10:
9:
6:
4:
3:
2:
475:
464:
461:
459:
456:
455:
453:
441:
436:
432:
428:
424:
420:
416:
412:
408:
403:
399:
395:
391:
387:
383:
379:
375:
371:
367:
363:
359:
355:
348:
344:
340:
335:
331:
327:
323:
319:
315:
311:
307:
303:
302:
297:
292:
291:
287:
279:
274:
271:
267:
262:
259:
252:
250:
248:
244:
240:
235:
227:
225:
217:
213:
209:
206:
202:
198:
197:
195:
191:
187:
180:
176:
172:
168:
167:
165:
161:
158:
154:
150:
146:
145:
143:
139:
135:
132:
128:
124:
120:
117:
113:
109:
105:
104:
103:
101:
96:
94:
90:
86:
82:
78:
74:
66:
64:
62:
58:
54:
50:
46:
42:
41:Purdom (1970)
38:
34:
30:
26:
22:
439:
414:
410:
392:(2): 56–58,
389:
385:
357:
353:
333:
305:
301:Algorithmica
299:
296:Mehlhorn, K.
273:
261:
238:
231:
223:
215:
211:
204:
200:
193:
189:
178:
174:
170:
163:
156:
148:
141:
137:
130:
126:
122:
115:
111:
107:
99:
97:
92:
88:
84:
80:
76:
72:
70:
57:Gabow (2000)
45:Munro (1971)
21:graph theory
18:
67:Description
61:linear time
452:Categories
382:Munro, Ian
288:References
417:: 76–94,
153:tree edge
431:20818200
345:(2000),
332:(1976),
374:1761551
322:8930091
429:
372:
320:
203:until
55:, and
37:stacks
23:, the
427:S2CID
350:(PDF)
318:S2CID
253:Notes
243:array
214:from
125:onto
121:Push
27:of a
210:Pop
79:and
419:doi
411:BIT
394:doi
362:doi
310:doi
188:If
110:to
19:In
454::
425:,
415:10
413:,
409:,
388:,
370:MR
368:,
358:74
356:,
352:,
316:,
306:15
304:,
196::
144::
63:.
51:,
47:,
43:,
444:.
434:.
421::
401:.
396::
390:1
377:.
364::
338:.
325:.
312::
268:.
239:P
218:.
216:P
212:v
205:v
201:S
194:P
190:v
181:.
179:w
175:P
171:P
164:w
159:;
157:w
149:w
142:w
138:v
133:.
131:P
127:S
123:v
118:.
116:C
112:C
108:v
100:v
93:C
89:P
85:S
81:P
77:S
73:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.