UNIVERSITY OF ENGINEERING AND TECHNOLOGY,
TAXILA
COURSE: DSA
INSTRUCTOR: Dr.Naveed
SUBMITTED BY: Ahmad Haseeb
Roll NO: 23-CP-42
Examples Tasks:
graph = {
'A' : ['B','C'],
'B': ['A','D','E'],
'C' : ['B','B'],
'E' : ['C','Z']
}
for i in graph:
print(f"{i}-> {graph[i]}")
OUTPUT:
Examples Tasks (Represent
a Graph using Adjacency
Matrix):
graph = {
'A' : ['B','C'],
'B': ['A','D','E'],
'C' : ['B','B'],
'E' : ['C','Z']
}
for i in graph:
print(f"{i}-> {graph[i]}")
My Approach to Create a
Graph and then its Traversal
Technique:
class Graph:
def __init__(self):
self.adjacent_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacent_list:
self.adjacent_list[vertex] = []
def add_edge(self, v1, v2):
self.add_vertex(v1)
self.add_vertex(v2)
self.adjacent_list[v1].append(v2)
self.adjacent_list[v2].append(v1)
def display(self):
for i in self.adjacent_list:
print(i, "->", self.adjacent_list[i])
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "E")
g.add_edge("D", "E")
g.add_edge("F","T")
g.display()
OUTPUT:
Breadth First Traversal
Technique:
from collections import deque
def bfs(graph, start):
visited = set() # to track visited nodes
queue = deque([start]) # queue with starting node
print("BFS Traversal:")
while queue:
vertex = queue.popleft() # remove from front of queue
if vertex not in visited:
print(vertex, end=" ") # process the node
visited.add(vertex) # mark as visited
for neighbor in graph[vertex]: # add neighbors
if neighbor not in visited:
queue.append(neighbor)
bfs(g.adjacent_list, 'A')
OUTPUT:
Easy Tasks in One Code:
from collections import deque, defaultdict
class Graph:
def __init__(self):
self.adj_list = defaultdict(list)
def add_edge(self, v1, v2):
self.adj_list[v1].append(v2)
self.adj_list[v2].append(v1)
def display(self):
print("\nGraph Adjacency List:")
for node in self.adj_list:
print(f"{node} -> {self.adj_list[node]}")
def detect_self_loops(self):
print("\nChecking for Self-Loops:")
for node in self.adj_list:
if node in self.adj_list[node]:
print(f"Self-loop found at node: {node}")
def bfs_with_levels(self, start):
visited = set()
level_map = defaultdict(list)
queue = deque([(start, 0)])
while queue:
node, level = queue.popleft()
if node not in visited:
visited.add(node)
level_map[level].append(node)
for neighbor in self.adj_list[node]:
if neighbor not in visited:
queue.append((neighbor, level + 1))
return dict(level_map)
g = Graph()
num_vertices = int(input("Enter number of vertices: "))
num_edges = int(input("Enter number of edges: "))
print("Enter edges in the format 'u v':")
for _ in range(num_edges):
u, v = input().split()
g.add_edge(u, v)
g.display()
g.detect_self_loops()
start_node = input("\nEnter the starting node for BFS: ")
bfs_result = g.bfs_with_levels(start_node)
print("\nBFS Level-Wise Traversal:")
for level in bfs_result:
print(f"Level {level}: {bfs_result[level]}")
OUTPUT:
Intermediate Problem:
import matplotlib.pyplot as plt
import networkx as nx
from collections import defaultdict
class Graph:
def __init__(self):
self.adj_list = defaultdict(list)
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def dfs_path(self, start):
visited = set()
path = []
def dfs(node):
visited.add(node)
path.append(node)
for neighbor in self.adj_list[node]:
if neighbor not in visited:
dfs(neighbor)
dfs(start)
return path
def visualize_dfs(self, start):
path = self.dfs_path(start)
G = nx.Graph()
for u in self.adj_list:
for v in self.adj_list[u]:
G.add_edge(u, v)
pos = nx.spring_layout(G, seed=42)
edge_colors = []
for u, v in G.edges():
if u in path and v in path:
i, j = path.index(u), path.index(v)
if abs(i - j) == 1:
edge_colors.append('red')
else:
edge_colors.append('gray')
else:
edge_colors.append('gray')
nx.draw(G, pos, with_labels=True, node_color='skyblue',
edge_color=edge_colors, width=2)
plt.title("DFS Traversal Path Highlighted in Red")
plt.show()
def to_adjacency_matrix(self):
nodes = list(self.adj_list.keys())
n = len(nodes)
matrix = [[0]*n for _ in range(n)]
idx = {node: i for i, node in enumerate(nodes)}
for u in self.adj_list:
for v in self.adj_list[u]:
i, j = idx[u], idx[v]
matrix[i][j] = 1
matrix[j][i] = 1
return nodes, matrix
def detect_cycle(self):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in self.adj_list[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for node in self.adj_list:
if node not in visited:
if dfs(node, None):
return True
return False
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "E")
g.add_edge("E", "F")
g.add_edge("F", "C") # This introduces a cycle
# DFS Path Visualization
g.visualize_dfs("A")
# Adjacency Matrix Conversion
nodes, matrix = g.to_adjacency_matrix()
print("\nAdjacency Matrix:")
print(" " + " ".join(nodes))
for i, row in enumerate(matrix):
print(nodes[i], row)
# Cycle Detection
if g.detect_cycle():
print("\nCycle Detected in the Graph")
else:
