Homework 4 (due 4/28)
CSC 321

We reviewed some of the basics of graph theory (Sections 2.5, 2.6), and talked about depth-first search (Section 4.2). We saw some initial applications (including Robbins' Theorem, which we will prove next time). Next time we will see additional applications, such as Topological Sort (Section 4.4) and more on to other graph algorithms, inclduing Breadth-First Search (Section 4.3) and Minimum Spanning Tree (Sections 7.2 and 7.3).

See Graphs in Python for a short introduction on how to encode graphs in Python (using the adjacency list model).

Midterm will be during class on Wednesday, 5/6 (6th week).

: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns. You do not need to include the code (or any executables).

1. (Reading Assignment) Read Sections 2.5, 2.6 (review), Section 3.3 (pg 116/117), Graphs in Python, and 4.2.

2. (Directed Graphs, 10pt) A directed graph is a graph in which every edge has a direction, so it is a pair (u,v) of vertices, pointing from u to v, rather than a set {u,v}, which is what an edge in an undirected graph is. (Section 2.5 has more information.) Given a directed graph G = (V,E), we can define its tranpose, tr(G), as the graph in which the direction of every edge of G has been reversed.

For the following problems, let n = |V|, and m = |E| (this is standard).

a) [2pt] What is the asymptotic running time of an algorithm calculating tr(G) from G in the adjacency matrix model? Express your answer in n and m as appropriate.

b) [3pt] What is the asymptotic running time of an algorithm calculating tr(G) from G in the adjacency list model? Express your answer in n and m as appropriate.

c) [5pt] Implement tr(G) for the adjacency list model and test-run it on some small sample graphs.

3. (DFS, 5pt) Do Exercise 4.2.2 (page 179) of the book. You don't have to show the details of performing the DFS, however, in your answer, clearly show the tree edges, and how they are oriented (away from the root), and identify the back edges (e.g. by using a different color). So your answer for this could be a picture of the graph in Exercise 4.2.2, with each edge directed, and colored according to type (tree or back).

4. (DFS, 20pt) The tasks in this problem ask you to implement variants of the DFS algorithm. You may want to implement a basic version of the algorithm first and test it before you implement the modifications below. For each of the following include a testrun on a small graph and illustrate the output.

a) [10pt] Implement basic Depth-First Search to traverse a graph given by an adjacency list. Print the vertices in the order that you encounter them. For this problem you can assume that the graph is connected. Hint: this is very close to the algorithm on page 175. Try to avoid global variables though.

b) [10pt] Modify your implementation of DFS from a) so it counts the number of connected components of a given graph. Test your algorithm on the graphs g0, g1, g2, and g3 of DFSgraphs.txt. Hint: Algorithm 4.2.4 in the book should be a good starting point. For testing: g0 has 2, g1 has 3, and g2 has 17 connected components. I'll let you figure out g3.

5. (Extra Credit, 10pt) The problem with the DFS implementations in 4 is that they are recursive, and that the recursion depth grows with the number of vertices in the graph. For Python this means that the stack will blow as soon as you find a path of length >= 1000 (roughly), and even increasing the recursion depth doesn't lead to efficient code. Reimplement your solution for 4b for counting connected components iteratively, and determine the number of connected compoents of the graph g4 in g4.zip. (g4 has around 100,000 vertices).

Marcus Schaefer
Last updated: April 23, 2015.