Scribd Logo
Upload

Welcome to Scribd!

  • 56 views

    Kosaraju's Two-Pass Algorithm

    Uploaded by

    Andrew Lee
    Kosaraju's Two-Pass Algorithm finds the strongly connected components (SCCs) of a directed graph using two depth-first searches. It first reverses the graph and runs DFS to number the vertices by finishing time. It then iterates through these vertices in reverse order, running DFS a second time. This second pass explores only "sink" nodes of each SCC, allowing it to uncover the SCCs. The algorithm runs in O(m+n) time, where m is the number of edges and n is the number of vertices.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Kosaraju's Two-Pass Algorithm

    Uploaded by

    Andrew Lee
    56 views2 pages
    Kosaraju's Two-Pass Algorithm finds the strongly connected components (SCCs) of a directed graph using two depth-first searches. It first reverses the graph and runs DFS to number the vertices by finishing time. It then iterates through these vertices in reverse order, running DFS a second time. This second pass explores only "sink" nodes of each SCC, allowing it to uncover the SCCs. The algorithm runs in O(m+n) time, where m is the number of edges and n is the number of vertices.

    Original Title

    kosaraju.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Kosaraju's Two-Pass Algorithm finds the strongly connected components (SCCs) of a directed graph using two depth-first searches. It first reverses the graph and runs DFS to number the vertices by finishing time. It then iterates through these vertices in reverse order, running DFS a second time. This second pass explores only "sink" nodes of each SCC, allowing it to uncover the SCCs. The algorithm runs in O(m+n) time, where m is the number of edges and n is the number of vertices.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    56 views2 pages

    Kosaraju's Two-Pass Algorithm

    Uploaded by

    Andrew Lee
    Kosaraju's Two-Pass Algorithm finds the strongly connected components (SCCs) of a directed graph using two depth-first searches. It first reverses the graph and runs DFS to number the vertices by finishing time. It then iterates through these vertices in reverse order, running DFS a second time. This second pass explores only "sink" nodes of each SCC, allowing it to uncover the SCCs. The algorithm runs in O(m+n) time, where m is the number of edges and n is the number of vertices.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Kosarajus Two-Pass Algorithm

    Algorithm

    The strongly connected components (SCCs) of a directed graph G are its


    maximal strongly connected subgraphs, where a strongly connected subgraph is one where there is a path from each vertex to every other vertex.
    1

    11

    13

    15

    def kosaraju ( G ) :
    S = stack ()
    G_rev = reverse ( G )

    # Reverse all the edges in G

    # Pass 1
    for v in G_rev :
    if v unexplored :
    explore ( v )
    DFS_pass1 ( G_rev , v , S )
    # Pass 2
    while not empty ( S ) :
    v = S . pop ()
    if v explored : # Flipped after pass 1
    unexplore ( v )
    SCC rooted at S = DFS_pass2 (G , v )

    17

    19

    21

    23

    25

    27

    29

    31

    def DFS_pass1 (G , v , stack ) :


    for (v , w ) in G :
    if w unexplored :
    explore ( w )
    DFS_pass1 (G , w )
    stack . push ( v )
    def DFS_pass2 (G , v ) :
    nodes = []
    for (v , w ) in G :
    if w explored :
    unexplore ( w )
    nodes += w
    DFS_pass2 (G , w )
    return nodes

    Essentially, the algorithm sorts the vertices in the graph by DFS finishing time and then iterates backwards through them to conduct one more
    DFS to uncover the SCCs. The second pass only explores sink nodes of
    a respective SCC.

    Kosarajus Two-Pass Algorithm


    2

    Analysis/Correctness

    The SCCs of G themselves introduce a meta-DAG, in that if they are collapsed into nodes and the paths between then are maintained, the resulting
    graph is also a DAG.
    Key Lemma

    c1

    Consider 2 adjacent SCCs in G:


    ~e

    c2

    If f (v) is the position on the stack of node v, with higher values corresponding to positions towards the top of the stack, then:
    max f (v) < max f (w)
    vc1

    (1)

    wc2

    Proof of Key Lemma In the first pass of the algorithm, all of c1 is


    explored before c2 because the meta-graph is acyclic. That is, if the first v
    chosen in the looped DFS is inside c2 , the algorithm will trace paths all the
    way to a sink vertex in c1 and push the rest of its nodes onto the stack
    before backtracking to c2 .
    Corollary From the key lemma, we deduce that the maximum f-value
    (top of the stack) must lie in the sink SCC in the meta-graph.
    f2

    f1 < f2 < f3 < f4

    f1

    f4
    f3

    Correctness Intuition By the above corollary, the second pass of the


    algorithm begins in a sink SCC, c . The first DFS uncovers c , and the rest
    recurses on G c .
    Runtime Because the algorithm is really just 2 DFS loops, it runs in
    O(m + n) time with some slow constants.
    2

    You might also like