KCCINSTITUTEOFTECHNOLOGYANDMANAGEMENT

2B,2C,VashishthRd,KnowledgeParkIII,GreaterNoida,UttarPradesh201306

DepartmentofComputerScienc
e & Engineering

DESIGN AND ANALYSIS OF

ALGORITHMSLAB FILE
BCS-553

[Link].CSE3rdYear(5thSem)

Academic Session 2025-26

Submitted By: SubmittedTo:

Student Name: Satyam Shukla Dr. Mohd Sadim
Branch: AI&ML (Professor , CSE Deptt.)

Roll Number: 2304921640105

 List of Experiments
Exp. Experiment Name Date Signature
No.
1. Program for Recursive Binary & Linear Search. 12/09/2025

2. Program for Heap Sort. 12/09/2025

3. Program for Merge Sort. 19/09/2025

4. Program for Selection Sort. 19/09/2025

5. Program for Insertion Sort. 26/09/2025

6. Program for Quick Sort. 26/09/2025

7. Knapsack Problem using Greedy Solution 10/10/2025

8. Perform Travelling Salesman Problem 10/10/2025

9. Find Minimum Spanning Tree using Kruskal’s 17/10/2025

Algorithm
10. Implement N Queen Problem using Backtracking 17/10/2025

11. Sort a given set of n integer elements using 31/10/2025

Quick Sort method and compute its time
complexity. Run the program for varied values of
n> 5000 and record the time taken to sort. Plot a
graph of the time taken versus non graph sheet.
The elements can be read from a file or can be
generated using the random number generator.
Demonstrate using Java how the divide and-
conquer method works along with its time
complexity analysis: worst case, average case
and best case.
12. Sort a given set of n integer elements using 31/10/2025
Merge Sort method and compute its time
complexity. Run the program for varied values of
n> 5000, and record the time taken to sort. Plot a
graph of the time taken versus non graph sheet.
The elements can be read from a file or can be
 generated using the random number generator.
Demonstrate how the divide andconquer method
works along with its time complexity analysis:
worst case, average case and best case.
13. Implement, the 0/1 Knapsack problem using; 07/11/2025
(a). Dynamic Programming method
(b). Greedy method.
14. From a given vertex in a weighted connected 07/11/2025
graph, find shortest paths to other vertices using
Dijkstra's algorithm.
15. Find Minimum Cost Spanning Tree of a given 14/11/2025
connected undirected graph using Kruskal's
algorithm. Use Union-Find algorithms in your
program.
16. Find Minimum Cost Spanning Tree of a given 14/11/2025
undirected graph using Prim’s algorithm.
17. Write programs to; 21/11/2025
(a) Implement All-Pairs Shortest Paths problem
using Floyd's algorithm.
(b) Implement Travelling Sales Person problem
using Dynamic programming.
18. Design and implement to find a subset of a given 21/11/2025
set S = {Sl, S2,. ....,Sn} of n positive integers
whose SUM is equal to a given positive integer
d. For example, if S ={1, 2, 5, 6, 8} and d= 9,
there are two solutions {1,2,6}and {1,8}. Display
a suitable message, if the given problem instance
doesn't have a solution.
19. Design and implement to find all Hamiltonian 28/11/2025
Cycles in a connected undirected Graph G of n
vertices using backtracking principle.
 Problem #1
Q. Program for Recursive Binary & Linear Search.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

def binary_search_recursive(arr, target, low, high):

if high >= low:
mid = (high + low) // 2
if arr[mid] == target:
return mid
elifarr[mid] > target:
return binary_search_recursive(arr, target, low, mid - 1)
else:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return -1

if __name__ == '__main__':
data = [2, 3, 4, 10, 40]
target = 10

linear_result = linear_search(data, target)

print(f"Linear Search - Element {target} found at index: {linear_result}")

data_sorted = sorted(data)
binary_result = binary_search_recursive(data_sorted, target, 0, len(data_sorted) - 1)
print(f"Recursive Binary Search - Element {target} found at index: {binary_result}")

Output:
 Problem #2
Q. Program for Heap Sort.
def heapify(arr, n, i):
largest = i
l=2*i+1
r=2*i+2

if l < n and arr[i] <arr[l]:

largest = l

if r < n and arr[largest] <arr[r]:

largest = r

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)

for i in range(n // 2 - 1, -1, -1):

heapify(arr, n, i)

for i in range(n - 1, 0, -1):

arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)

if __name__ == '__main__':
data = [12, 11, 13, 5, 6, 7]
heap_sort(data)
print("Sorted array using Heap Sort is:")
print(data)

