Scribd
Upload
4 views9 pages

aipr8ka

The document contains three practical implementations of graph algorithms: Depth First Search (DFS) and Breadth First Search (BFS) for traversing graphs, A* algorithm for pathfinding, and Prim's and Kruskal's algorithms for finding Minimum Spanning Trees (MST). Each section includes function definitions, example graphs, and user input for starting points or algorithm choices. The implementations demonstrate fundamental concepts in graph theory and algorithm design.

Uploaded by

Sabhya Lokhande
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views9 pages

aipr8ka

The document contains three practical implementations of graph algorithms: Depth First Search (DFS) and Breadth First Search (BFS) for traversing graphs, A* algorithm for pathfinding, and Prim's and Kruskal's algorithms for finding Minimum Spanning Trees (MST). Each section includes function definitions, example graphs, and user input for starting points or algorithm choices. The implementations demonstrate fundamental concepts in graph theory and algorithm design.

Uploaded by

Sabhya Lokhande
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

Practical - 8

from collections import deque


def dfs(graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
def main():
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
start_vertex = input("\nEnter the starting vertex: ").strip().upper()
print("\nDepth First Search starting from vertex '{}':".format(start_vertex))
dfs(graph, start_vertex)
print("\nBreadth First Search starting from vertex '{}':".format(start_vertex))
bfs(graph, start_vertex)
print("\n")

if __name__ == "__main__":
main()
Practical - 9

import heapq

class Node:
def __init__(self, state, parent=None, g=0, h=0):
self.state = state
self.parent = parent
self.g = g # Cost from start to this node
self.h = h # Heuristic cost estimate to goal
self.f = g + h # Total cost (f = g + h)

def __lt__(self, other):


return self.f < other.f

def a_star(start, goal, get_neighbors, heuristic):


open_set = []
closed_set = set()

start_node = Node(state=start, g=0, h=heuristic(start, goal))


heapq.heappush(open_set, start_node)

while open_set:
current_node = heapq.heappop(open_set)

if current_node.state == goal:
path = []
while current_node:
path.append(current_node.state)
current_node = current_node.parent
return path[::-1] # Return reversed path

closed_set.add(current_node.state)

for neighbor, cost in get_neighbors(current_node.state):


if neighbor in closed_set:
continue
g_cost = current_node.g + cost
h_cost = heuristic(neighbor, goal)
neighbor_node = Node(state=neighbor, parent=current_node, g=g_cost,
h=h_cost)

if all(neighbor_node.f < node.f for node in open_set if node.state == neighbor):


heapq.heappush(open_set, neighbor_node)

return None
def heuristic(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])

def get_neighbors(state):
x, y = state
neighbors = []
for dx, dy, cost in [(-1, 0, 1), (1, 0, 1), (0, -1, 1), (0, 1, 1)]:
nx, ny = x + dx, y + dy
neighbors.append(((nx, ny), cost))
return neighbors

start = (0, 0)
goal = (3, 3)
path = a_star(start, goal, get_neighbors, heuristic)

if path:
print("Path found:", path)
else:
print("No path found")
Practical - 12

import sys

class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n

def find(self, u):


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

def union(self, u, v):


root_u = self.find(u)
root_v = self.find(v)

if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1

def prim_mst(graph):
num_vertices = len(graph)
key = [sys.maxsize] * num_vertices # Initialize keys as infinite
parent = [None] * num_vertices # Array to store constructed MST
mst_set = [False] * num_vertices # To track vertices included in MST

key[0] = 0 # Start from the first vertex


parent[0] = -1 # First node is the root of the MST

for _ in range(num_vertices):
# Find the vertex with the minimum key value that is not yet included in the MST
min_key = sys.maxsize
min_index = -1
for v in range(num_vertices):
if not mst_set[v] and key[v] < min_key:
min_key = key[v]
min_index = v

u = min_index
mst_set[u] = True # Add the vertex to the MST

# Update key values and parent index of the adjacent vertices of the picked vertex
for v in range(num_vertices):
if graph[u][v] and not mst_set[v] and graph[u][v] < key[v]:
key[v] = graph[u][v]
parent[v] = u

# Print the constructed MST


print("Prim's Algorithm MST:")
print("Edge \tWeight")
for i in range(1, num_vertices):
print(f"{parent[i]} - {i} \t{graph[i][parent[i]]}")

def kruskal_mst(vertices, edges):


# Sort edges by weight
edges.sort(key=lambda x: x[2])

ds = DisjointSet(vertices)

mst = []
mst_weight = 0

for u, v, weight in edges:


if ds.find(u) != ds.find(v):
ds.union(u, v)
mst.append((u, v, weight))
mst_weight += weight

# Print the constructed MST


print("Kruskal's Algorithm MST:")
print("Edge \tWeight")
for u, v, weight in mst:
print(f"{u} - {v} \t{weight}")
print(f"Total weight of MST: {mst_weight}")

def main():
print("Select the algorithm:")
print("1. Prim's Algorithm")
print("2. Kruskal's Algorithm")
choice = input("Enter your choice (1 or 2): ").strip()

if choice == '1':
graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
prim_mst(graph)
elif choice == '2':
vertices = 5
edges = [
(0, 1, 2),
(1, 2, 3),
(2, 4, 7),
(4, 3, 9),
(0, 3, 6),
(1, 4, 5)
]
kruskal_mst(vertices, edges)
else:
print("Invalid choice!")

if __name__ == "__main__":
main()

You might also like