[go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • Depth-First Search: COMP171 Fall 2005

    Uploaded by

    Praveen Kumar
    205 views27 pages
    Depth-first search (DFS) is a graph search algorithm that explores all the vertices reachable from a source vertex. It works by continuing to visit unvisited neighbors of the most recently visited vertex in a recursive manner. DFS can provide information about a graph like whether it contains cycles. The time complexity of DFS is O(V+E) as it examines each vertex and edge at most once. DFS results in a tree structure called a DFS tree that captures the recursive calls made during the search.

    Original Description:

    data

    Original Title

    dfs

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Report this Document
    Depth-first search (DFS) is a graph search algorithm that explores all the vertices reachable from a source vertex. It works by continuing to visit unvisited neighbors of the most recently visited vertex in a recursive manner. DFS can provide information about a graph like whether it contains cycles. The time complexity of DFS is O(V+E) as it examines each vertex and edge at most once. DFS results in a tree structure called a DFS tree that captures the recursive calls made during the search.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Flag for inappropriate content
    Download as ppt, pdf, or txt
    205 views27 pages

    Depth-First Search: COMP171 Fall 2005

    Uploaded by

    Praveen Kumar
    Depth-first search (DFS) is a graph search algorithm that explores all the vertices reachable from a source vertex. It works by continuing to visit unvisited neighbors of the most recently visited vertex in a recursive manner. DFS can provide information about a graph like whether it contains cycles. The time complexity of DFS is O(V+E) as it examines each vertex and edge at most once. DFS results in a tree structure called a DFS tree that captures the recursive calls made during the search.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Flag for inappropriate content
    Download as ppt, pdf, or txt
    of 27

    COMP171 Fall 2005

    Depth-first search

    Graph / Slide 2

    Depth-First Search (DFS)

    DFS is another popular graph search strategy

    Idea is similar to pre-order traversal (visit children first)

    DFS can provide certain information about the graph that BFS cannot

    It can tell whether we have encountered a cycle or not More in COMP271

    Graph / Slide 3

    DFS Algorithm
    DFS

    will continue to visit neighbors in a recursive pattern


    Whenever we visit v from u, we recursively visit all unvisited neighbors of v. Then we backtrack (return) to u. Note: it is possible that w2 was unvisited when we recursively visit w1, but became visited by the time we return from the recursive call.
    u v w1 w2 w3

    Graph / Slide 4

    DFS Algorithm
    Flag all vertices as not visited

    Flag yourself as visited For unvisited neighbors, call RDFS(w) recursively

    We can also record the paths using pred[ ].

    Graph / Slide 5

    Example
    Adjacency List Visited Table (T/F)
    0

    0 8
    source

    F F F F F F

    1 2

    3 4 5

    1
    3 4 5

    7
    6

    6
    7 8 9

    F
    F F F

    Pred Initialize visited table (all False) Initialize Pred to -1

    Graph / Slide 6

    Example
    Adjacency List 0 8
    source

    Visited Table (T/F)


    0 1 2 3

    F F T F F F

    2 1 3 7

    4 5

    F
    F F F

    6 5

    7 8 9

    Pred Mark 2 as visited

    RDFS( 2 ) Now visit RDFS(8)

    Graph / Slide 7

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    F F T F F F

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T F

    2 -

    Pred Mark 8 as visited


    Recursive calls

    RDFS( 2 ) RDFS(8) 2 is already visited, so visit RDFS(0)

    mark Pred[8]

    Graph / Slide 8

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T F T F F F

    8 -

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T F

    2 -

    Pred Mark 0 as visited


    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(0) -> no unvisited neighbors, return to call RDFS(8)

    Mark Pred[0]

    Graph / Slide 9

    Example
    0
    source

    Back to 8 8

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T F T F F F

    8 -

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T F

    2 -

    Pred
    Recursive calls

    RDFS( 2 ) RDFS(8) Now visit 9 -> RDFS(9)

    Graph / Slide 10

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T F T F F F

    8 -

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T T

    2 8

    Pred Mark 9 as visited


    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) -> visit 1, RDFS(1)

    Mark Pred[9]

    Graph / Slide 11

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T F F F

    8 9 -

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T T

    2 8

    Pred Mark 1 as visited


    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) visit RDFS(3)

    Mark Pred[1]

    Graph / Slide 12

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T T F F

    8 9 1 -

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T T

    2 8

    Pred Mark 3 as visited


    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) visit RDFS(4)

    Mark Pred[3]

    Graph / Slide 13

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T T T F

    8 9 1 3 -

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T T

    2 8

    Pred
    Recursive calls

    RDFS( 2 ) Mark 4 as visited RDFS(8) RDFS(9) Mark Pred[4] RDFS(1) RDFS(3) RDFS(4) STOP all of 4s neighbors have been visited return back to call RDFS(3)

    Graph / Slide 14

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T T T F

    8 9 1 3 -

    3 4 5

    1
    3 4 Back to 3 RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) visit 5 -> RDFS(5) 5 7 6

    6
    7 8 9

    F
    F T T

    2 8

    Pred
    Recursive calls

    Graph / Slide 15

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T T T T

    8 9 1 3 3

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    F
    F T T

    2 8

    Pred
    Recursive calls

    RDFS( 2 ) RDFS(8) Mark 5 as visited RDFS(9) Mark Pred[5] RDFS(1) RDFS(3) RDFS(5) 3 is already visited, so visit 6 -> RDFS(6)

    Graph / Slide 16

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T T T T

    8 9 1 3 3

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    T
    F T T

    5
    2 8

    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) RDFS(6) visit 7 -> RDFS(7)

    Pred

    Mark 6 as visited
    Mark Pred[6]

    Graph / Slide 17

    Example
    0
    8
    source

    Adjacency List

    Visited Table (T/F)


    0 1 2

    T T T T T T

    8 9 1 3 3

    3 4 5

    1
    3 4 5 7 6

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Recursive calls

    Pred RDFS( 2 ) RDFS(8) Mark 7 as visited RDFS(9) RDFS(1) Mark Pred[7] RDFS(3) RDFS(5) RDFS(6) RDFS(7) -> Stop no more unvisited neighbors

    Graph / Slide 18

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) RDFS(6) -> Stop

    Pred

    Graph / Slide 19

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) -> Stop

    Pred

    Graph / Slide 20

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) -> Stop

    Pred

    Graph / Slide 21

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) -> Stop

    Pred

    Graph / Slide 22

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Recursive calls

    RDFS( 2 ) RDFS(8) RDFS(9) -> Stop

    Pred

    Graph / Slide 23

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    RDFS( 2 ) RDFS(8) -> Stop


    Recursive calls

    Pred

    Graph / Slide 24

    Example
    Adjacency List 0 Visited Table (T/F)
    0

    T T T T T T

    8 9 1 3 3

    8
    source

    1 2

    2 1 3

    4 5

    7
    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    RDFS( 2 ) -> Stop


    Recursive calls

    Pred

    Graph / Slide 25

    Example
    0 8
    source

    Adjacency List

    Visited Table (T/F)


    0 1

    T T T T T T

    8 9 1 3 3

    2 1 3 7

    2 3 4 5

    6 5

    6
    7 8 9

    T
    T T T

    5
    6 2 8

    Check our paths, does DFS find valid paths? Yes. Try some examples. Path(0) -> Path(6) -> Path(7) ->

    Pred

    Graph / Slide 26

    Time Complexity of DFS


    (Using adjacency list)

    We never visited a vertex more than once We had to examine all edges of the vertices

    We know vertex v degree(v) = 2m where m is the number of edges

    So, the running time of DFS is proportional to the number of edges and number of vertices (same as BFS)

    O(n + m)

    You will also see this written as:

    O(|v|+|e|)

    |v| = number of vertices (n) |e| = number of edges (m)

    Graph / Slide 27

    DFS Tree
    Resulting DFS-tree. Notice it is much deeper than the BFS tree.

    Captures the structure of the recursive calls - when we visit a neighbor w of v, we add w as child of v - whenever DFS returns from a vertex v, we climb up in the tree from v to its parent

    You might also like