Output:
 Problem #3
Q. Program for Merge Sort.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]

merge_sort(L)
merge_sort(R)

i=j=k=0

while i<len(L) and j <len(R):

if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

while i< len(L):

arr[k] = L[i]
i += 1
k += 1

while j <len(R):
arr[k] = R[j]
j += 1
k += 1

if __name__ == '__main__':
data = [38, 27, 43, 3, 9, 82, 10]
merge_sort(data)
print("Sorted array using Merge Sort is:")
print(data)

Output:
 Problem #4
Q. Program for Selection Sort.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] <arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

if __name__ == '__main__':
data = [64, 25, 12, 22, 11]
selection_sort(data)
print("Sorted array using Selection Sort is:")
print(data)

Output:
 Problem #5
Q. Program for Insertion Sort.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and key <arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

if __name__ == '__main__':
data = [12, 11, 13, 5, 6]
insertion_sort(data)
print("Sorted array using Insertion Sort is:")
print(data)

Output:
 Problem #6
Q. Program for Quick Sort.
def partition(arr, low, high):
i = (low - 1)
pivot = arr[high]

for j in range(low, high):

if arr[j] <= pivot:
i=i+1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]

return (i + 1)

def quick_sort(arr, low, high):

if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)

if __name__ == '__main__':
data = [10, 7, 8, 9, 1, 5]
n = len(data)
quick_sort(data, 0, n - 1)
print("Sorted array using Quick Sort is:")
print(data)

Output:
 Problem #7
Q. Knapsack Problem using Greedy Solution
def knapsack_greedy(W, wt, val):
n = len(wt)
items = []
for i in range(n):
[Link]((val[i] / wt[i], wt[i], val[i]))

[Link](key=lambda x: x[0], reverse=True)

max_value = 0.0
current_weight = 0

for ratio, weight, value in items:

if current_weight + weight <= W:
current_weight += weight
max_value += value
else:
remaining_capacity = W - current_weight
fraction = remaining_capacity / weight
max_value += value * fraction
current_weight += remaining_capacity
break

return max_value

if __name__ == '__main__':
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
max_val = knapsack_greedy(W, wt, val)
print(f"Maximum value in Knapsack (Greedy): {max_val}")

Output:
 Problem #8
Q. Perform Travelling Salesman Problem
import itertools
import sys

def calculate_path_cost(path, graph):

cost = 0
for i in range(len(path) - 1):
cost += graph[path[i]][path[i+1]]
cost += graph[path[-1]][path[0]]
return cost

def travelling_salesman_problem(graph):
n = len(graph)
nodes = list(range(n))
min_cost = [Link]
best_path = []

for path in [Link](nodes):

current_cost = calculate_path_cost(path, graph)
if current_cost<min_cost:
min_cost = current_cost
best_path = path

final_path = list(best_path) + [best_path[0]]

return min_cost, final_path

if __name__ == '__main__':
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

min_cost, path = travelling_salesman_problem(graph)

print(f"Minimum cost for TSP (Brute Force): {min_cost}")
print(f"Optimal path (starting and ending at node 0): {path}")
Output:
 Problem #9
Q. Find Minimum Spanning Tree using Kruskal’s Algorithm
def kruskals_mst_basic(graph):
edges = []
for u in range(len(graph)):
for v in range(u + 1, len(graph)):
if graph[u][v] != 0:
[Link]((graph[u][v], u, v))
[Link]()

parent = list(range(len(graph)))
def find_set(i):
if parent[i] == i:
return i
return find_set(parent[i])

def union_sets(i, j):

i_id = find_set(i)
j_id = find_set(j)
if i_id != j_id:
parent[i_id] = j_id
return True
return False

mst_weight = 0
mst_edges = []

for weight, u, v in edges:

if union_sets(u, v):
mst_weight += weight
mst_edges.append((u, v, weight))
return mst_weight, mst_edges

if __name__ == '__main__':
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]
]
weight, edges = kruskals_mst_basic(graph)
print(f"Minimum Spanning Tree Weight (Kruskal's Basic): {weight}")
print("Edges in MST:")
print(edges)
Output:
 Problem #10
Q. Implement N Queen Problem using Backtracking
def is_safe(board, row, col, N):
for i in range(col):
if board[row][i] == 1:
return False
i, j = row, col
while i>= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
i, j = row, col
while i< N and j >= 0:
if board[i][j] == 1:
return False
i += 1
j -= 1
return True

