CSCE 411 Lecture 17

Lecture Slides

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

Graphs

BFS Running Time

Initialization takes 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)} time.
Every node is enqueued and dequeued once, taking 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)} 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 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)}

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: 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)}
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 $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.