Page 280 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 13: Graphs

3. Test the program for obtaining the depth first spanning tree for the following graph: Notes

4. “A graph may have many spanning trees; for instance the complete graph on four vertices
has sixteen spanning trees”. Explain

5. Define vertices of a graph.
6. A graph is regular if every vertex has the same valence (that is, if it is adjacent to the
same number of other vertices). For a regular graph, a good implementation is to keep the
vertices in a linked list and the adjacency lists contiguous. The length of all the adjacency
lists is called the degree of the graph.
7. The topological sorting functions as presented in the text are deficient in error checking.

Modify the (a) depth-first and (b) breadth-first functions so that they will detect any

(directed) cycles in the graph and indicate what vertices cannot be placed in any topological
order because they lie on a cycle.
8. How can we determine a maximal spanning tree in a network?
9. Write Digraph methods called write that will write pertinent information specifying a
graph to the terminal. The graph is to be implemented with
a. An adjacency table;
b. A linked vertex list with linked adjacency lists;

c. A contiguous vertex list of linked adjacency lists.
10. Implement and test the method for determining shortest distances in directed graphs with
weights.

Answers: Self Assessment

1. spanning trees 2. edges

3. algorithm 4. unordered
5. directed cycle 6. True
7. False 8. False
9. True 10. True

LOVELY PROFESSIONAL UNIVERSITY 275