Activity of Algorithms

1. Prim's Algorithm
A. Algorithm Description

Objective: Find the Minimum Spanning Tree (MST) of a connected, weighted graph.

Steps:

1. Initialize:
o Choose an arbitrary starting vertex.
o Set the MST set initially containing only that vertex.
o Mark all vertices as not included in the MST.
2. Loop:
o Select the edge with the smallest weight that connects a vertex in the MST with a
vertex outside the MST.
o Add the selected edge and the vertex to the MST set.
3. Repeat:
o Continue until all vertices are included in the MST.
4. Termination:
o The MST will contain (V-1) edges (where V is the number of vertices).

B. Flowchart

Below is an ASCII representation of the flowchart for Prim's algorithm:

pgsql
CopyEdit
+-----------------------+
| Start |
+-----------------------+
|
v
+-----------------------+
| Choose starting vertex|
+-----------------------+
|
v
+-----------------------+
| Initialize MST = {} |
| Mark starting vertex |
+-----------------------+
|
v
+------------------------------+
 | Is all vertex in MST? |
+------------------------------+
/ \
No/ \Yes
/ \
v v
+-----------------+ +--------------+
| Select the edge | | End |
| with minimum | | (MST complete)|
| weight connecting| +--------------+
| MST and non-MST |
+-----------------+
|
v
+---------------------------+
| Add edge and vertex to MST|
+---------------------------+
|
v
(Loop back to check if all vertices are in MST)

C. Python Implementation
python
CopyEdit
import heapq
import networkx as nx
import matplotlib.pyplot as plt

def prim_mst(graph):
# Arbitrary starting node (pick the first node)
start = list(graph.nodes)[0]
mst_edges = []
visited = {start}
# Priority queue: edges are (weight, vertex_u, vertex_v)
edges = [(weight, start, to) for to, weight in graph[start].items()]
heapq.heapify(edges)

while edges and len(visited) < len(graph.nodes):

weight, u, v = heapq.heappop(edges)
if v not in visited:
visited.add(v)
mst_edges.append((u, v, weight))
for to, wt in graph[v].items():
if to not in visited:
heapq.heappush(edges, (wt, v, to))
return mst_edges

# Sample Graph (Undirected Weighted Graph)

G = nx.Graph()
edges = [
('A', 'B', 6), ('A', 'F', 2), ('A', 'E', 1), ('A', 'D', 4), ('A', 'C', 6),
('B', 'C', 2), ('B', 'E', 4),
('C', 'D', 1), ('C', 'F', 5),
('D', 'E', 7),
('E', 'F', 4)
]
G.add_weighted_edges_from(edges)

# Compute MST using Prim's Algorithm

mst_prim = prim_mst(G)
print("Prim's Algorithm MST:")
for u, v, weight in mst_prim:
print(f"{u} - {v}: {weight}")

# Plotting the result

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue')
nx.draw_networkx_edge_labels(G, pos, edge_labels=nx.get_edge_attributes(G,
'weight'))
# Highlight MST edges:
mst_edges_set = [(u, v) for u, v, _ in mst_prim]
nx.draw_networkx_edges(G, pos, edgelist=mst_edges_set, width=2.5,
edge_color='red')
plt.title("Prim's Algorithm - MST")
plt.show()

