10.Graphs§
- A graph G=(V,E) consists of a set of vertices V, and a set of edges E, such that each edge in E is a connection between a pair of vertices in V.
- The number of vertices is written |V|, and the number edges is written |E|.
interface Graph { // Graph class ADT
// Initialize the graph with some number of vertices
void init(int n);
// Return the number of vertices
int nodeCount();
// Return the current number of edges
int edgeCount();
// Get the value of node with index v
Object getValue(int v);
// Set the value of node with index v
void setValue(int v, Object val);
// Adds a new edge from node v to node w with weight wgt
void addEdge(int v, int w, int wgt);
// Get the weight value for an edge
int weight(int v, int w);
// Removes the edge from the graph.
void removeEdge(int v, int w);
// Returns true iff the graph has the edge
boolean hasEdge(int v, int w);
// Returns an array containing the indicies of the neighbors of v
int[] neighbors(int v);
}
.
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED)
DoSomething();
Some applications require visiting every vertex in the graph exactly once.
The application may require that vertices be visited in some special order based on graph topology.
void graphTraverse(Graph G) {
int v;
for (v=0; v<G.nodeCount(); v++)
G.setValue(v, null); // Initialize
for (v=0; v<G.nodeCount(); v++)
if (G.getValue(v) != VISITED)
doTraversal(G, v);
}
void DFS(Graph G, int v) {
PreVisit(G, v);
G.setValue(v, VISITED);
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED)
DFS(G, nList[i]);
PostVisit(G, v);
}
Cost: Θ(|V|+|E|).
.
void BFS(Graph G, int v) {
LQueue Q = new LQueue(G.nodeCount());
Q.enqueue(v);
G.setValue(v, VISITED);
while (Q.length() > 0) { // Process each vertex on Q
v = (Integer)Q.dequeue();
PreVisit(G, v);
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED) { // Put neighbors on Q
G.setValue(nList[i], VISITED);
Q.enqueue(nList[i]);
}
PostVisit(G, v);
}
}
.
void topsortDFS(Graph G) {
int v;
for (v=0; v<G.nodeCount(); v++)
G.setValue(v, null); // Initialize
for (v=0; v<G.nodeCount(); v++)
if (G.getValue(v) != VISITED)
tophelp(G, v);
}
void tophelp(Graph G, int v) {
G.setValue(v, VISITED);
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED)
tophelp(G, nList[i]);
printout(v);
}
.
void topsortBFS(Graph G) { // Topological sort: Queue
Queue Q = new LQueue(G.nodeCount());
int[] Count = new int[G.nodeCount()];
int[] nList;
int v;
for (v=0; v<G.nodeCount(); v++) Count[v] = 0; // Initialize
for (v=0; v<G.nodeCount(); v++) { // Process every edge
nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
Count[nList[i]]++; // Add to v's prereq count
}
for (v=0; v<G.nodeCount(); v++) // Initialize Queue
if (Count[v] == 0) // V has no prerequisites
Q.enqueue(v);
while (Q.length() > 0) { // Process the vertices
v = (Integer)Q.dequeue();
printout(v); // PreVisit for Vertex V
nList = G.neighbors(v);
for (int i=0; i< nList.length; i++) {
Count[nList[i]]--; // One less prerequisite
if (Count[nList[i]] == 0) // This vertex is now free
Q.enqueue(nList[i]);
}
}
}
.
.
Input: A graph with weights or costs associated with each edge.
Output: The list of edges forming the shortest path.
Will actually calculate only distances.
.
// Compute shortest path distances from s, store them in D
void Dijkstra(Graph G, int s, int[] D) {
for (int i=0; i<G.nodeCount(); i++) // Initialize
D[i] = INFINITY;
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // Process the vertices
int v = minVertex(G, D); // Find next-closest vertex
G.setValue(v, VISITED);
if (D[v] == INFINITY) return; // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w)))
D[w] = D[v] + G.weight(v, w);
}
}
}
Issue: How to determine the next-closest vertex? (I.e., implement minVertex)
Approach 2: Store unprocessed vertices using a min-heap to implement a priority queue ordered by D value. Must update priority queue for each edge.
Cost: Θ((|V|+|E|)log|V|)
// Find the unvisited vertex with the smalled distance
int minVertex(Graph G, int[] D) {
int v = 0; // Initialize v to any unvisited vertex;
for (int i=0; i<G.nodeCount(); i++)
if (G.getValue(i) != VISITED) { v = i; break; }
for (int i=0; i<G.nodeCount(); i++) // Now find smallest value
if ((G.getValue(i) != VISITED) && (D[i] < D[v]))
v = i;
return v;
}
// Dijkstra's shortest-paths: priority queue version
void DijkstraPQ(Graph G, int s, int[] D) {
int v; // The current vertex
KVPair[] E = new KVPair[G.edgeCount()]; // Heap for edges
E[0] = new KVPair(0, s); // Initial vertex
MinHeap H = new MinHeap(E, 1, G.edgeCount());
for (int i=0; i<G.nodeCount(); i++) // Initialize distance
D[i] = INFINITY;
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // For each vertex
do { KVPair temp = H.removemin();
if (temp == null) return; // Unreachable nodes exist
v = (Integer)temp.value(); } // Get position
while (G.getValue(v) == VISITED);
G.setValue(v, VISITED);
if (D[v] == INFINITY) return; // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w))) { // Update D
D[w] = D[v] + G.weight(v, w);
H.insert(D[w], w);
}
}
}
}
.
We could run Shortest Paths starting at each vertex.
Define a k-path from vertex v to vertex u to be any path whose intermediate vertices (aside from v and u) all have indices less than k.
/** Compute all-pairs shortest paths */
static void Floyd(Graph G, int[][] D) {
for (int i=0; i<G.n(); i++) // Initialize D with weights
for (int j=0; j<G.n(); j++)
if (G.weight(i, j) != 0) D[i][j] = G.weight(i, j);
for (int k=0; k<G.n(); k++) // Compute all k paths
for (int i=0; i<G.n(); i++)
for (int j=0; j<G.n(); j++)
if ((D[i][k] != Integer.MAX_VALUE) &&
(D[k][j] != Integer.MAX_VALUE) &&
(D[i][j] > (D[i][k] + D[k][j])))
D[i][j] = D[i][k] + D[k][j];
}
Minimal Cost Spanning Tree (MST) Problem:
Input: An undirected, connected graph G.
- Output: The subgraph of G that
- has minimum total cost as measured by summing the values of all the edges in the subset, and
- keeps the vertices connected.
.
// Compute shortest distances to the MCST, store them in D.
// V[i] will hold the index for the vertex that is i's parent in the MCST
void Prim(Graph G, int s, int[] D, int[] V) {
for (int i=0; i<G.nodeCount(); i++) // Initialize
D[i] = INFINITY;
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // Process the vertices
int v = minVertex(G, D); // Find next-closest vertex
G.setValue(v, VISITED);
if (D[v] == INFINITY) return; // Unreachable
if (v != s) AddEdgetoMST(V[v], v);
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > G.weight(v, w)) {
D[w] = G.weight(v, w);
V[w] = v;
}
}
}
}
Initially, each vertex is in its own MST.
How to tell if an edge connects two vertices already in the same MST?
representation.
.
Total cost: Θ(|V|+|E|log|E|).