Java Reference
In-Depth Information
IN PRACTICE
14.19
In this chapter we claim that, for the implementation of graph algo-
rithms that run on large input, data structures are crucial to ensure
reasonable performance. For each of the following instances in which
a poor data structure or algorithm is used, provide a Big-Oh analysis
of the result and compare the actual performance with the algorithms
and data structures presented in the text. Implement only one change
at a time. You should run your tests on a reasonably large and some-
what sparse random graph. Then do the following.
a.
When an edge is read, determine whether it is already in the
graph.
b.
Implement the “dictionary” by using a sequential scan of the ver-
tex table.
c.
Implement the queue by using the algorithm in Exercise 6.24
(which should affect the unweighted shortest-path algorithm).
d.
In the unweighted shortest-path algorithm, implement the search for
the minimum-cost vertex as a sequential scan of the vertex table.
e.
Implement the priority queue by using the algorithm in Exercise 6.26
(which should affect the weighted shortest-path algorithm).
f.
Implement the priority queue by using the algorithm in Exercise 6.27
(which should affect the weighted shortest-path algorithm).
g.
In the weighted shortest-path algorithm, implement the search for
the minimum-cost vertex as a sequential scan of the vertex table.
h.
In the acyclic shortest-path algorithm, implement the search for a
vertex with indegree 0 as a sequential scan of the vertex table.
i.
Implement any of the graph algorithms by using an adjacency
matrix instead of adjacency lists.
PROGRAMMING PROJECTS
14.20
A directed graph is strongly connected if there is a path from every
vertex to every other vertex. Do the following.
a.
Pick any vertex S . Show that, if the graph is strongly connected, a
shortest-path algorithm will declare that all nodes are reachable
from S .
b.
Show that, if the graph is strongly connected and then the direc-
tions of all edges are reversed and a shortest-path algorithm is run
from S , all nodes will be reachable from S .
c.
Show that the tests in parts (a) and (b) are sufficient to decide
whether a graph is strongly connected (i.e., a graph that passes
both tests must be strongly connected).
Search WWH ::




Custom Search