D. Example & Output Explanation (Prim's Algorithm)

For the sample graph:

 Vertices: A, B, C, D, E, F
 Edges: (A,B=6), (A,F=2), (A,E=1), etc.

Output Explanation: The algorithm starts at vertex A and always selects the smallest edge that
connects the current MST set with a vertex not in MST. Suppose it picks A-E (weight 1), then A-
F (weight 2), then from F adds edge F-C (weight 5) or from E adds B-E (4) depending on the
available minimum weights. The final MST will contain 5 edges connecting all vertices. The
output printed in the console and the red-highlighted edges in the plotted graph represent the
MST.

2. Kruskal's Algorithm
A. Algorithm Description

Objective: Find the Minimum Spanning Tree (MST) for a connected, weighted graph.

Steps:

1. Initialize:
o Create a list of all edges and sort them in non-decreasing order of their weight.
o Initialize a disjoint-set data structure for cycle detection.
2. Loop through Sorted Edges:
 oFor each edge, check if adding it creates a cycle using the disjoint-set.
oIf it does not create a cycle, add the edge to the MST.
3. Termination:
o Stop when the MST contains (V - 1) edges.

B. Flowchart

Here is the ASCII flowchart for Kruskal's algorithm:

pgsql
CopyEdit
+-------------------------+
| Start |
+-------------------------+
|
v
+-------------------------+
| Sort all edges by weight|
+-------------------------+
|
v
+-------------------------+
| Initialize Disjoint Set |
+-------------------------+
|
v
+-------------------------+
| For each edge in sorted |
| list: |
+-------------------------+
|
v
+-------------------------+
| Check if edge creates |
| cycle (using DSU) |
+-------------------------+
|
+-----+-----+
| |
No| |Yes
| v
| +-----------------+
| | Skip this edge |
| +-----------------+
| |
+-----+-----+
|
v
+-------------------------+
| Add edge to MST and DSU |
+-------------------------+
|
v
+-------------------------+
 | MST complete? (edges==V-1)|
+-------------------------+
|
+--------+--------+
| |
Yes No
| |
v v
+------+ (Loop back)
| End |
+------+

C. Python Implementation
python
CopyEdit
# Python implementation for Kruskal's Algorithm using a Disjoint Set (Union-
Find).
class UnionFind:
def __init__(self, elements):
self.parent = {e: e for e in elements}
self.rank = {e: 0 for e in elements}

def find(self, element):

if self.parent[element] != element:
self.parent[element] = self.find(self.parent[element])
return self.parent[element]

def union(self, a, b):

rootA = self.find(a)
rootB = self.find(b)
if rootA == rootB:
return False # They are already in the same set
if self.rank[rootA] < self.rank[rootB]:
self.parent[rootA] = rootB
elif self.rank[rootA] > self.rank[rootB]:
self.parent[rootB] = rootA
else:
self.parent[rootB] = rootA
self.rank[rootA] += 1
return True

def kruskal_mst(graph):
# Extract unique edges (for undirected graph) and sort them.
edges = []
seen = set()
for u in graph:
for v, weight in graph[u].items():
edge = tuple(sorted([u,v]))
if edge not in seen:
seen.add(edge)
edges.append((u, v, weight))
edges.sort(key=lambda x: x[2])

# Initialize disjoint sets

uf = UnionFind(list(graph.keys()))
 mst_edges = []

for u, v, weight in edges:

if uf.union(u, v):
mst_edges.append((u, v, weight))
if len(mst_edges) == len(graph) - 1:
break
return mst_edges

# Using the same sample graph as in Prim's algorithm:

graph_adj = {
'A': {'B': 6, 'F': 2, 'E': 1, 'D': 4, 'C': 6},
'B': {'A': 6, 'C': 2, 'E': 4},
'C': {'A': 6, 'B': 2, 'D': 1, 'F': 5},
'D': {'A': 4, 'C': 1, 'E': 7},
'E': {'A': 1, 'B': 4, 'D': 7, 'F': 4},
'F': {'A': 2, 'C': 5, 'E': 4}
}

# Compute MST using Kruskal's Algorithm

mst_kruskal = kruskal_mst(graph_adj)
print("Kruskal's Algorithm MST:")
for u, v, weight in mst_kruskal:
print(f"{u} - {v}: {weight}")

# (Visualization can be done similarly using NetworkX as in Prim's.)

