Share
VIDEOS 1 TO 50
Strongly Connected Components Tutorial
Strongly Connected Components Tutorial
Published: 2015/04/01
Channel: Michael Mroczka
Tarjan
Tarjan's Toposort Algorithm - Graph Theory 14
Published: 2016/03/07
Channel: 0612 TV w/ NERDfirst
Strongly Connected Components Kosaraju
Strongly Connected Components Kosaraju's Algorithm Graph Algorithm
Published: 2015/08/13
Channel: Tushar Roy - Coding Made Simple
Tarjan
Tarjan's Algorithm Finding Bridges in less than 6 MINUTES!
Published: 2016/03/04
Channel: Aleksandar Abas
Topological Sort & Strongly Connected Components
Topological Sort & Strongly Connected Components
Published: 2014/08/25
Channel: Mifta Sintaha
Strongly Connected Components Tutorial
Strongly Connected Components Tutorial
Published: 2017/02/20
Channel: Raymond Chan
Princeton Algorithms Course 3   5   Strong Components 20 22
Princeton Algorithms Course 3 5 Strong Components 20 22
Published: 2014/07/26
Channel: Benedict Chen
Articulation Points Graph Algorithm
Articulation Points Graph Algorithm
Published: 2015/09/10
Channel: Tushar Roy - Coding Made Simple
Strongly Connected Components -  A Walkthrough
Strongly Connected Components - A Walkthrough
Published: 2017/02/12
Channel: Chad Mills
Connected Components
Connected Components
Published: 2015/02/23
Channel: Udacity
Algorithms Live! Episode 23 - Strongly Connected Components
Algorithms Live! Episode 23 - Strongly Connected Components
Published: 2017/06/24
Channel: Algorithms Live!
001 Strongly connected components introduction
001 Strongly connected components introduction
Published: 2015/11/11
Channel: Townman Alex
Graph Theory - Strongly Connected Components - Tarjan - 1 (Arabic)
Graph Theory - Strongly Connected Components - Tarjan - 1 (Arabic)
Published: 2016/05/22
Channel: Arabic Competitive Programming
Kosaraju
Kosaraju's Algorithm - Strongly Connected Components | GeeksforGeeks
Published: 2017/05/09
Channel: GeeksforGeeks
Strongly Connected Components
Strongly Connected Components
Published: 2016/05/05
Channel: EducateYourself
Strongly Connected components in Bangla|| SCC || Algorithms
Strongly Connected components in Bangla|| SCC || Algorithms
Published: 2017/09/04
Channel: Learn CSE
Strongly Connected Components
Strongly Connected Components
Published: 2016/10/18
Channel: David Sturgill
6. Connected Components
6. Connected Components
Published: 2014/08/13
Channel: Algorithms and Data Structures
Algorithms 22.5 - strongly connected components
Algorithms 22.5 - strongly connected components
Published: 2017/04/07
Channel: John Edwards
Algorithms: 1.5 Topological Sorting and Strongly Connected Components
Algorithms: 1.5 Topological Sorting and Strongly Connected Components
Published: 2016/04/20
Channel: Stanford Scholar
Strongly Connected Components - Harder Example
Strongly Connected Components - Harder Example
Published: 2015/04/01
Channel: Michael Mroczka
PageRank, Strongly Connected Components
PageRank, Strongly Connected Components
Published: 2014/04/07
Channel: Gyu-Ho Lee
Graph Theory - Strongly Connected Components - Tarjan - 2 (Arabic)
Graph Theory - Strongly Connected Components - Tarjan - 2 (Arabic)
Published: 2016/05/28
Channel: Arabic Competitive Programming
[Mean Stack Development] Topological Sort & Strongly Connected Components
[Mean Stack Development] Topological Sort & Strongly Connected Components
Published: 2017/05/05
Channel: Toan Nguyen Song
Jason Katsaros - Strongly Connected Components Algorithms Project
Jason Katsaros - Strongly Connected Components Algorithms Project
Published: 2014/04/27
Channel: Jason Katsaros
Connected Components - Intro to Algorithms
Connected Components - Intro to Algorithms
Published: 2015/02/23
Channel: Udacity
Robert Tarjan: Search Tree Mysteries
Robert Tarjan: Search Tree Mysteries
Published: 2012/08/24
Channel: princetonacademics
Strongly connected components (SCC) In Bangla
Strongly connected components (SCC) In Bangla
Published: 2016/08/10
Channel: Easy Lessons
finding strongly connected components in bangla tutorial
finding strongly connected components in bangla tutorial
Published: 2016/11/29
Channel: Rr Ss
Tarjan Alogrithm parte 1
Tarjan Alogrithm parte 1
Published: 2015/01/20
Channel: jorgerodriguezc
8   8   Path Compression  Tarjan
8 8 Path Compression Tarjan 's Analysis I Advanced Optional 14 min
Published: 2015/08/16
Channel: Pavan Ravi
SAP HANA Academy - Graph: Strongly Connected Components [SPS 12]
SAP HANA Academy - Graph: Strongly Connected Components [SPS 12]
Published: 2016/06/10
Channel: SAP HANA Academy
Detect Cycle in Directed Graph Algorithm
Detect Cycle in Directed Graph Algorithm
Published: 2016/01/16
Channel: Tushar Roy - Coding Made Simple
Strongly Connected Components (SCC)
Strongly Connected Components (SCC)
Published: 2016/02/21
Channel: Aldo Omar Rodriguez
Tarjans connect
Tarjans connect
Published: 2015/06/03
Channel: Cami Tokowitz
Articulation Points Tutorial
Articulation Points Tutorial
Published: 2015/04/02
Channel: Michael Mroczka
Interview with Robert Tarjan at DIKU
Interview with Robert Tarjan at DIKU
Published: 2015/04/22
Channel: DIKU - Datalogisk Institut, Københavns Universitet
What Is A Strongly Connected Graph?
What Is A Strongly Connected Graph?
Published: 2017/08/17
Channel: Oakley Oakley
006 Testing the Tarjan algorithm
006 Testing the Tarjan algorithm
Published: 2015/11/11
Channel: Townman Alex
048 10   7   Computing Strong Components The Algorithm 29 min
048 10 7 Computing Strong Components The Algorithm 29 min
Published: 2016/08/20
Channel: Madhusudan Samantray
Finding Strongly Connected Components  - A Hand Executed Example
Finding Strongly Connected Components - A Hand Executed Example
Published: 2017/01/16
Channel: Chad Mills
Algorithms – Path Compression Tarjan
Algorithms – Path Compression Tarjan's Analysis I
Published: 2017/10/13
Channel: intrigano
Graph Theory - Articulation points using Tarjan (Arabic)
Graph Theory - Articulation points using Tarjan (Arabic)
Published: 2016/05/30
Channel: Arabic Competitive Programming
DIKU Talk:
DIKU Talk: 'Simple Algorithms Whose Analysis Isn't' by Robert Tarjan
Published: 2015/04/22
Channel: DIKU - Datalogisk Institut, Københavns Universitet
Topic 14 F DFS Applications TS SCC
Topic 14 F DFS Applications TS SCC
Published: 2013/10/24
Channel: UHMICSAlgorithms
Connected Components Code - Intro to Algorithms
Connected Components Code - Intro to Algorithms
Published: 2015/02/23
Channel: Udacity
Algorithms – Path Compression Tarjan
Algorithms – Path Compression Tarjan's Analysis II
Published: 2017/10/13
Channel: intrigano
Tarjan
Tarjan's Wedding 4
Published: 2017/08/10
Channel: Tarjan Bhattarai
09 - Path Compression Tarjans Analysis II [Advanced - Optional]
09 - Path Compression Tarjans Analysis II [Advanced - Optional]
Published: 2014/08/21
Channel: xind xrci
Janet Ginnings Training with Tee Tarjan at MighteeFit Health Studios
Janet Ginnings Training with Tee Tarjan at MighteeFit Health Studios
Published: 2010/02/13
Channel: jghairandbeauty
NEXT
GO TO RESULTS [51 .. 100]

