Section 6.1 Graphs and Their Representations
505
52. Given the adjacency matrix a for a directed graph G, describe the graph represented by the adjacency
matrix a
T
(see Exercise 15 in Section 5.7).
For Exercises 53–58, draw the adjacency list representation for the indicated graph.
53. Exercise 37
54. Exercise 38
55. Exercise 39
56. Exercise 40
57. Exercise 41
58. Exercise 42
59. Refer to the accompanying graph.
a. Draw the adjacency list representation.
b. How many storage locations are required for the adjacency list? (A pointer takes
one storage location.)
c. How many storage locations would be required in an adjacency matrix for this graph?
60. Draw the adjacency list representation for the following weighted directed graph.
1
1
3
2
4
2
1
2
3
61. For the directed graph of Exercise 42, construct the array-pointer representation.
62. For the weighted directed graph of Exercise 60, construct the array-pointer representation.
63. Draw the undirected graph represented by the following adjacency list.
2
1
1
2
1
2
3
4
3
4
3
2
2
3
4
4
3
64. Draw the directed graph represented by the following adjacency list.
1
2
1
1
2
3
4
4
2
3
6
4
5
1
2