P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38
2.9 Exercises 49
- Given the following adjacency matrix, compute the adjacency list and
the edge list.
A=
⎡
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
011000000
101000000
110110000
001011100
001101100
000110110
000111010
000001101
000000010
⎤
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
(2.29)
Special Graphs
- Prove that|E|=|V|−1 in trees.
Graph/Network Algorithms
- Consider the tree shown in Figure2.28. Traverse the graph using both
BFS and DFS and list the order in which nodes are visited in each
algorithm.
v 1
v 2 v^3
v 4 v 5 v 6 v 7
v 8 v 9 v 10 v 11 v 12
Figure 2.28. A Sample (Binary) Tree.
- For a tree and a nodev, under what condition isvvisited sooner by
BFS than DFS? Provide details. - For a real-world social network, is BFS or DFS more desirable? Provide
details. - Compute the shortest path between any pair of nodes using Dijkstra’s
algorithm for the graph in Figure2.29. - Detail why edges with negative weights are not desirable for computing
shortest paths using Dijkstra’s algorithm.