cs126 depth & breath first search

What makes a traversal efficient?

It is efficient if it visits all edges and vertices in O(n).

What is a reachability problem?

It answers the question of if there is a path from one vertex to another.

Define subgraph.

A graph contained within a larger graph.

Define spanning graph.

A subgraph that contains all of the graph’s vertices.

When does a graph have only one spanning tree?

When the graph itself is a tree.

Define (free) tree.

A connected, undirected graph that contains no cycles.

Define forest.

An undirected (possibly unconnected) graph that contains no cycles.

What does a DFS/BFS do?

• Visits all the vertices and edges of G

• Determines whether G is connected

• Computes the connected components of G

• Computes a spanning forest of G

Describe how a DFS is performed starting at vertex u.

1. Mark u as visited

2. For each of its outgoing vertices, v

   • If v hasn’t been visited, record (u,v) as its ‘discovery edge’

3. Repeat from (1) with v

What are the properties of a DFS from start vertex u?

• The discovery edges form a spanning tree of the connected component of u

• The DFS tree contains directed paths from u to every vertex reachable from u

What is the time cost of setting / getting a vertex / edge?

O(1)

What is the time cost of performing a DFS on an adjacency list?

O(n+m)

How can DFS be specialised to find a path between two vertices u and v?

• Call DFS(u)

• Use a stack to keep track of the path

• As soon as v is encountered, the path is returned by popping from the stack

How is backtracking used in a DFS?

• At any vertex, if there is an unvisited neighbour, go there

• Otherwise retreat along the edge last traversed, to find an unvisited neighbour 

How can DFS be specialised to find a cycle in a graph?

• Run a DFS

• If any back edges exist, a cycle exists

How can a DFS be specialised for testing for connectivity in a graph?

• Run a DFS

• If the number of edges discovered in the DFS is equal to the total number in the graph, the graph is connected.

How can DFS be specialised to traverse an entire (possibly disconnected) graph?

Loop over all vertices, calling DFS on each univisited one.

Describe how a BFS is performed starting at vertex u.

1. Create a queue Q

2. Mark u as visited

3. Add u to Q

4. For all vertices v in Q

   1. For each of its edges to unexplored  vertices w:

      • Record (v,w) as DISCOVERY

      • Mark w as visited

      • Add w to Q

   2. For each of its edges to explored vertices x:

      • Record (v,x) as CROSS

Define forward edge.

An edge that connects a node to one of its descendants.

Define back edge.

An edge that connects a node to one of its ancestors.

Define cross edge.

An edge that connects two nodes that are neither descendants or ancestors of each other (in the BFS tree).

What are the properties of a BFS from some start vertex u?

• The discovery edges labeled by BFS form a spanning tree of the connected component of the start vertex

• For each vertex v in level i:

  • The path of the spanning tree from u to v has i edges

  • Every path from u to v in the BFS has at least i edges

What are the applications of a BFS?

• Compute the connected components of G

• Compute a spanning forest of G

• Find a simple cycle in G, or report that G is a forest

• Given two vertices of G, find a path in G between them with the minimum number of edges, or report that no such path exists

What are the differences between a DFS and BFS?

• DFS has front, back and cross edges

• BFS has only cross edges (and back edges on a directed graph)

What is the worst-case time cost of a breadth first search?

O(|E| + |V|)