Graph Applications
? Modeling connectivity in computer
networks
? Representing maps
? Modeling flow capacities in networks
? Finding paths from start to goal (AI)
? Modeling transitions in algorithms
? Ordering tasks
? Modeling relationships (families,
organizations)
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|.
Graphs (2)
Paths and Cycles
Path,A sequence of vertices v1,v2,…,vn of length
n-1 with an edge from vi to vi+1 for 1 <= i < n.
A path is simple if all vertices on the path are
distinct.
A cycle is a path of length 3 or more that connects
vi to itself.
A cycle is simple if the path is simple,except the
first and last vertices are the same.
Connected Components
An undirected graph is connected if there is
at least one path from any vertex to any
other.
The maximum connected subgraphs of an
undirected graph are called connected
components.
Directed Representation
Undirected Representation
Representation Costs
Adjacency Matrix:
Adjacency List:
Graph ADT
class Graph { // Graph abstract class
public:
virtual int n() =0; // # of vertices
virtual int e() =0; // # of edges
// Return index of first,next neighbor
virtual int first(int) =0;
virtual int next(int,int) =0;
// Store new edge
virtual void setEdge(int,int,int) =0;
// Delete edge defined by two vertices
virtual void delEdge(int,int) =0;
// Weight of edge connecting two vertices
virtual int weight(int,int) =0;
virtual int getMark(int) =0;
virtual void setMark(int,int) =0;
};
Graph Traversals
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.
Examples:
– Artificial Intelligence Search
– Shortest paths problems
Graph Traversals (2)
To insure visiting all vertices:
void graphTraverse(const Graph* G) {
for (v=0; v<G->n(); v++)
G->setMark(v,UNVISITED); // Initialize
for (v=0; v<G->n(); v++)
if (G->getMark(v) == UNVISITED)
doTraverse(G,v);
}
Depth First Search (1)
// Depth first search
void DFS(Graph* G,int v) {
PreVisit(G,v); // Take action
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
DFS(G,w);
PostVisit(G,v); // Take action
}
Depth First Search (2)
Cost,?(|V| + |E|).
Breadth First Search (1)
Like DFS,but replace stack with a queue.
– Visit vertex’s neighbors before continuing
deeper in the tree.
Breadth First Search (2)
void BFS(Graph* G,int start,Queue<int>*Q) {
int v,w;
Q->enqueue(start); // Initialize Q
G->setMark(start,VISITED);
while (Q->length() != 0) { // Process Q
Q->dequeue(v);
PreVisit(G,v); // Take action
for(w=G->first(v);w<G->n();w=G->next(v,w))
if (G->getMark(w) == UNVISITED) {
G->setMark(w,VISITED);
Q->enqueue(w);
}
}
}
Breadth First Search (3)
Topological Sort (1)
Problem,Given a set of jobs,courses,etc.,
with prerequisite constraints,output the
jobs in an order that does not violate any
of the prerequisites.
Topological Sort (2)
void topsort(Graph* G) { // Topological sort
int i;
for (i=0; i<G->n(); i++) // Initialize
G->setMark(i,UNVISITED);
for (i=0; i<G->n(); i++) // Do vertices
if (G->getMark(i) == UNVISITED)
tophelp(G,i); // Call helper
}
void tophelp(Graph* G,int v) { // Process v
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
tophelp(G,w);
printout(v); // PostVisit for Vertex v
}
Topological Sort (3)
Queue-Based Topsort
void topsort(Graph* G,Queue<int>* Q) {int Count[G->n()];
int v,w;for (v=0; v<G->n(); v++) Count[v] = 0;
for (v=0; v<G->n(); v++) // Process edgesfor (w=G->first(v); w<G->n();
w = G->next(v,w))Count[w]++; // Add to v2's count
for (v=0; v<G->n(); v++) // Initialize Qif (Count[v] == 0) // No prereqs
Q->enqueue(v);while (Q->length() != 0) {
Q->dequeue(v);printout(v); // PreVisit for V
for (w=G->first(v); w<G->n();w = G->next(v,w)) {
Count[w]--; // One less prereqif (Count[w] == 0) // Now free
Q->enqueue(w);}}}
Shortest Paths Problems
Input,A graph with weights or costs
associated with each edge.
Output,The list of edges forming the shortest
path.
Sample problems:
– Find shortest path between two named vertices
– Find shortest path from S to all other vertices
– Find shortest path between all pairs of vertices
Will actually calculate only distances.
Shortest Paths Definitions
d(A,B) is the shortest distance from
vertex A to B.
w(A,B) is the weight of the edge
connecting A to B.
– If there is no such edge,then w(A,B) = ?.
Single-Source Shortest Paths
Given start vertex s,find the shortest path from s
to all other vertices.
Try 1,Visit vertices in some order,compute
shortest paths for all vertices seen so far,then
add shortest path to next vertex x.
Problem,Shortest path to a vertex already
processed might go through x.
Solution,Process vertices in order of distance from
s.
Dijkstra’s Algorithm Example
A B C D E
Initial 0 ? ? ? ?
Process A 0 10 3 20 ?
Process C 0 5 3 20 18
Process B 0 5 3 10 18
Process D 0 5 3 10 18
Process E 0 5 3 10 18
Dijkstra’s Implementation
// Compute shortest path distances from s,
// return them in D
void Dijkstra(Graph* G,int* D,int s) {
int i,v,w;
for (i=0; i<G->n(); i++) { // Do vertices
v = minVertex(G,D);
if (D[v] == INFINITY) return;
G->setMark(v,VISITED);
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > (D[v] + G->weight(v,w)))
D[w] = D[v] + G->weight(v,w);
}
}
Implementing minVertex
Issue,How to determine the next-closest
vertex? (I.e.,implement minVertex)
Approach 1,Scan through the table of
current distances.
– Cost,?(|V|2 + |E|) = ?(|V|2).
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|)
Approach 1
// Find min cost vertex
int minVertex(Graph* G,int* D) {
int i,v;
// Set v to an unvisited vertex
for (i=0; i<G->n(); i++)
if (G->getMark(i) == UNVISITED)
{ v = i; break; }
// Now find smallest D value
for (i++; i<G->n(); i++)
if ((G->getMark(i) == UNVISITED) &&
(D[i] < D[v]))
v = i;
return v;
}
Approach 2
void Dijkstra(Graph* G,int* D,int s) {int i,v,w; // v is current vertex
DijkElem temp;DijkElem E[G->e()]; // Heap array
temp.distance = 0; temp.vertex = s;E[0] = temp; // Initialize heap array
minheap<DijkElem,DDComp> H(E,1,G->e()); for (i=0; i<G->n(); i++) {// Get distances
do { if(!H.removemin(temp)) return;v = temp.vertex;
} while (G->getMark(v) == VISITED);G->setMark(v,VISITED);
if (D[v] == INFINITY) return;for(w=G->first(v); w<G->n(); w=G->next(v,w))
if (D[w] > (D[v] + G->weight(v,w))) {D[w] = D[v] + G->weight(v,w);
temp.distance = D[w]; temp.vertex = w;H.insert(temp); // Insert in heap
}}}
All-Pairs Shortest Paths
For every vertex u,v ?V,calculate d(u,v).
Could run Dijkstra’s Algorithm |V| times.
Better is Floyd’s Algorithm.
Define a k-path from u to v to be any path
whose intermediate vertices all have
indices less than k.
Floyd’s Algorithm
//Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
int D[G->n()][G->n()]; // Store distances
for (int i=0; i<G->n(); i++) // Initialize
for (int j=0; j<G->n(); j++)
D[i][j] = G->weight(i,j);
// Compute all k paths
for (int k=0; k<G->n(); k++)
for (int i=0; i<G->n(); i++)
for (int j=0; j<G->n(); j++)
if (D[i][j] > (D[i][k] + D[k][j]))
D[i][j] = D[i][k] + D[k][j];
}
Minimal Cost Spanning Trees
Minimal Cost Spanning Tree (MST) Problem:
Input,An undirected,connected graph G.
Output,The subgraph of G that
1) has minimum total cost as measured by
summing the values of all the edges in the
subset,and
2) keeps the vertices connected.
MST Example
Prim’s MST Algorithm
void Prim(Graph* G,int* D,int s) {
int V[G->n()]; // Who's closest
int i,w;
for (i=0; i<G->n(); i++) {// Do vertices
int v = minVertex(G,D);
G->setMark(v,VISITED);
if (v != s) AddEdgetoMST(V[v],v);
if (D[v] == INFINITY) return;
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);// Update dist
V[w] = v; // Update who it came from
}
}
}
Alternate Implementation
As with Dijkstra’s algorithm,the key issue is
determining which vertex is next closest.
As with Dijkstra’s algorithm,the alternative is
to use a priority queue.
Running times for the two implementations
are identical to the corresponding
Dijkstra’s algorithm implementations.
Kruskal’s MST Algorithm (1)
Initially,each vertex is in its own MST.
Merge two MST’s that have the shortest
edge between them.
– Use a priority queue to order the unprocessed
edges,Grab next one at each step.
How to tell if an edge connects two vertices
already in the same MST?
– Use the UNION/FIND algorithm with parent-
pointer representation.
Kruskal’s MST Algorithm (2)
Kruskal’s MST Algorithm (3)
Cost is dominated by the time to remove
edges from the heap.
– Can stop processing edges once all vertices
are in the same MST
Total cost,?(|V| + |E| log |E|).
? Modeling connectivity in computer
networks
? Representing maps
? Modeling flow capacities in networks
? Finding paths from start to goal (AI)
? Modeling transitions in algorithms
? Ordering tasks
? Modeling relationships (families,
organizations)
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|.
Graphs (2)
Paths and Cycles
Path,A sequence of vertices v1,v2,…,vn of length
n-1 with an edge from vi to vi+1 for 1 <= i < n.
A path is simple if all vertices on the path are
distinct.
A cycle is a path of length 3 or more that connects
vi to itself.
A cycle is simple if the path is simple,except the
first and last vertices are the same.
Connected Components
An undirected graph is connected if there is
at least one path from any vertex to any
other.
The maximum connected subgraphs of an
undirected graph are called connected
components.
Directed Representation
Undirected Representation
Representation Costs
Adjacency Matrix:
Adjacency List:
Graph ADT
class Graph { // Graph abstract class
public:
virtual int n() =0; // # of vertices
virtual int e() =0; // # of edges
// Return index of first,next neighbor
virtual int first(int) =0;
virtual int next(int,int) =0;
// Store new edge
virtual void setEdge(int,int,int) =0;
// Delete edge defined by two vertices
virtual void delEdge(int,int) =0;
// Weight of edge connecting two vertices
virtual int weight(int,int) =0;
virtual int getMark(int) =0;
virtual void setMark(int,int) =0;
};
Graph Traversals
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.
Examples:
– Artificial Intelligence Search
– Shortest paths problems
Graph Traversals (2)
To insure visiting all vertices:
void graphTraverse(const Graph* G) {
for (v=0; v<G->n(); v++)
G->setMark(v,UNVISITED); // Initialize
for (v=0; v<G->n(); v++)
if (G->getMark(v) == UNVISITED)
doTraverse(G,v);
}
Depth First Search (1)
// Depth first search
void DFS(Graph* G,int v) {
PreVisit(G,v); // Take action
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
DFS(G,w);
PostVisit(G,v); // Take action
}
Depth First Search (2)
Cost,?(|V| + |E|).
Breadth First Search (1)
Like DFS,but replace stack with a queue.
– Visit vertex’s neighbors before continuing
deeper in the tree.
Breadth First Search (2)
void BFS(Graph* G,int start,Queue<int>*Q) {
int v,w;
Q->enqueue(start); // Initialize Q
G->setMark(start,VISITED);
while (Q->length() != 0) { // Process Q
Q->dequeue(v);
PreVisit(G,v); // Take action
for(w=G->first(v);w<G->n();w=G->next(v,w))
if (G->getMark(w) == UNVISITED) {
G->setMark(w,VISITED);
Q->enqueue(w);
}
}
}
Breadth First Search (3)
Topological Sort (1)
Problem,Given a set of jobs,courses,etc.,
with prerequisite constraints,output the
jobs in an order that does not violate any
of the prerequisites.
Topological Sort (2)
void topsort(Graph* G) { // Topological sort
int i;
for (i=0; i<G->n(); i++) // Initialize
G->setMark(i,UNVISITED);
for (i=0; i<G->n(); i++) // Do vertices
if (G->getMark(i) == UNVISITED)
tophelp(G,i); // Call helper
}
void tophelp(Graph* G,int v) { // Process v
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
tophelp(G,w);
printout(v); // PostVisit for Vertex v
}
Topological Sort (3)
Queue-Based Topsort
void topsort(Graph* G,Queue<int>* Q) {int Count[G->n()];
int v,w;for (v=0; v<G->n(); v++) Count[v] = 0;
for (v=0; v<G->n(); v++) // Process edgesfor (w=G->first(v); w<G->n();
w = G->next(v,w))Count[w]++; // Add to v2's count
for (v=0; v<G->n(); v++) // Initialize Qif (Count[v] == 0) // No prereqs
Q->enqueue(v);while (Q->length() != 0) {
Q->dequeue(v);printout(v); // PreVisit for V
for (w=G->first(v); w<G->n();w = G->next(v,w)) {
Count[w]--; // One less prereqif (Count[w] == 0) // Now free
Q->enqueue(w);}}}
Shortest Paths Problems
Input,A graph with weights or costs
associated with each edge.
Output,The list of edges forming the shortest
path.
Sample problems:
– Find shortest path between two named vertices
– Find shortest path from S to all other vertices
– Find shortest path between all pairs of vertices
Will actually calculate only distances.
Shortest Paths Definitions
d(A,B) is the shortest distance from
vertex A to B.
w(A,B) is the weight of the edge
connecting A to B.
– If there is no such edge,then w(A,B) = ?.
Single-Source Shortest Paths
Given start vertex s,find the shortest path from s
to all other vertices.
Try 1,Visit vertices in some order,compute
shortest paths for all vertices seen so far,then
add shortest path to next vertex x.
Problem,Shortest path to a vertex already
processed might go through x.
Solution,Process vertices in order of distance from
s.
Dijkstra’s Algorithm Example
A B C D E
Initial 0 ? ? ? ?
Process A 0 10 3 20 ?
Process C 0 5 3 20 18
Process B 0 5 3 10 18
Process D 0 5 3 10 18
Process E 0 5 3 10 18
Dijkstra’s Implementation
// Compute shortest path distances from s,
// return them in D
void Dijkstra(Graph* G,int* D,int s) {
int i,v,w;
for (i=0; i<G->n(); i++) { // Do vertices
v = minVertex(G,D);
if (D[v] == INFINITY) return;
G->setMark(v,VISITED);
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > (D[v] + G->weight(v,w)))
D[w] = D[v] + G->weight(v,w);
}
}
Implementing minVertex
Issue,How to determine the next-closest
vertex? (I.e.,implement minVertex)
Approach 1,Scan through the table of
current distances.
– Cost,?(|V|2 + |E|) = ?(|V|2).
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|)
Approach 1
// Find min cost vertex
int minVertex(Graph* G,int* D) {
int i,v;
// Set v to an unvisited vertex
for (i=0; i<G->n(); i++)
if (G->getMark(i) == UNVISITED)
{ v = i; break; }
// Now find smallest D value
for (i++; i<G->n(); i++)
if ((G->getMark(i) == UNVISITED) &&
(D[i] < D[v]))
v = i;
return v;
}
Approach 2
void Dijkstra(Graph* G,int* D,int s) {int i,v,w; // v is current vertex
DijkElem temp;DijkElem E[G->e()]; // Heap array
temp.distance = 0; temp.vertex = s;E[0] = temp; // Initialize heap array
minheap<DijkElem,DDComp> H(E,1,G->e()); for (i=0; i<G->n(); i++) {// Get distances
do { if(!H.removemin(temp)) return;v = temp.vertex;
} while (G->getMark(v) == VISITED);G->setMark(v,VISITED);
if (D[v] == INFINITY) return;for(w=G->first(v); w<G->n(); w=G->next(v,w))
if (D[w] > (D[v] + G->weight(v,w))) {D[w] = D[v] + G->weight(v,w);
temp.distance = D[w]; temp.vertex = w;H.insert(temp); // Insert in heap
}}}
All-Pairs Shortest Paths
For every vertex u,v ?V,calculate d(u,v).
Could run Dijkstra’s Algorithm |V| times.
Better is Floyd’s Algorithm.
Define a k-path from u to v to be any path
whose intermediate vertices all have
indices less than k.
Floyd’s Algorithm
//Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
int D[G->n()][G->n()]; // Store distances
for (int i=0; i<G->n(); i++) // Initialize
for (int j=0; j<G->n(); j++)
D[i][j] = G->weight(i,j);
// Compute all k paths
for (int k=0; k<G->n(); k++)
for (int i=0; i<G->n(); i++)
for (int j=0; j<G->n(); j++)
if (D[i][j] > (D[i][k] + D[k][j]))
D[i][j] = D[i][k] + D[k][j];
}
Minimal Cost Spanning Trees
Minimal Cost Spanning Tree (MST) Problem:
Input,An undirected,connected graph G.
Output,The subgraph of G that
1) has minimum total cost as measured by
summing the values of all the edges in the
subset,and
2) keeps the vertices connected.
MST Example
Prim’s MST Algorithm
void Prim(Graph* G,int* D,int s) {
int V[G->n()]; // Who's closest
int i,w;
for (i=0; i<G->n(); i++) {// Do vertices
int v = minVertex(G,D);
G->setMark(v,VISITED);
if (v != s) AddEdgetoMST(V[v],v);
if (D[v] == INFINITY) return;
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);// Update dist
V[w] = v; // Update who it came from
}
}
}
Alternate Implementation
As with Dijkstra’s algorithm,the key issue is
determining which vertex is next closest.
As with Dijkstra’s algorithm,the alternative is
to use a priority queue.
Running times for the two implementations
are identical to the corresponding
Dijkstra’s algorithm implementations.
Kruskal’s MST Algorithm (1)
Initially,each vertex is in its own MST.
Merge two MST’s that have the shortest
edge between them.
– Use a priority queue to order the unprocessed
edges,Grab next one at each step.
How to tell if an edge connects two vertices
already in the same MST?
– Use the UNION/FIND algorithm with parent-
pointer representation.
Kruskal’s MST Algorithm (2)
Kruskal’s MST Algorithm (3)
Cost is dominated by the time to remove
edges from the heap.
– Can stop processing edges once all vertices
are in the same MST
Total cost,?(|V| + |E| log |E|).
