Exercises on Graph Traversal and Unweighted Distance

1Problem 1: Paths, distance, and connected components

Let the undirected graph $$G=(V,E)$$G=(V,E) be defined by

1. List every path of length 2 from $$a$$a to $$d$$d.
2. Find $$d(a,d)$$d(a,d) and $$d(a,f)$$d(a,f).
3. Find all connected components.

1.1Solution

The length-2 paths are $$a,b,d$$a,b,d and $$a,c,d$$a,c,d. Therefore $$d(a,d)=2$$d(a,d)=2. No path joins $$a$$a to $$f$$f, so $$d(a,f)=\mathrm{\infty }$$d(a,f)=\infty. The connected components are $$\{a,b,c,d\}$$\{a,b,c,d\} and $$\{e,f\}$$\{e,f\}.

2Problem 2: DFS and BFS order

Use the graph from Problem 1 and examine every adjacency list in alphabetical order. Start at $$a$$a and mark a vertex visited when it is added to the candidates.

1. Determine the first-visit order of recursive DFS.
2. Determine the first-visit order of BFS.
3. Find the traversal levels $$\ell$$\ell recorded by BFS and verify that they equal the distances from $$a$$a to every reachable vertex.

2.1Solution

DFS visits $$a,b,d,c$$a,b,d,c. It proceeds from $$a$$a to $$b$$b, from $$b$$b to $$d$$d, and then from $$d$$d to the unvisited vertex $$c$$c.

BFS visits $$a,b,c,d$$a,b,c,d. The recorded distances are

These levels equal the lengths of the shortest paths found in Problem 1. Vertices $$e,f$$e,f are unreachable from $$a$$a.

3Problem 3: When to mark a vertex visited

Run BFS on the triangle graph

Explain what duplication may occur if a vertex is not marked visited until it is removed from the queue. Then explain why marking it when it is added prevents the duplication.

3.1Solution

Processing $$s$$s adds $$u,v$$u,v to the queue. When $$u$$u is removed, $$v$$v may still be unvisited, so edge $$\{u,v\}$$\{u,v\} can add $$v$$v again, leaving two copies of $$v$$v in the queue.

If a vertex is marked at insertion, then $$v\in S$$v\in S immediately after its first insertion. A later examination through another edge fails the condition $$v\notin S$$v\notin S, so every vertex is added to the candidates at most once.

4Problem 4: Representation, complexity, and method selection

Answer the following questions for an undirected graph with $$\left|V\right|=n$$|V|=n and $$\left|E\right|=m$$|E|=m.

1. Give the number of edge entries stored in adjacency lists and their space complexity.
2. Give the space complexity and edge-query time of an adjacency matrix, and choose a representation for a sparse graph.
3. Explain the running time of DFS and BFS with adjacency lists.
4. State whether DFS or BFS applies to unweighted shortest distance, reachability, and shortest distance with unequal edge weights.

4.1Solution

Each undirected edge appears once in the list of each endpoint, so there are $$2m$$2m edge entries and the lists, including the vertex headers, use $$O(n+m)$$O(n+m) space. An adjacency matrix uses $$O\left(n^2\right)$$O(n^2) space but answers an edge-existence query in $$O\left(1\right)$$O(1) time. Adjacency lists are preferable for a sparse graph, where $$m$$m is much smaller than $$n^2$$n^2.

With adjacency lists, each vertex is processed at most once and each undirected edge is examined at most once from each endpoint. Thus DFS and BFS run in $$O(n+m)$$O(n+m) time. Use BFS for unweighted shortest distance. Either DFS or BFS determines reachability. Neither ordinary DFS nor ordinary BFS guarantees shortest distance when edge weights differ; for nonnegative weights, use a method such as Dijkstra's algorithm.