Graph Algorithms
Topics
• Graph terminology
• Graph Representations
• Matrix Representation
• Linked list Representation
• Graph Traversal
• Breath First Search (BFS)
• Depth First Search (DFS)
• Spanning Trees
• Kruskal’s algorithm and analysis
• Prim’s algorithm
• Single shortest distance
• Dijkstra’s algorithm
Spanning Trees
Definition
• A spanning tree for an undirected graph is a sub-graph which includes all vertices but has no
cycles.
• There can be several spanning trees for a graph. Figure shows some of the trees for the graph
with vertices v1,v2,v3,v4
• Each tree has same number of edges
• Spanning trees can be generated by depth-first–search and breadth-first-search procedures.
Minimum Spanning Trees
• A weighted undirected graph can have several spanning trees.
• One of the spanning trees has smallest sum of all the weights associated with the edges. This
tree is called minimum spanning tree.
• Figure shows a sample weighted graph, some of the spanning trees, and the minimum
spanning tree.
Minimum Spanning Trees
Minimum spanning trees have many practical applications. Some typical applications are:
• A telephone network can be configured, using minimum spanning tree, to have minimum cable
length.
• The air travel routes can be selected so that the travel time or travel cost is least.
• A computer network can be set up with minimum routing distance
• Linking a group of island with bridges so that total bridge span length is minimum
Two important algorithms for creating a minimum spanning tree for a graph, named after their
inventors, are Kruskal’s algorithm and Prim’s algorithm.
Greedy Algorithms for MST
Kruskal’s Algorithm
The algorithm works as follows:
Step #1: Remove all edges of the graph
Step #2: Arrange edges according to their weights
Step #3: Select a edge with least weight
Step #4: Attach the edge to the corresponding vertices if it does nor form cycle; otherwise, drop
the edge
Step #5: Repeat steps 3 to 4 until all the edges are processed (added or dropped)
For the Kruskal’s algorithm generally a priority queue is used to store graph edges, so that
edges are retrieved in increasing order.
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Edges are stored into a priority queue. The priorities are weights, so that the smallest
weight is extracted first.
Kruskal’s Algorithm – Example
Edge EF is extracted. It is added to the spanning tree .
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
Kruskal’s Algorithm – Example
The minimum spanning tree is generated. The minimum distance is 182. The tree includes
all the vertices.
Prim’s Algorithm
Unlike the Kruskal’s algorithm, the Prim’s algorithm makes a systematic selection of vertices. It
proceeds by choosing a vertex, which is at shortest distance of all the linked vertices.
Let V be the vertex set for a graph G. Prim’s algorithm proceeds as follows:
Step #1: Select some vertex s in V, as the starting vertex.
Step #2: Add vertex s to an empty set S. Remove s from V.
Step #3: Repeat Step #4 through Step #6 until the set V is empty.
Step #4: Examine all vertices in S which are linked to vertices in V.
Step #5: Choose the vertex u in V which has the minimum distance from vertex v in S.
Step #6: Remove vertex u from V and add it to S. Move edge (v ,u) to T.
Prim’s Algorithm
A sample weighted graph with vertex set V= {A,B, C, D, E, F, G, H, I, J} is used to demonstrate
Prim’s algorithm for creating a Minimum Spanning Tree.
Prim’s Algorithm
Initially, the set V contains all of the graph vertices. Another set S holds the processed vertices.
First, vertex A is chosen. It is deleted from V and placed in set S. A is marked as selected, and
shown in pink color.
Prim’s Algorithm
All vertices in set V, which are linked to the vertices in set S, are examined. The vertex which
has the shortest distance is selected, and placed in set S. The selected vertices form path of the
Minimum Spanning Tree. Vertices B, I, J in set V are linked to vertex A in set S, and have
distances 10, 30, 28 respectively. Since B has minimum distance 10, it is selected.
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Dijkstra’s Algorithm
The algorithm for single-source shortest paths determines the smallest routes of all vertices in a
graph from a given vertex, called source vertex.
Dijkstra’s Algorithm
The working of Dijkstra’s algorithm is similar to Prim’s algorithm. It repeatedly computes the
distances between a source vertex and the vertices being explored, and selects the minimum
distance from among the feasible paths.
Let V be the vertex set for a graph G. Let d be an array that stores shortest distances. The
algorithm proceeds as follows:
Step #1: Add source vertex s to an empty set S. Remove s from V.
Step #2: Repeat Step #3 and Step #4 until the set V is empty.
Step #3: Examine vertices in S which are linked to vertices in V. Choose the vertex u in V which
has the shortest distance from the source. Store this distance in d[u]
Step #4: Remove vertex u from V and add it to S.
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Dijkstra’s Algorithm