The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science

CSci 131 - Data Structures
Week 10 Homework

1. Complete the graph representation segment of the Interactive Data Structure Visualization courseware and submit the problem electronically.

2. Complete the graph searching segment of the Interactive Data Structure Visualization courseware and submit the problem electronically.

3. Complete the graph categorization segment of the Interactive Data Structure Visualization courseware and submit the problem electronically.

4. Determine one correct topological order for the following directed graph:

V = {a, b, c, d, e}
E = {<a,b>, <a,c>, <c,d>, <a,d>, <c,e>}

Are there any other topological orders for this graph?

5. Modify the depth-first search procedure, program 10.3, so that it will visit a node more than once if it is a successor to more than one node. For example, in the graph in problem 4, the node d would be visited twice because it is a successor to both a and c. Be certain, however, to not visit a node a second twice on the same path. In other words, if there are cycles in the graph, your program should not loop infinitely around any cycle.