EECE 330 Chapter, Fall 2011
American University of Beirut · Data Structures and Algorithms · 55 pages · Prof. Hassan Artail
Showing the first 10 of 55 pages. Download the PDF to see all of it.
More EECE 330 files
Show the text of this chapter
Graphs
EECE 330
Data Structures & Algorithms
Graph Applications
1.
Modeling connectivity in computer and
communications networks
2.
Representing a map as a set of locations with
distances between locations; used to compute shortest
routes between locations
3.
Modeling flow capacities in transportation networks
4.
Finding a path from a starting condition to a goal
condition; for example in artificial intelligence problem
solving
5.
Modeling computer algorithms, showing transitions
from one program state to another
6.
Finding an acceptable order for finishing subtasks in a
complex activity, such as constructing large buildings
7.
Modeling relationships in business, military
organizations, and scientific taxonomies
Graph Notations (1)
o A graph is defined by by two sets: Set of nodes:
vertices and connections: edges
o Trees and lists can be viewed as restricted forms
of graphs graphs are the most general of all
data structures
o 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.
o The number of vertices is written |V|, and the
number edges is written |E|.
o |E| can range between 0 and (|V|2)
Graphs Notations (2)
o A graph with relatively few edges is called
sparse
o A graph with many edges is called dense.
o A graph containing all possible edges is called
complete
o A graph with edges directed from one vertex to
another is a directed graph
o A graph with edges not directed is an undirected
graph
o A graph with labels that are associated with its
edges is called a labeled graph
o A graph with weights assigned to its edges is
said to be weighted
Graphs Notations (3)
o Two vertices are adjacent if they are joined by an edge
(also called neighbors).
o An edge connecting vertices u and v is written (u, v).
This edge is said to be incident on vertices u and v.
o A sequence of vertices v1, v2, …, vn forms a path of
length n-1 if there is an edge from vi to vi+1 for 1i<n.
o A path is simple if all vertices on the path are distinct.
o A cycle is a path of length of 3 or more that connects
some vertex vi to itself.
o A cycle is simple if the path is simple, except for the first
and last vertices (which are the same).
o An undirected graph is connected if there is at least one
path from any vertex to another.
o A graph without cycles is called acyclic
Graphs Examples
Directed graph
Labelled, directed,
weighted graph
There are 2 simple paths
from vertex 0 to vertex 3
Connected Components
The maximum connected subgraphs of an
undirected graph are called connected
components.
Example of a True Graph
In a network, routers connect subnets
together.
A subnet is a smaller network, e.g.,
network of a department in a
company.
AUB’s network for example contains
100 subnets (routers).
Routers are usually connected in an
ad-hoc manner (not like a chain or a
tree) but based on growth over the
years Graph.
The Internet for example is formed of
hundreds of thousands or even
millions of routers.
The function of the router is to forward
network packets from one end to
another end in the network with the
minimum cost (i.e., shortest distance
– subject to bandwidth availability).
router
workstation
server
mobile
Company x
Department y
Company x
Department z
Company x
Department w
Internet Service
Provider
Common Representations
Adjacency matrix is a |V| |V| array
- Row i contains entries for vertex vi
- Column j in row i is marked if there
is an edge from vertx vi to vj and
is not marked otherwise.
- The space requirements is (|V|2)
Adjacency list is an array of linked lists
- Row i contains pointer to list of vertices that
are adjacent to vertex vi
- There is an array entry for every vertex
- If vertx vi has no adjacent vertices, it will
have no elements in its linked list.
- The space requirements is (|V|+|E|)
Undirected Representation
Adjacency list contains overhead
due to the use of pointers
- For a sparse matrix, adjacency list
is more space-efficient
- For a dense matrix, adjacency
matrix is more space-efficient
Graph Implementation Notes
o Vertices are described by an index value
o Graph application stores all additional information about a
given vertex elsewhere.
o A common activity in graph algorithms is to visit edges
extending from a given vertex
o The list of neighbors for a given vertex is sorted by vertex
number
o A graph is built up by using the setEdge function (next
slide)
Graph ADT
class Graph { // Graph abstract class
public:
virtual int n() =0; // # of vertices for whole graph
virtual int e() =0; // # of edges for whole graph
// Return index of first neighbor for a given vertex
virtual int first(int) =0;
// Return index of next neighbor (get vertex1’s neighbor
after // vertex2).
virtual int next(int, int) =0;
// Store new edge, identified by two vertices, 3rd parm is weight
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;
// The mark functions are used for traversal (VISITED or not)
virtual int getMark(int) =0;
virtual void setMark(int, int) =0;
};
Graph Traversals
o
Graph traversal typically begin with a start vertex and
attempt to visit the remaining vertices from there
o
Some applications require visiting every vertex in the
graph exactly once.
o
The application may require that vertices be visited in
some special order based on graph topology.
Issues:
It may not be possible to reach all vertices from the
start vertex (when graph is not connected)
Graph may contain cycles
Solutions:
Using a mark bit
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 mark array
// some times later…
for (v=0; v <G-> n(); v++)
if (G->getMark(v) == UNVISITED)
// doTraverse is implemented using one of many
// well-known algorithms
doTraverse(G, v); // Sets the mark to VISITED
}
Depth First Search
// Depth first search
void DFS(Graph* G, int v) {
// Take action prior to visiting this vertex
PreVisit(G, v);
// Mark vertex v as being visited
G->setMark(v, VISITED);
// Refer to the adjacency matrix, this for loop visits
// all vertices that correspond to entries in the row for v
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
// Don’t process w if it was already visited
if (G->getMark(w) == UNVISITED)
// Process this next node (go deeper into the graph)
// i.e., visit next next … until we reach the end of
// this path (end of this recursion chain). Then go back and visit
// vertices on branches of this path, from the bottom-up.
DFS(G, w);
// When you finish processing all vertices connected to the path from v
// (even via secondary branches), now do a postvisit on v.
PostVisit(G, v);
}
Depth First Search Example
Cost: (|V| + |E|)
A
B
C
D
E
F
A
1
1
B
1
1
C
1
1
1
1
D
1
1
E
1
1
F
1
1
1
1
void DFS(Graph* G, int v) {
PreVisit(G, v);
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);
}
DFS( A): pre(A), A(visited), Row of A: C(not visited)
DFS(C): pre(C), C(visited), Row of C: A(visited), B(not visited)
DFS(B): pre(B), B(visited), Row of B: C(visited), F(not visited)
DFS(F): pre(F), F(visited), Row of F: B(visited), C(visited), D(not visited)
DFS(D): pre(D), D(visited), Row of D: C(visited), F(visited), █
post(D), return from this recursive call (back to row F)
E(not visisted)
DFS(E): pre(E), E(visited), Row of E: A(visited), F(visited), █
post(E), return from this recursive call (back to row F)
█ post(F), return from this recursive call (back to row B)
█ post(B), return from this recursive call (back to row C)
D(visited), F(visited), █ post(C), return from this recursive call (back to row A)
E(visited), █ post(A), return from this recursive call
(End of Function)
Breadth First Search
– Visit vertex’s neighbors before continuing
deeper in the graph.
– Uses a Queue to process vertices
void BFS(Graph* G, int start, Queue<int>*Q) {
int v, w;
Q->enqueue(start); //Initialize Q with starting vertex
G->setMark(start, VISITED); //Mark this vertex visited
while (Q->length() != 0) {
// process the vertex at the front of the queue
Q->dequeue(v);
PreVisit(G, v); // Take pre action
// for all vertices corresponding to entries in the row of v
// in the adjancency matrix of G
for(w=G->first(v);w<G->n();w=G->next(v,w))
if (G->getMark(w) == UNVISITED) {
G->setMark(w, VISITED); //Mark this vertex visited
Q->enqueue(w);// Insert into Queue
}
PostVisit(G, v); // Take post action on v (not on the w’s)
}
}
Cost: |E|
Breadth First Search Example
void BFS(Graph* G, int start, Queue<int>*Q) {
int v, w;
Q->enqueue(start);
G->setMark(start, VISITED);
while (Q->length() != 0) {
Q->dequeue(v);
PreVisit(G, v);
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);
}
PostVisit(G, v);
}
}
A
B
C
D
E
F
A
1
1
B
1
1
C
1
1
1
1
D
1
1
E
1
1
F
1
1
1
1
BFS(A):
Q=[A], A(visited),
Q= [ ], pre(A), Row of A:
C(not visited) C(visited), Q=[C], E(not visited) E(visited), Q=[E,C], post(A)
Q= [E], pre(C), Row of C:
A(visited), B(not visited) B(visited), Q=[B,E], D(not visited) D(visited), Q=[D,B,E],
F(not visited) F(visited), Q=[F,D,B,E], post(C)
Q= [F,D,B], pre(E), Row of E:
A(visited), F(visited), post(E)
Q= [F,D], pre(B), Row of B:
C(visited), F(visited), post(B)
Q= [F], pre(D), Row of D:
C(visited), F(visited), post(D)
Q= [ ], pre(F), Row of F:
B(visited), C(visited), D(visited), E(visited), post(F)
(End of Function)
Topological Sort
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.
Requires a Directed Acyclic Graph (DAG)
- Directed because one task is prerequisite to another
- Acyclic because a cycle would indicate a conflict
The process of laying out the vertices of a DAG in a
linear order to meet prerequisite rules is called a
topological sort.
Topological Sort Implementation
void topsort(Graph* G) { // This particular implementation uses the DFS algorithm
// Topological sort: outputs vertices in reverse order
int i;
for (i=0; i<G->n(); i++) // Initialize vertices to UNVISITED
G->setMark(i, UNVISITED);
// Process vertices: we use a for loop to take care of
// disconnected vertices or sub-graphs
// DFS will visit ALL vertices as long as they are connected
// to the path emanating from the input vertex v
for (i=0; i<G->n(); i++)
if (G->getMark(i) == UNVISITED)
tophelp(G, i); // Call helper function (DFS algorithm)
}
// tophelp implements the DFS algorithm
void tophelp(Graph* G, int v) {
G->setMark(v, VISITED); // note that we took out the pre-visit function
for (int w=G->first(v); w<G->n(); w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
tophelp(G, w);
printout(v); // post-visit for vertex v: executes @ end of each recursion
}
// Now, reverse the order of the outputted vertices
Topological Sort Example – Queue Implementation
J1 J2 J3 J4 J5 J6 J7
J1
1
1
J2
1
1
1
J3
1
J4
1
J5
1
J6
J7
Initially this is the
only vertex that does
not have edges leading
To it (no prerequisites)
After processing J1,
these two vertices do
not have edges leading
To them (no prerequisites)
void topsort(Graph* G, Queue<int>* Q) {
int Count[G->n()];
int v, w;
for (v=0; v<G->n(); v++) Count[v] = 0; // Initialize
for (v=0; v<G->n(); v++) // Process edges
for (w=G->first(v); w<G->n(); w = G->next(v,w))
Count[w]++; // Compute the # edges to each vertex
// e.g., count[J4] is incremented when J2 is processed and when J3 is processed
for (v=0; v<G->n(); v++)
if (Count[v] == 0)
Q->enqueue(v); // Add the vertices that have no prerequisites
while (Q->length() != 0) {
Q->dequeue(v); // Process each vertex in the Q (has no prereq.)
printout(v); // PreVisit for v
// Since we processed v, treat it as if it did not exist decrement count for
// all vertices that are connected to v (i.e., are in the row for v in the matrix)
for (w=G->first(v); w<G->n(); w = G->next(v,w)) {
Count[w]--; // One less prereq for each vertex connected to v
if (Count[w] == 0) // Put each free vertex (no prereq.) in Q
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
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.
Strategy: 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 (a vertex that has
not yet been processed).
Solution: Process vertices in order of distance from
s.
Dijkstra Algorithm
Suppose we have processed in order of distance from s to the
first i-1 vertices that are closest to s. Call this set of vertices S.
We are now about to process the ith closest vertex, call it x.
A shortest path from s to x must have its next-to-last vertex in S.
d(s,x)=min[d(s,u)+w(u,x)], uS
Shortest path from s to x is the minimum over all paths that go
from s to u, and where there is an edge from u to x (u is a vertex
in S).
Note how we only consider the shortest paths
previously established.
Now select the path passing through u1, u2, or
u3 based on the shortest cumulative distance
from s to x.
S
s
x
u1
u2
u3
S
s
x
u1
u2
Shortest
path
Select shortest path to x by considering
shortest paths to vertices that connect directly
to x: u1 and u2.
Now select the shortest path to x based on the
shortest cumulative distance from s to x.
Dijkstra’s Algorithm Example
A
B
C
D
E
3
2
20
5
10
15
11
A
B
C
D
E
3
2
20
5
15
11
A
B
C
D
E
3
2
5
15
11
Consider B
C has a single incoming path
Consider E
A
B
C
D
E
3
15
Considering E
d(A,B)=min[d(A,u)+w(u,B)], u={A, C}
d(A,B)=min[0+10, 3+2]=5 through C
d(A,C)=3
d(A,D)=min[d(A,A)+w(A,D), d(A,B)+w(B,D)]
=min[0+20, 5+5]=10 through B
d(A,E)=min[d(A,D)+w(D,E), d(A,C)+w(C,E)]
=min[10+11, 3+15]=18 through C
Dijkstra’s Implementation (Approach 1)
// Compute shortest path distances from s, return them in D
// Initially, D[0]=0 (source), D[i] = for i>0
void Dijkstra(Graph* G, int* D, int s) {
int i, v, w;
for (i=0; i<G->n(); i++) {
// Among the unvisited vertices, get the one with minimum
// distance from the source.
v = minVertex(G, D);
// Check for disconnected vertex (unreachable)
if (D[v] == INFINITY) return;
// Mark as visited
G->setMark(v, VISITED);
// Go through all the immediate neighbors of v
for (w=G->first(v); w<G->n(); w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
// if not processed earlier, D[w]= while D[v] should be (visited)
if (D[w] > (D[v] + G->weight(v, w)))
// Now D[w]: represents cumulative distance from source
D[w] = D[v] + G->weight(v, w);
}
}
Dijkstra’s Example – step by step
// Initially, D[0]=0 (source), D[i] = for i>0
void Dijkstra(Graph* G, int* D, int s) {
int i, v, w;
for (i=0; i<G->n(); i++) {
v = minVertex(G, D);
if (D[v] == INFINITY) return;
G->setMark(v, VISITED);
// check all the immediate neighbors
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
// if current distance is larger than the distance of last
// neighbor+distance that connects the two, then change
// current distance This is what makes it shortest.
if (D[w] > (D[v] + G->weight(v, w))){
D[w] = D[v] + G->weight(v, w);
Predecessor[w]=v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
// pick the first unvisited vertex
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
// see if there is an unvisited vertex with shorter distance
if ((G->getMark(j) == UNVISITED) &&
(D[j] < D[v]))
v = j;
return v;
}
i=0; minVertex {v=0; D[j>0]= return 0}
V0: visited; consider V1 and V2:
D[1]= > (D[0]+5) D[1]=5
D[2]= > (D[0]+10) D[2]=10
i=1; minVertex {v=1; j=2; D[2]=10, D[v]=5 return 1}
V1: visited; consider V3 and V4:
D[3]= > (D[1]+7)D[3]=5+7=12
D[4]= > (D[1]+9)D[4]=5+9=14
i=2; minVertex {v=2; j=3; D[3]<D[2], D[4]<D[2] return 2}
V2: visited; consider V3 and V4:
D[3]=12 > (D[2]+1) D[3]=D[2]+1=11
D[4]=14 > (D[2]+3) D[4]=D[2]+3=13
i=3; minVertex {v=3; j=4; D[4]<D[3], D[5]<D[3] return 3}
V3: visited; consider V4 and V5:
D[4]=13 > (D[3]+1) D[4]=D[3]+1=11+1=12
D[5]= > (D[3]+3) D[5]=D[3]+3=11+3=14
i=4; minVertex {v=4; j=5; D[5]<D[4] return 3}
V4: visited; consider V5:
D[5]=14 > (D[4]+4)
0
1
2
3
4
10
2
3
7
5
3
1
5
9
1
4
Approach 2 – Using a min-heap
void Dijkstra(Graph* G, int* D, int s) {
int i, v, w; // v is current vertex
DijkElem temp;
DijkElem E[G->e()]; // E is an array of DijkElem elements
temp.distance = 0; // distance from starting element (itself)
temp.vertex = s; // starting vertex
E[0] = temp; // Initialize heap array
// minheap constructor builds the min-heap; we pass it the array and the size
minheap<DijkElem, DDComp> H(E, 1, G->e());
for (i=0; i<G->n(); i++) { // Get distances
// the do-while will keep on looking for unvisited vertices
// It will stop upon encountering the first unvisited vertex
// Initially, all vertices are unvisited
do { if(!H.removemin(temp)) return;
v = temp.vertex;
} while (G->getMark(v) == VISITED);
// From above, v is the first encountered unvisited vertex
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
}
}
}
// class needed by the min-heap
// implementation
Class DijkLelem {
Public:
int vertex, distance;
DijkLelem() {
vertex = -1;
distance = -1;
}
DijkLelem(int v, int d) {
vertex = v;
distance = d;
}
All-Pairs Shortest Paths
o
Path 1-3 is 0-path (no intermediate vertices)
o
Path 3-0-2 is 1-path (vertex 0 with index 0<1)
o
Path 1-3-2 is 4-path (vertex 3 with index 3<4)
o
An m-path is also an (m+1)-path, (m+2)-path, etc.
Example: Path 3-0-2 is also 2-path, 3-path, 4-path,
etc.
From any vertex, we calculate the shortest path to any other vertex
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.
Define Dk(v,u) the length of the shortest k-path from v to u.
Assuming we laready know the shortest k-path from v to u
Shortest (k+1)-path either goes through vertex k or it does not
If it does, best path=best k-path(vk) followed by best k-path(ku). Note that this eliminates
vertex k as an intermediate vertex
If not, keep best k-path seen before
Floyd’s Algorithm
//Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
// for Storing distances
int D[G->n()][G->n()];
// Initialize with the weights (non-existent edges weight=)
for (int i=0; i<G->n(); i++)
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++)
// Check if using intermediate vertices would render shorter distance
// this includes vertices (I,j) that do not have an edge that connects
// them (D[i][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
1.
Start with any vertex N in the graph MST = N
2.
Pick the least-cost edge connected to N (connecting N to M)
a.
Add M and edge (N, M) to the MST
3.
Pick the least-cost edge coming from either N or M to any
other vertex in the graph.
a.
Add this edge and the vertex it reaches to the MST
4.
Continue the above by selecting the least-cost edge from a
vertex currently in the MST to a vertex not currently in the
MST.
Prim’s algorithm is very close to Djikstra’s algorithm with
the following difference:
o
We are seeking not the next closest vertex to the start vertex, but
rather the next closest vertex to any vertex currently in the MST.
Prim’s MST Algorithm Implementation
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
// v[i] stores the previously visited vertex that is closest to vertex i so we know which edge goes
into the MST when vertex i is processed.
int i, w;
for (i=0; i<G->n(); i++) { // for all vertices in G
int v = minVertex(G, D);
G->setMark(v, VISITED);
if (v != s) AddEdgetoMST(V[v], v); // if it is not the starting vertex
if (D[v] == INFINITY) return;
for (w=G->first(v); w<G->n(); w=G->next(v,w))
if (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) { // this is different from Dijkstra’s algorithm
D[w] = G->weight(v,w); // Update distance
V[w] = v; // Update who it came from
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
// pick the first unvisited vertex
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
// see if there is an unvisited vertex with shorter distance
if ((G->getMark(j) == UNVISITED) && (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (0)
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
i=0,
minVertexD{v=0}
0: visited,
D[1]=9, V[1]=0
D[3]=7, V[3]=0
D[4]=4, V[4]=0
D[0]=0, V[0]=0
D[1]=, V[1]=
D[2]=, V[2]=
D[3]=, V[3]=
D[4]=, V[4]=
D[5]=, V[5]=
D[6]=, V[6]=
D[7]=, V[7]=
D[8]=, V[8]=
Visited: {}
Prim’s MST Algorithm Example (1)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=9, V[1]=0
D[2]=, V[2]=
D[3]=7, V[3]=0
D[4]=4, V[4]=0
D[5]= , V[5]=
D[6]=, V[6]=
D[7]= , V[7]=
D[8]= , V[8]=
Visited: {0}
i=1,
minVertexD{v=1, D[2]=>D[1],
D[3]<D[1]v=3, D[4]<D[3]v=4}
4: visited, Add(V[4], 4),
Neighbors of 4:
(0 was visited)
D[3]>5D[3]=5, V[3]=4
D[8]>6 D[8]=6, V[8]=4
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (2)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=9, V[1]=0
D[2]=, V[2]=
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=, V[5]=
D[6]=, V[6]=
D[7]=, V[7]=
D[8]=6, V[8]=4
Visited: {0, 4}
i=2,
minVertexD{v=1, D[2]=>D[1],
D[3]<D[1]v=3, D[5]>D[3],
D[6]>D[3], D[7]>D[3], D[8]>D[3]}
3: visited, Add(V[3], 3),
Neighbors of 3:
(0 and 4 were visited)
D[2]>1D[2]=1, V[2]=3
D[7]>3 D[7]=3, V[7]=3
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (3)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=9, V[1]=0
D[2]=1, V[2]=3
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=, V[5]=
D[6]=, V[6]=
D[7]=3, V[7]=3
D[8]=6, V[8]=4
Visited: {0,3,4}
i=3,
minVertexD{v=1, D[2]<D[1]v=2,
D[5]>D[2],D[6]>D[2],D[7]>D[2], D[8]>D[2]}
2: visited, Add(V[2], 2),
Neighbors of 2:
(3 was visited)
D[1]>8D[1]=8, V[1]=2
D[6]>2 D[6]=2, V[6]=2
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (4)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=8, V[1]=2
D[2]=1, V[2]=3
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=, V[5]=
D[6]=2, V[6]=2
D[7]=3, V[7]=3
D[8]=6, V[8]=4
Visited: {0,2,3,4}
i=4,
minVertexD{v=1, D[5]>D[1],D[6]<D[1]v=6
D[7]>D[6], D[8]>D[6]}
6: visited, Add(V[6], 6),
Neighbors of 6:
(2 was visited)
D[5]>7D[5]=7, V[5]=6
D[8]>3D[8]=3, V[8]=6
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (5)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=8, V[1]=2
D[2]=1, V[2]=3
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=7, V[5]=6
D[6]=2, V[6]=2
D[7]=3, V[7]=3
D[8]=3, V[8]=6
Visited: {0,2,3,4,6}
i=5,
minVertexD{v=1, D[5]<D[1]v=5
D[7]<D[5]v=7, D[8]=D[7]}
7:visited, Add(V[7], 7),
Neighbors of 7:
(3 was visited)
D[8]<4
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (6)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=8, V[1]=2
D[2]=1, V[2]=3
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=7, V[5]=6
D[6]=2, V[6]=2
D[7]=3, V[7]=3
D[8]=3, V[8]=6
Visited: {0,2,3,4,6,7}
i=6,
minVertexD{v=1, D[5]<D[1]v=5
D[8]<D[5]v=8}
8:visited, Add(V[8], 8),
Neighbors of 8:
(4,6,7 were visited)
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (7)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=8, V[1]=2
D[2]=1, V[2]=3
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=7, V[5]=6
D[6]=2, V[6]=2
D[7]=3, V[7]=3
D[8]=3, V[8]=6
Visited: {0,2,3,4,6,7,8}
i=7,
minVertexD{v=1, D[5]<D[1]v=5}
5:visited, Add(V[5], 5),
Neighbors of 5:
(6 was visited)
D[1]>6 D[1]=6, V[1]=5
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, int* D) {
int j, v;
for (j=0; j<G->n(); j++)
if (G->getMark(j) == UNVISITED)
{ v = j; break; }
for (j++; j<G->n(); j++)
if ((G->getMark(j) == UNVISITED)
&& (D[j] < D[v]))
v = j;
return v;
}
Prim’s MST Algorithm Example (8)
0
3
2
7
6
9
1
5
3
7
2
3
8
4
4
4
1
5
6
7
6
8
D[0]=0, V[0]=0
D[1]=6, V[1]=5
D[2]=1, V[2]=3
D[3]=5, V[3]=4
D[4]=4, V[4]=0
D[5]=7, V[5]=6
D[6]=2, V[6]=2
D[7]=3, V[7]=3
D[8]=3, V[8]=6
Visited: {0,2,3,4,5,6,7,8}
i=8,
minVertexD{v=1}
1:visited, Add(V[1], 1),
Neighbors of 1:
(0,2,5 were visited)
void Prim(Graph* G, int* D, int s) {
int V[G->n()];
int i, w;
for (i=0; i<G->n(); i++) {
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 (G->getMark(w) == UNVISITED)
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);
V[w] = v;
}
}
}
int minVertex(Graph* G, in