WIKIPEDIA ARTICLE

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Tarjan's strongly connected components algorithm
Tarjan's Algorithm Animation.gif
Tarjan's algorithm animation
Data structure Graph
Worst-case performance

Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's Algorithm is named for its inventor, Robert Tarjan.[1]

Overview[edit]

The algorithm takes a directed graph as input, and produces a partition of the graph's vertices into the graph's strongly connected components. Each vertex of the graph appears in exactly one of the strongly connected components. Any vertex that is not on a directed cycle forms a strongly connected component all by itself: for example, a vertex whose in-degree or out-degree is 0, or any vertex of an acyclic graph.

The basic idea of the algorithm is this: a depth-first search begins from an arbitrary start node (and subsequent depth-first searches are conducted on any nodes that have not yet been found). As usual with depth-first search, the search visits every node of the graph exactly once, declining to revisit any node that has already been visited. Thus, the collection of search trees is a spanning forest of the graph. The strongly connected components will be recovered as certain subtrees of this forest. The roots of these subtrees are called the "roots" of the strongly connected components. Any node of a strongly connected component might serve as the root, if it happens to be the first node of the component that is discovered by the search.

Stack invariant[edit]

Nodes are placed on a stack in the order in which they are visited. When the depth-first search recursively visits a node v and its descendants, those nodes are not all necessarily popped from the stack when this recursive call returns. The crucial invariant property is that a node remains on the stack after it has been visited if and only if there exists a path in the input graph from it to some node earlier on the stack.

