Chapter 7 Review
615
o n t H e c o m p u t e R
For Exercises 1–5, write a computer program that
produces the desired output from the given input.
1. Input: Adjacency matrix a for a directed graph
Output: Reachability matrix r for the graph, computed from the formula r = a ~ a
(2) ~ c~ a
(n)
2. Input: Adjacency matrix a for a directed graph
Output: Reachability matrix r for the graph, computed by using Warshall’s algorithm
3. Input: Adjacency matrix a for a graph
Output: Message indicating whether the graph has
an Euler path
4. Input: Adjacency matrix a for a simple weighted
graph or directed graph and two nodes in the graph
Output: Distance for the shortest path between the
two nodes or a message that no path exists; vertices in the shortest path if one exists (Hint: You will
need to find some way of denoting which vertices
are currently in IN.)
5. Input: Adjacency matrix a for a simple, weighted,
connected graph
Output: Arcs (as ordered pairs) in a minimal
spanning tree
For Exercises 6–8, first write a function that collects
information from the user about a graph and builds an
adjacency list representation of the graph; incorporate
this function in the programs requested.
6. Input: Information about a graph (see instructions
above) and a node in the graph
Output: Nodes in a depth-first search of the graph
beginning with the given node
7. Input: Information about a graph (see instructions
above) and a node in the graph
Output: Nodes in a breadth-first search of the graph
beginning with the given node
8. Input: Information about a graph (see instructions
above)
Output: Articulation points in the graph