CHAPTER 9
Graph Algorithms
9.1 The following ordering is arrived at by using a queue and assumes that vertices appear on an adjacency list
alphabetically. The topological order that results is then
9.2 Assuming the same adjacency list, the topological order produced when a stack is used is
9.3
/*
Finds a topological sort for a graph stored as adjacency list
Since the STL priority queue does not support decrease key
*/
#include<iostream>
#include<vector>
using namespace std;
class Graph
{
private:
vector<Vertex> adjList;
vector<int> indegrees;
if (indegrees[minDeg] > indegrees[i])
minDeg = i;
return minDeg;
}
minDeg= getMinDegIndex();
}
cout<<endl;
};
void readIn()
cin>>numVerts;
resize(numVerts);
for (int i = 0; i < numVerts; i++)
}
};
int main()
{
9.6 We’ll assume that Dijkstra’s algorithm is implemented with a priority queue of vertices that uses the
9.7 (a) The graph shown here is an example. Dijkstra’s algorithm gives a path from A to C of cost 2, when the
9.9
/*
Finds single source shortest path for a weighted graph stored as adjacency list
*/
#include<iostream>
#include<vector>
using namespace std;
class Graph
}
/**
* Print shortest path to v after dijkstra has run.
* Assume that the path exists.
*/
void printPath( int v )
{
int getSmallDistIndex()
{
int minIndex= –1;
for (int i = 0; i < adjList.size(); i++)
if (adjList[i].dist >= 0 && !adjList[i].known
&& (minIndex < 0 ||adjList[i].dist<adjList[minIndex].dist))
minIndex = i;
return minIndex;
{
int v = getSmallDistIndex();
adjList[v].known = true;
for (int i = 0; i < adjList[v].adj.size(); i++)
{
int w = adjList[v].adj[i];
if( !adjList[w].known )
{
void readIn()
{
int numVerts;
int outDegree;
int adjLabel;
}
}
};
int main()
{
Graph graph;
int start;
int finish;
*/
9.10 (a) Use an array count such that for any vertex u, count[u] is the number of distinct paths from s to u known
so far. When a vertex v is marked as known, its adjacency list is traversed. Let w be a vertex on the adjacency
list. If dv + cv,w = dw, then increment count[w] by count[v] because all shortest paths from s to v with last edge
(b) Use an array numEdges such that for any vertex u, numEdges[u] is the shortest number of edges on a path
9.11 (This solution is not unique.)
First, send four units of flow along the path s, G, H, I, t. This gives the following residual graph:
The preceding residual graph has no path from s to t. Thus the algorithm terminates. The final flow
graph, which carries 11 units, is as follows:
9.12 Let T be the tree with root r, and children r1, r2, . . . , rk, which are the roots of T1, T2, . . . , Tk, which have
maximum incoming flow of c1, c2, . . . , ck, respectively. By the problem statement, we may take the
maximum incoming flow of r to be infinity. The recursive pseudo-method findMaxFlow( T, incomingCap )
finds the value of the maximum flow in T (finding the actual flow is a matter of bookkeeping); the flow is
else
{
totalFlow = 0;
for( each subtree $T_i$ of T )
{
childFlow = findMaxFlow( $T_i$, min( incomingCap, $c_i$
) );
totalFlow += childFlow;
}
9.13 (a) Assume that the graph is connected and undirected. If it is not connected, then apply the algorithm to the
(b) Construct an undirected graph with a vertex for each instructor, a vertex for each course, and an edge
(c) Give each edge in the bipartite graph a weight of 1, and direct the edge from the instructor to the course.
9.14 (a) This is a slight modification of Dijkstra’s algorithm. Let fi be the best flow from s to i at any point in the
9.15 One possible minimum spanning tree is shown here. This solution is not unique.
9.17 The proof of this fact can be found in any good graph theory book. A more general theorem follows:
9.18
/*
Finds the min weight spanning tree for a weighted graph stored as adjacency list
Assumes vertex labels are integers from 0 to |V| -1
input format:
class DisjointSet
{
private:
vector<int> set;
public:
DisjointSet(int size= 0) : set(size,-1) {}
int find(int i)
if (set[setA] < set[setB])
{
set[setA] += set[setB];
set[setB] = setA;
}
struct Vertex
{
int label;
bool known;
vector<double> weight;
};
class Graph
{
private:
public:
Graph() {}
void insert(Vertex V)
}
edges.pop();
}
return tree;
}
void readIn()
cin>>numVerts;
for (int i = 0; i < numVerts; i++)
{
cin>>outDegree;
vertex.label = i;
for (int j = 0; j<outDegree; j++)
int main()
{
Graph graph;
vector<Edge> spanTree;
graph.readIn();
3 5 1 3 4 4 6
*/
9.19 The obvious solution using elementary methods is to bucket sort the edge weights in linear time. Then the
running time of Kruskal’s algorithm is dominated by the union/find operations and is O(|E|
(|E|, |V|)). The
9.20 Since the minimum spanning tree algorithm works for negative edge costs, an obvious solution is to replace
9.21 We start the depth-first search at A and visit adjacent vertices alphabetically. The articulation points are C, E,
9.22 The only difficult part is showing that if some nonroot vertex a is an articulation point, then there is no back
edge between any proper descendent of a and a proper ancestor of a in the depth-first spanning tree. We
prove this by a contradiction.
Let u and v be two vertices such that every path from u to v goes through a. At least one of u and v is a
9.24 Let (v, w) be a cross edge. Since at the time w is examined it is already marked, and w is not a descendent of
9.25 Suppose the vertices are numbered in preorder and postorder.
If (v, w) is a tree edge, then v must have a smaller preorder number than w. It is easy to see that the
9.26 The first depth-first spanning tree is
Gr, with the order in which to perform the second depth-first search, is shown next. The strongly
connected components are F and all other vertices.
9.17
/*
Finds the min weight spanning tree for a weighted graph stored as adjacency list
Assumes vertex labels are integers from 0 to |V| -1
input format:
output format: is a list of verticies and component numbers
*/
struct Vertex
{
private:
{
// cout<<“postorder: “<<i<<endl;
if (!vertexPtr->known)
}
void reachable(Vertex * & start, int compNum, vector<Vertex *> &revList)
{
if (start->component < 0) // not already assigned
}
public:
Graph() {}
void postOrder()
}
}while(i < adjList.size());
}
void printGraph(vector<Vertex *> list)
}
void sort(vector<Vertex *> & list)
// sorts in decending order
}
vector<Vertex*> reverseGraph()
{
vector<Vertex *> revAdjList(adjList.size());
for (int i = 0; i < adjList.size(); i++)
for(auto x: adjList)
for (auto y: x->adj)
revAdjList[y->label]->adj.push_back(revAdjList[x->label]);
return revAdjList;
}
void printComponents()
postOrder();// compute the post order visit number for each vertex
revAdjList= reverseGraph(); // create the reverse graph
sort(revAdjList);
do
void readIn()
{
int numVerts;
int outDegree;
}
for (int i = 0; i < numVerts; i++)
{
cin>>outDegree;
adjList[i]->label = i;
for (int j = 0; j<outDegree; j++)
int main()
{
Graph graph;
9.29 Because an edge (v, w) is implicitly processed, it is placed on a stack. If v is determined to be an articulation
9.30 Let (u, v) be an edge of the breadth-first spanning tree. (u, v) are connected, thus they must be in the same
9.33 If there is an Euler circuit, then it consists of entering and exiting nodes; the number of entrances clearly must
9.34 Neither of the proposed algorithms works. For example, as shown, a depth-first search of a biconnected graph
that follows A, B, C, D is forced back to A, where it is stranded.
9.36 All the algorithms work without modification for multigraphs.
9.37 Obviously, G must be connected. If each edge of G can be converted to a directed edge and produce a
9.38 (b) Define a graph where each stick is represented by a vertex. If stick Si is above Sj and thus must be
9.40 Use a greedy algorithm: At each step, choose the vertex with the highest connectivity to vertices not already
9.41 If no vertex has indegree 0, we can find a cycle by tracing backwards through vertices with positive indegree;
9.42 The basic idea is that we examine cell A[s,t]: If it is 0, then t is not a sink; otherwise s is not a sink. Each
9.43 Perform a postorder traversal, computing node sizes; the first node that has a size greater than N/2 vertices is
9.48 (a) Use the same ideas from the shortest path algorithm, but place unmarked adjacent squares at the front of a
9.49 SAME AS OLD 9.49
9.53 Each actor is a vertex; an edge connects two vertices if the actors have a shared movie role. The graph is not
9.56 Clearly, the baseball card collector problem (BCCP) is in NP, because it is easy to check if K packets contain