def solve_n_queen_util(board, col, N, solutions):

if col >= N:
solution = ["".join(["Q" if board[i][j] == 1 else "." for j in range(N)]) for i in range(N)]
[Link](solution)
return
for i in range(N):
if is_safe(board, i, col, N):
board[i][col] = 1
solve_n_queen_util(board, col + 1, N, solutions)
board[i][col] = 0

def n_queen_problem(N):
board = [[0] * N for _ in range(N)]
solutions = []
solve_n_queen_util(board, 0, N, solutions)
return solutions

if __name__ == '__main__':
N=4
solutions = n_queen_problem(N)
print(f"Total solutions for N={N} Queens: {len(solutions)}")
if solutions:
print("One solution:")
for row in solutions[0]:
print(row)
Output:
 Problem #11
Q. Sort a given set of n integer elements using Quick Sort method and compute
its time complexity. Run the program for varied values of n> 5000 and record the
time taken to sort. Plot a graph of the time taken versus non graph sheet. The
elements can be read from a file or can be generated using the random number
generator. Demonstrate using Java how the divide and- conquer method works
along with its time complexity analysis: worst case, average case and best case.
import [Link];
import [Link];
import [Link];

public class QuickSortPerformance {

private void swap(int[] arr, int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

private int partition(int[] arr, int low, int high) {

int pivot = arr[high];
int i = (low - 1);

for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}

swap(arr, i + 1, high);
return (i + 1);
}

public void quickSort(int[] arr, int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

public static void main(String[] args) {

QuickSortPerformance sorter = new QuickSortPerformance();
int[] nValues = {5000, 10000, 20000};
Random rand = new Random();

[Link]("--- Quick Sort Performance Analysis (n > 5000) ---");

[Link]("%-15s | %s%n", "Array Size (n)", "Time Taken (ms)");
[Link]("-------------------------------------");

for (int n :nValues) {

int[] arrRandom = new int[n];
for (int i = 0; i< n; i++) {
arrRandom[i] = [Link](100000);
}

long startTime = [Link]();

[Link](arrRandom, 0, n - 1);
long endTime = [Link]();

long duration = [Link](endTime - startTime);

[Link]("%-15d | %d%n", n, duration);
}

[Link]("\n--- Time Complexity Analysis (Quick Sort) ---");

[Link]("Divide-and-Conquer Method:");
[Link]("Quick Sort is a divide-and-conquer algorithm. It selects an element as a pivot and
partitions the array around the pivot. The sub-arrays are then recursively sorted.");

[Link]("\nWorst Case Time Complexity: O(n^2)");

[Link]("Occurs when the pivot selection consistently leads to the most unbalanced partition
(e.g., array is already sorted or reverse sorted, and the pivot is always the smallest/largest element).");

[Link]("\nAverage Case Time Complexity: O(n log n)");

[Link]("Occurs when the pivot divides the array into roughly equal or near-equal halves. This is
the most common case in practice due to random data distribution.");

[Link]("\nBest Case Time Complexity: O(n log n)");

[Link]("Occurs when the partition process always picks the median element as the pivot, leading
to perfectly balanced sub-arrays.");

[Link]("\nInstructions for Plotting:");

[Link]("Use the recorded time data points (n, Time Taken) to manually plot a graph of Time
Taken vs. n on a graph sheet. This plot should visually demonstrate the near O(n log n) behavior of Quick
Sort in the average case.");
}
}
Output:

Graph:
 Problem #12
Q. Sort a given set of n integer elements using Merge Sort method and compute
its time complexity. Run the program for varied values of n> 5000, and record
the time taken to sort. Plot a graph of the time taken versus non graph sheet. The
elements can be read from a file or can be generated using the random number
generator. Demonstrate how the divide andconquer method works along with its
time complexity analysis: worst case, average case and best case.
import random
import time

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]

merge_sort(L)
merge_sort(R)

i=j=k=0

while i<len(L) and j <len(R):

if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

while i< len(L):

arr[k] = L[i]
i += 1
k += 1

while j <len(R):
arr[k] = R[j]
j += 1
k += 1

def run_performance_test():
n_values = [5000, 10000, 20000]
results = {}
 print("--- Merge Sort Performance Analysis (n > 5000) ---")
print("Array Size (n) | Time Taken (seconds)")
print("-------------------------------------")

for n in n_values:
arr_random = [[Link](1, 100000) for _ in range(n)]

start_time = [Link]()
merge_sort(arr_random)
end_time = [Link]()

time_taken = end_time - start_time

results[n] = time_taken
print(f"{n:<14} | {time_taken:.6f}")

print("\n--- Time Complexity Analysis (Merge Sort) ---")

print("Divide-and-Conquer Method:")
print("Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, calls
itself for the two halves, and then merges the two sorted halves. The merging step is the core operation.")
print("\nWorst Case Time Complexity: O(n log n)")
print("Occurs consistently regardless of the input array's arrangement, as Merge Sort always divides the
array into two halves and takes O(n) time to merge.")
print("\nAverage Case Time Complexity: O(n log n)")
print("Same as the worst case.")
print("\nBest Case Time Complexity: O(n log n)")
print("Same as the worst case, demonstrating its stability and reliable performance irrespective of input
order.")
print("\nInstructions for Plotting:")
print("Use the recorded time data points (n, Time Taken) to manually plot a graph of Time Taken vs. n on
a graph sheet. This plot should visually demonstrate the consistent O(n log n) behavior of Merge Sort.")

if __name__ == '__main__':
run_performance_test()
Output:

Graph:
 Problem #13
Q. Implement, the 0/1 Knapsack problem using;
(a). Dynamic Programming method
(b). Greedy method.
def knapsack_dp(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]

for i in range(n + 1):

for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]

return K[n][W]

def knapsack_greedy(W, wt, val, n):

items = []
for i in range(n):
[Link]((val[i] / wt[i], wt[i], val[i]))

[Link](key=lambda x: x[0], reverse=True)

max_value = 0.0
current_weight = 0

for ratio, weight, value in items:

if current_weight + weight <= W:
current_weight += weight
max_value += value
else:
remaining_capacity = W - current_weight
fraction = remaining_capacity / weight
max_value += value * fraction
break

return max_value

if __name__ == '__main__':
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
 n = len(val)

dp_result = knapsack_dp(W, wt, val, n)

print(f"Maximum value for 0/1 Knapsack (Dynamic Programming): {dp_result}")

greedy_result = knapsack_greedy(W, wt, val, n)

print(f"Maximum value for Fractional Knapsack (Greedy): {greedy_result}")
print("Note: Greedy approach is optimal for Fractional Knapsack, but not for 0/1 Knapsack.")

Output:
 Problem #14
Q. From a given vertex in a weighted connected graph, find shortest paths to
other vertices using Dijkstra's algorithm.
import heapq

def dijkstra(graph, start_node):

num_vertices = len(graph)
distances = {node: float('inf') for node in range(num_vertices)}
distances[start_node] = 0
priority_queue = [(0, start_node)]

while priority_queue:
current_distance, current_node = [Link](priority_queue)

if current_distance> distances[current_node]:
continue

for neighbor, weight in graph[current_node].items():

distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
[Link](priority_queue, (distance, neighbor))

return distances

if __name__ == '__main__':
graph = {
0: {1: 4, 2: 8},
1: {0: 4, 2: 11, 3: 8},
2: {0: 8, 1: 11, 4: 7},
3: {1: 8, 4: 2, 5: 9},
4: {2: 7, 3: 2, 5: 6},
5: {3: 9, 4: 6}
}
start_node = 0
shortest_paths = dijkstra(graph, start_node)
print(f"Shortest paths from node {start_node}:")
print(shortest_paths)
Output:
 Problem #15
Q. Find Minimum Cost Spanning Tree of a given connected undirected graph
using Kruskal's algorithm. Use Union-Find algorithms in your program.
class DisjointSet:
def __init__(self, n):
[Link] = list(range(n))

def find(self, i):

if [Link][i] == i:
return i
[Link][i] = [Link]([Link][i])
return [Link][i]

def union(self, i, j):

i_root = [Link](i)
j_root = [Link](j)
if i_root != j_root:
[Link][i_root] = j_root
return True
return False

def kruskals_mst(edges, num_vertices):

[Link]()
ds = DisjointSet(num_vertices)
mst_weight = 0
mst_edges = []

for weight, u, v in edges:

if [Link](u, v):
mst_weight += weight
mst_edges.append((u, v, weight))
return mst_weight, mst_edges

if __name__ == '__main__':
edges = [
(4, 0, 1), (8, 0, 7), (8, 1, 2), (11, 1, 7),
(7, 2, 3), (2, 2, 8), (4, 3, 4), (14, 3, 5),
(9, 4, 5), (10, 5, 6), (1, 6, 7), (2, 6, 8),
(6, 7, 8)
]
num_vertices = 9
weight, mst_edges = kruskals_mst(edges, num_vertices)
print(f"Minimum Spanning Tree Weight (Kruskal's with Union-Find): {weight}")
print("Edges in MST:")
print(mst_edges)
Output:
 Problem #16
Q. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s
algorithm.
import heapq

def prims_mst(graph):
num_vertices = len(graph)

min_heap = [(0, 0)]

in_mst = [False] * num_vertices
mst_weight = 0
mst_edges = []

while min_heap:
weight, u = [Link](min_heap)

if in_mst[u]:
continue

in_mst[u] = True
mst_weight += weight

for v in range(num_vertices):
edge_weight = graph[u][v]
if edge_weight> 0 and not in_mst[v]:
[Link](min_heap, (edge_weight, v))

return mst_weight

if __name__ == '__main__':
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]
]

weight = prims_mst(graph)
print(f"Minimum Spanning Tree Weight (Prim's Algorithm): {weight}")
Output:
 Problem #17
Q. Write programs to;
(a) Implement All-Pairs Shortest Paths problem using Floyd's algorithm.
(b) Implement Travelling Sales Person problem using Dynamic programming.
import sys
import math

INF = [Link]

def floyd_warshall(graph):
V = len(graph)
dist = [[graph[i][j] for j in range(V)] for i in range(V)]

for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return dist

def tsp_dp(graph):
V = len(graph)
memo = {}

def solve(mask, pos):

if mask == (1 << V) - 1:
return graph[pos][0]

if (mask, pos) in memo:

return memo[(mask, pos)]

min_cost = INF
for next_node in range(V):
if (mask & (1 <<next_node)) == 0:
new_mask = mask | (1 <<next_node)
cost = graph[pos][next_node] + solve(new_mask, next_node)
min_cost = min(min_cost, cost)

memo[(mask, pos)] = min_cost

return min_cost

return solve(1, 0)

if __name__ == '__main__':
 floyd_graph = [
[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]
all_pairs_shortest_paths = floyd_warshall(floyd_graph)
print("All-Pairs Shortest Paths (Floyd's Algorithm):")
for row in all_pairs_shortest_paths:
print([x if x != INF else "INF" for x in row])

tsp_graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
min_tsp_cost = tsp_dp(tsp_graph)
print(f"\nMinimum cost for TSP (Dynamic Programming): {min_tsp_cost}")

Output:
 Problem #18
Q. Design and implement to find a subset of a given set S = {Sl, S2,. ....,Sn} of n
positive integers whose SUM is equal to a given positive integer d. For example,
if S ={1, 2, 5, 6, 8} and d= 9, there are two solutions {1,2,6}and {1,8}. Display a
suitable message, if the given problem instance doesn't have a solution.
def subset_sum_util(S, d, index, current_subset, solutions):
if d == 0:
[Link](list(current_subset))
return

if index == len(S) or d < 0:

return

current_subset.append(S[index])
subset_sum_util(S, d - S[index], index + 1, current_subset, solutions)
current_subset.pop()

subset_sum_util(S, d, index + 1, current_subset, solutions)

def subset_sum(S, d):

solutions = []
[Link]()
subset_sum_util(S, d, 0, [], solutions)
return solutions

if __name__ == '__main__':
S = [1, 2, 5, 6, 8]
d=9
results = subset_sum(S, d)

print(f"Given set S = {S} and target sum d = {d}")

if results:
print("Solutions found:")
for solution in results:
print(solution)
else:
print("No subset found that sums to the target.")
Output:
 Problem #19
Q. Design and implement to find all Hamiltonian Cycles in a connected
undirected Graph G of n vertices using backtracking principle.
def is_safe(v, graph, path, pos):
if graph[path[pos - 1]][v] == 0:
return False

if v in path[:pos]:
return False
return True

def ham_cycle_util(graph, path, pos, V, cycles):

if pos == V:
if graph[path[pos - 1]][path[0]] == 1:
[Link](path + [path[0]])
return

for v in range(1, V):

if is_safe(v, graph, path, pos):
path[pos] = v
ham_cycle_util(graph, path, pos + 1, V, cycles)
path[pos] = -1

def find_hamiltonian_cycles(graph):
V = len(graph)
path = [-1] * V
path[0] = 0
cycles = []

ham_cycle_util(graph, path, 1, V, cycles)

return cycles

if __name__ == '__main__':
graph = [
[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0]
]

cycles = find_hamiltonian_cycles(graph)
print(f"Found {len(cycles)} Hamiltonian Cycles (starting and ending at node 0):")
for cycle in cycles:
print(cycle)
Output: