Chapter ObjeCtives
After studying this chapter, you will be able to:
• Convert between adjacency matrix, adjacency relation, and directed graph
representations.
• Use the reachability matrix of a directed graph to determine whether one node
is reachable from another.
• Compute the reachability matrix of a directed graph either directly or by using
Warshall’s algorithm.
• Test a graph for the existence of an Euler path (solve the highway inspector
problem).
• Understand the Hamiltonian circuit problem (and the traveling salesman problem) and how they are fundamentally different from the Euler path problem.
• Use Dijkstra’s algorithm to find the shortest path between two nodes in a simple,
weighted, connected graph.
• Use Prim’s algorithm to find the minimal spanning tree in a simple, weighted,
connected graph.
• Carry out depth-first search and breadth-first search in a simple, connected graph.
• Understand how depth-first search can be used to test for reachability in a directed graph, perform a topological sort on a partially ordered set represented
by a directed graph, and find the connected components of an unconnected
graph.
• Identify articulation points in a simple connected graph.
You are the network administrator for a wide-area backbone network that serves your
company’s many offices across the country. Messages travel through the network by
being routed from point to point until they reach their destination. Each node in the
network therefore acts as a switching station to forward messages to other nodes according to a routing table maintained at each node. Some connections in the network
carry heavy traffic, while others are less used. Traffic may vary with the time of day;
in addition, new nodes occasionally come on line and existing nodes may go off line.
Therefore you must periodically provide each node with updated information so that
it can forward messages along the most efficient (that is, the least heavily traveled)
route.
Question: How can you compute the routing table for each node?
7 7
Graph Algorithms
C h a p t e r
553
After studying this chapter, you will be able to:
• Convert between adjacency matrix, adjacency relation, and directed graph
representations.
• Use the reachability matrix of a directed graph to determine whether one node
is reachable from another.
• Compute the reachability matrix of a directed graph either directly or by using
Warshall’s algorithm.
• Test a graph for the existence of an Euler path (solve the highway inspector
problem).
• Understand the Hamiltonian circuit problem (and the traveling salesman problem) and how they are fundamentally different from the Euler path problem.
• Use Dijkstra’s algorithm to find the shortest path between two nodes in a simple,
weighted, connected graph.
• Use Prim’s algorithm to find the minimal spanning tree in a simple, weighted,
connected graph.
• Carry out depth-first search and breadth-first search in a simple, connected graph.
• Understand how depth-first search can be used to test for reachability in a directed graph, perform a topological sort on a partially ordered set represented
by a directed graph, and find the connected components of an unconnected
graph.
• Identify articulation points in a simple connected graph.
You are the network administrator for a wide-area backbone network that serves your
company’s many offices across the country. Messages travel through the network by
being routed from point to point until they reach their destination. Each node in the
network therefore acts as a switching station to forward messages to other nodes according to a routing table maintained at each node. Some connections in the network
carry heavy traffic, while others are less used. Traffic may vary with the time of day;
in addition, new nodes occasionally come on line and existing nodes may go off line.
Therefore you must periodically provide each node with updated information so that
it can forward messages along the most efficient (that is, the least heavily traveled)
route.
Question: How can you compute the routing table for each node?
7 7
Graph Algorithms
C h a p t e r
553