Java Reference
In-Depth Information
(a) IF an undirected graph is connected and has no simple cycles, THEN
the graph has jVj 1 edges.
(b) IF an undirected graph has jVj 1 edges and no cycles, THEN the
graph is connected.
11.3 (a) Draw the adjacency matrix representation for the graph of Figure 11.26.
(b) Draw the adjacency list representation for the same graph.
(c) If a pointer requires four bytes, a vertex label requires two bytes, and
an edge weight requires two bytes, which representation requires more
space for this graph?
(d) If a pointer requires four bytes, a vertex label requires one byte, and
an edge weight requires two bytes, which representation requires more
space for this graph?
11.4 Show the DFS tree for the graph of Figure 11.26, starting at Vertex 1.
11.5 Write a pseudocode algorithm to create a DFS tree for an undirected, con-
nected graph starting at a specified vertex V.
11.6 Show the BFS tree for the graph of Figure 11.26, starting at Vertex 1.
11.7 Write a pseudocode algorithm to create a BFS tree for an undirected, con-
nected graph starting at a specified vertex V.
11.8 The BFS topological sort algorithm can report the existence of a cycle if one
is encountered. Modify this algorithm to print the vertices possibly appearing
in cycles (if there are any cycles).
11.9 Explain why, in the worst case, Dijkstra's algorithm is (asymptotically) as
efficient as any algorithm for finding the shortest path from some vertex I to
another vertex J.
11.10 Show the shortest paths generated by running Dijkstra's shortest-paths alg-
orithm on the graph of Figure 11.26, beginning at Vertex 4.
Show the D
values as each vertex is processed, as in Figure 11.19.
11.11 Modify the algorithm for single-source shortest paths to actually store and
return the shortest paths rather than just compute the distances.
11.12 The root of a DAG is a vertex R such that every vertex of the DAG can be
reached by a directed path from R. Write an algorithm that takes a directed
graph as input and determines the root (if there is one) for the graph. The
running time of your algorithm should be (jVj + jEj).
11.13 Write an algorithm to find the longest path in a DAG, where the length of
the path is measured by the number of edges that it contains. What is the
asymptotic complexity of your algorithm?
11.14 Write an algorithm to determine whether a directed graph of jVj vertices
contains a cycle. Your algorithm should run in (jVj + jEj) time.
11.15 Write an algorithm to determine whether an undirected graph of jVj vertices
contains a cycle. Your algorithm should run in (jVj) time.