D. Example & Output Explanation (Kruskal's Algorithm)

For the sample graph:

 The algorithm starts by sorting all edges.

 It then iteratively adds the smallest edges that do not create a cycle.
 The printed output shows the list of edges (with weights) that form the MST.
 In our sample graph, 5 edges (for 6 vertices) are selected, and the output confirms these
are the minimal required connections.

3. Dijkstra's Algorithm
A. Algorithm Description

Objective: Find the shortest path from a source vertex to all other vertices in a weighted graph
with non-negative edge weights.

Steps:

1. Initialize:
o Set the distance to the source vertex as 0 and to all others as infinity.
 o Create a priority queue (min-heap) to store vertices by their current distance.
2. Loop:
o Extract the vertex with the minimum distance from the priority queue.
o For each neighbor of this vertex, calculate the new distance through the current
vertex.
o If the new distance is lower, update the distance and add the neighbor to the
priority queue.
3. Termination:
o Repeat until the priority queue is empty.
4. Result:
o The algorithm outputs the shortest distances from the source to every vertex.

B. Flowchart

ASCII Flowchart for Dijkstra's algorithm:

pgsql
CopyEdit
+-----------------------+
| Start |
+-----------------------+
|
v
+-----------------------+
| Initialize distances: |
| source = 0, others = ∞ |
+-----------------------+
|
v
+-----------------------+
| Insert source in PQ |
+-----------------------+
|
v
+-----------------------+
| While PQ is not empty |
+-----------------------+
|
v
+-----------------------+
| Extract vertex u with |
| min distance |
+-----------------------+
|
v
+------------------------------+
| For each neighbor v of u: |
| if distance[u] + weight < |
| distance[v] then update |
| distance[v] and add v to PQ|
+------------------------------+
|
v
 +-----------------------+
| End While Loop |
+-----------------------+
|
v
+-----------------------+
| End |
+-----------------------+

C. Python Implementation
python
CopyEdit
import heapq

def dijkstra_shortest_paths(graph, source):

# Initialize distances dictionary. All distances are "infinity", except
source.
distances = {node: float('inf') for node in graph}
distances[source] = 0
# Priority queue stores tuples (distance, node)
pq = [(0, source)]

while pq:
current_distance, u = heapq.heappop(pq)
# If the distance is outdated in the queue, skip it.
if current_distance > distances[u]:
continue
for v, weight in graph[u].items():
distance_through_u = current_distance + weight
if distance_through_u < distances[v]:
distances[v] = distance_through_u
heapq.heappush(pq, (distance_through_u, v))
return distances

# Using the same graph as defined for Kruskal:

graph_adj = {
'A': {'B': 6, 'F': 2, 'E': 1, 'D': 4, 'C': 6},
'B': {'A': 6, 'C': 2, 'E': 4},
'C': {'A': 6, 'B': 2, 'D': 1, 'F': 5},
'D': {'A': 4, 'C': 1, 'E': 7},
'E': {'A': 1, 'B': 4, 'D': 7, 'F': 4},
'F': {'A': 2, 'C': 5, 'E': 4}
}

# Compute shortest paths from source vertex 'A'

source_vertex = 'A'
shortest_paths = dijkstra_shortest_paths(graph_adj, source_vertex)
print(f"Shortest paths from {source_vertex}:")
for vertex, distance in shortest_paths.items():
print(f"Distance to {vertex}: {distance}")

D. Example & Output Explanation (Dijkstra's Algorithm)

For the sample graph:

  Source: Vertex A
 The algorithm initializes all distances and uses a min-heap to extract the vertex with the
least current distance.
 It updates the distances for neighbors when a shorter path is found.
 Output: The final printed distances show the shortest path cost from A to every other
vertex.
o For instance, if vertex E is directly connected to A by an edge of weight 1, then
the output lists Distance to E = 1.
o Other vertices are updated accordingly as the algorithm proceeds.

4. Conclusion
This report illustrates the three important graph algorithms:

 Prim's Algorithm builds an MST by expanding a tree from a starting vertex.

 Kruskal's Algorithm constructs an MST by considering the edges in order of weight and
using disjoint sets to avoid cycles.
 Dijkstra's Algorithm efficiently computes the shortest paths from a single source to all
other vertices using a priority queue.