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:

discovery time: when recursive call starts
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

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.