At the end of the call that visits v and its descendants, we know whether v itself has a path to any node earlier on the stack. If so, the call returns, leaving v on the stack to preserve the invariant. If not, then v must be the root of its strongly connected component, which consists of v together with any nodes later on the stack than v (such nodes all have paths back to v but not to any earlier node, because if they had paths to earlier nodes then v would also have paths to earlier nodes which is false). The connected component rooted at v is then popped from the stack and returned, again preserving the invariant.

Bookkeeping[edit]

Each node v is assigned a unique integer v.index, which numbers the nodes consecutively in the order in which they are discovered. It also maintains a value v.lowlink that represents (roughly speaking) the smallest index of any node known to be reachable from v, including v itself. Therefore v must be left on the stack if v.lowlink < v.index, whereas v must be removed as the root of a strongly connected component if v.lowlink == v.index. The value v.lowlink is computed during the depth-first search from v, as this finds the nodes that are reachable from v.

The algorithm in pseudocode[edit]

 algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty array
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  end for

  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)
    v.onStack := true

    // Consider successors of v
    for each (v, w) in E do
      if (w.index is undefined) then
        // Successor w has not yet been visited; recurse on it
        strongconnect(w)
        v.lowlink  := min(v.lowlink, w.lowlink)
      else if (w.onStack) then
        // Successor w is in stack S and hence in the current SCC
        // Note: The next line may look odd - but is correct.
        // It says w.index not w.lowlink; that is deliberate and from the original paper
        v.lowlink  := min(v.lowlink, w.index)
      end if
    end for

    // If v is a root node, pop the stack and generate an SCC
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        w.onStack := false
        add w to current strongly connected component
      while (w != v)
      output the current strongly connected component
    end if
  end function

The index variable is the depth-first search node number counter. S is the node stack, which starts out empty and stores the history of nodes explored but not yet committed to a strongly connected component. Note that this is not the normal depth-first search stack, as nodes are not popped as the search returns up the tree; they are only popped when an entire strongly connected component has been found.

The outermost loop searches each node that has not yet been visited, ensuring that nodes which are not reachable from the first node are still eventually traversed. The function strongconnect performs a single depth-first search of the graph, finding all successors from the node v, and reporting all strongly connected components of that subgraph.

When each node finishes recursing, if its lowlink is still set to its index, then it is the root node of a strongly connected component, formed by all of the nodes above it on the stack. The algorithm pops the stack up to and including the current node, and presents all of these nodes as a strongly connected component.

Complexity[edit]

Complexity: The Tarjan procedure is called once for each node; the forall statement considers each edge at most once. The algorithm's running time is therefore linear in the number of edges and nodes in G, i.e. .

In order to achieve this complexity, the test for whether w is on the stack should be done in constant time. This may be done, for example, by storing a flag on each node that indicates whether it is on the stack, and performing this test by examining the flag.

Additional remarks[edit]

While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse topological sort of the DAG formed by the strongly connected components.[2]

Donald Knuth described Tarjan's algorithm as one of Knuth's favorite implementations in his book The Stanford GraphBase.[3]

He also wrote:[4]

The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct.

References[edit]

  1. ^ Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160, doi:10.1137/0201010 
  2. ^ Harrison, Paul. "Robust topological sorting and Tarjan's algorithm in Python". Retrieved 9 February 2011. 
  3. ^ Knuth, The Stanford GraphBase, pages 512–519.
  4. ^ Knuth, Donald. "Twenty Questions for Donald Knuth". 

External links[edit]

Disclaimer

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license