CSCE 411 Lecture 17

Lecture Slides

« previous | Wednesday, October 3, 2012 | next »

Graphs

BFS Running Time

• Initialization takes $O(V)$ time.
• Every node is enqueued and dequeued once, taking $O(V)$ time.
• When a node is dequeued, all its neighbors are checked to see if they are unvisited, taking time proportional to the number of neighbors, summing to $O(E)$

Total time is $O(V+E)$

Depth-First Search (DFS)

def depth_first_search graph
  graph.each_node do |u|
    u.visited = false
  end
  graph.each_node do |u|
    recursive_dfs u
  end
end

def recursive_dfs source
  source.visited = true
  source.neighbors.select{|v| not v.visited?}.each do |v|
    recursive_dfs v
  end
end

DFS is called on all nodes to make sure that we visit all nodes (helps with disconnected graph)

Like BFS, if we keep track of parents, we construct a forest resulting from the DFS traversal.

def depth_first_search graph
  graph.each_node do |u|
    u.visited = false
    u.parent = nil                      #!
  end
  graph.each_node do |u|
    u.parent = u                        #!
    recursive_dfs u
  end
end

def recursive_dfs source
  source.visited = true
  source.neighbors.select{|v| not v.visited?}.each do |v|
    v.parent = source                   #!
    recursive_dfs v
  end
end

Two more interesting pieces of information:

1. discovery time: when recursive call starts
2. finish time: when recursive call ends

def depth_first_search graph
  graph.each_node do |u|
    u.visited = false
    u.parent = nil
  end
  $time = 0                             #!
  graph.each_node do |u|
    u.parent = u
    recursive_dfs u
  end
end

def recursive_dfs source
  source.visited = true
  $time += 1                            #!
  source.discovery_time = $time         #!
  source.neighbors.select{|v| not v.visited?}.each do |v|
    v.parent = source
    recursive_dfs v
    $time += 1                          #!
    source.finish_time = $time          #!
  end
end

DFS Running Time

• Initialization: $O(V)$
• Non-recursive wrapper: $O(V)$
• Recursive call checks all neighbors; so total time in all recursive calls is $O(E)$

Total time is $O(V+E)$

Nested Intervals

Let v.interval for vertex $v$ be (v.discovery .. v.finish).

For any two nodes, either one interval precedes the other one or one is enclosed in the other one

• maximal "disjoint" time intervals represent DFS traversal of a "connected component"
• They will not overlap because overlapping implies a recursive call starts before the other one ends.

Corollary: $v$ is a descendent of $u$ ind the DFS forest iff the time interval of $v$ is contained within the interval of $u$

Classifying Edges

Classifying graph edges in DFS traversal

Consider a directed graph formed by DFS forest.

tree edge

$v$ is a child of $u$

back edge

$v$ is an ancestor of $u$

forward edge

$v$ is a descendent of $u$, but not a child.

cross edge

none of the above.