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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V)}
Recursive call checks all neighbors; so total time in all recursive calls is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(E)}

Total time is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V+E)}

Nested Intervals

Let v.interval for vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is a descendent of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} ind the DFS forest iff the time interval of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is contained within the interval of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u}

Classifying Edges

Classifying graph edges in DFS traversal

Consider a directed graph formed by DFS forest.

tree edge: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is a child of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u}
back edge: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is an ancestor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u}
forward edge: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is a descendent of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} , but not a child.
cross edge: none of the above.