You need to login before you can make any post submission.
Graph is a data structure that consists of following two components:
- Adjacency Matrix
adj[i][j] = 1
indicates that there is an edge from vertex i to vertex j.
- Adjacency List
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u) # If undirected
def print_graph(self):
# print the vertex
for vertex in self.graph:
print("[{}]".format(vertex), end="")
# print the connected_vertices to this vertex
for connected_vertex in self.graph[vertex]:
print("-->{}".format(connected_vertex), end="")
print()
print("Example-1: Graph Representation")
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)
g.print_graph()
Output:
Graphs are used to represent many real-life applications:
BFS for a graph is similar to Breadth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again.
To avoid processing a node more than once, we use a boolean visited array.
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
def unvisited(self, visited):
for vertex in visited:
if(visited[vertex] is False):
return vertex
return None
def bfs_traversal_util(self, start_vertex, visited):
# Take a queue and enqueue the start_vertex and mark it as visited
queue = []
queue.append(start_vertex)
visited[start_vertex] = True
# Dequeue out the current_vertex from queue and print it
while(queue):
current_vertex= queue.pop(0)
print("{}".format(current_vertex), end=" ")
# See all the connected vertices to current_vertex
for connected_vertex in self.graph[current_vertex]:
# If any connected_vertex is not visited enqueue to the queue and mark it visited
if(visited[connected_vertex] is False):
queue.append(connected_vertex)
visited[connected_vertex] = True
def bfs_traversal(self, start_vertex):
# Mark every every vertex as unvisited
visited = {}
for vertex in self.graph:
visited[vertex] = False
# Call the bfs_traversal_util with start_vertex
self.bfs_traversal_util(start_vertex, visited)
# Check if there is still any unvisited vertex
# Only when graph is UNREACHABLE or DISCONNECTED below lines will be executed
while(self.unvisited(visited) is not None):
# Call the bfs_traversal_util from the unvisited vertex
self.bfs_traversal_util(self.unvisited(visited), visited)
print()
print("Example-1: BFS Traversal of Graph from vertex-1:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 2)
g.add_edge(1, 5)
g.add_edge(5, 6)
g.add_edge(5, 8)
g.add_edge(8, 3)
g.add_edge(8, 6)
g.add_edge(8, 7)
g.bfs_traversal(1)
print("Example-2: BFS Traversal of Graph from vertex-2:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 5)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.bfs_traversal(2)
print("Example-3: BFS Traversal of Graph from vertex-A:")
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("D", "E")
g.add_edge("E", "G")
g.add_edge("F", "D")
g.add_edge("G", "H")
g.add_edge("H", "E")
g.bfs_traversal("A")
Output:
DFS for a graph is similar to Depth First Traversal of tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again.
To avoid processing a node more than once, we use a boolean visited array.
Start with the given start_vertex, take a stack and push the start_vertex to it.
While stack is not empty take out the current_vertex from stack.
If current_vertex is not already visited:
coz stack may contain some vertex more than once, so we need to print the popped item only if it is not visited. This may happen if some vertex was discovered by some earlier vertex and at later point it is visited by some other vertex. # Example: In Graph-1: vertex-2 and vertex-6 was discovered by previous vertex and visited later by other.
See all the connected vertices to current_vertex:
Check if any unvisited vertex (case of UNREACHABLE or DISCONNECTED graphs):
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
def unvisited(self, visited):
for vertex in visited:
if(visited[vertex] is False):
return vertex
return None
def dfs_traversal_iterative_util(self, start_vertex, visited):
# Take a stack and push the start_vertex
stack = []
stack.append(start_vertex)
# Pop out the current_vertex from stack and print it
while(stack):
current_vertex= stack.pop()
# Stack may contain some vertex more than once, so we need to print the popped item
# only if it is not visited.
# This may happen if some vertex was discovered by some earlier vertex and at
# later point it is visited by some other vertex.
# Example: In Graph-1: vertex-2 and vertex-6 was discovered by previous
# vertex and visited later by other.
if(visited[current_vertex] is False):
visited[current_vertex] = True
print("{}".format(current_vertex), end=" ")
# See all the connected vertices to current_vertex
for connected_vertex in self.graph[current_vertex]:
# If any connected_vertex is not visited push to the stack
if(visited[connected_vertex] is False):
stack.append(connected_vertex)
def dfs_traversal_iterative(self, start_vertex):
# Mark every every vertex as unvisited
visited = {}
for vertex in self.graph:
visited[vertex] = False
# Call the dfs_traversal_iterative_util with start_vertex
self.dfs_traversal_iterative_util(start_vertex, visited)
# Check if there is still any unvisited vertex
# Only when graph is UNREACHABLE or DISCONNECTED below lines will be executed
while(self.unvisited(visited) is not None):
# Call the dfs_traversal_iterative_util from the unvisited vertex
self.dfs_traversal_iterative_util(self.unvisited(visited), visited)
print()
print("Example-1: DFS Traversal of Graph (Iterative) from vertex-1:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 2)
g.add_edge(1, 5)
g.add_edge(5, 6)
g.add_edge(5, 8)
g.add_edge(8, 3)
g.add_edge(8, 6)
g.add_edge(8, 7)
g.dfs_traversal_iterative(1)
print("Example-2: DFS Traversal of Graph (Iterative) from vertex-2:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 5)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.dfs_traversal_iterative(2)
print("Example-3: DFS Traversal of Graph (Iterative) from vertex-A:")
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("D", "E")
g.add_edge("E", "G")
g.add_edge("F", "D")
g.add_edge("G", "H")
g.add_edge("H", "E")
g.dfs_traversal_iterative("A")
Output:
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
def unvisited(self, visited):
for vertex in visited:
if(visited[vertex] is False):
return vertex
return None
def dfs_traversal_recursive_util(self, vertex, visited):
visited[vertex] = True
print("{}".format(vertex), end=" ")
# See all the connected vertices to vertex and make recursive call from
# the vertex not already visited
for connected_vertex in self.graph[vertex]:
if(visited[connected_vertex] is False):
self.dfs_traversal_recursive_util(connected_vertex, visited)
def dfs_traversal_recursive(self, start_vertex):
# Mark every every vertex as unvisited
visited = {}
for vertex in self.graph:
visited[vertex] = False
# Call the dfs_traversal_recursive_util with start_vertex
self.dfs_traversal_recursive_util(start_vertex, visited)
# Check if there is still any unvisited vertex
# Only when graph is UNREACHABLE or DISCONNECTED below lines will be executed
while(self.unvisited(visited) is not None):
# Call the dfs_traversal_recursive_util from the unvisited vertex
self.dfs_traversal_recursive_util(self.unvisited(visited), visited)
print()
print("Example-1: DFS Traversal of Graph (Recursive) from vertex-1:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 2)
g.add_edge(1, 5)
g.add_edge(5, 6)
g.add_edge(5, 8)
g.add_edge(8, 3)
g.add_edge(8, 6)
g.add_edge(8, 7)
g.dfs_traversal_recursive(1)
print("Example-2: DFS Traversal of Graph (Recursive) from vertex-2:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 5)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.dfs_traversal_recursive(2)
print("Example-3: DFS Traversal of Graph (Recursive) from vertex-A:")
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("D", "E")
g.add_edge("E", "G")
g.add_edge("F", "D")
g.add_edge("G", "H")
g.add_edge("H", "E")
g.dfs_traversal_recursive("A")
Output:
Given a undirected graph, check whether the graph contains a cycle or not.
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
self.graph[v].append(u)
def unvisited(self, visited):
for vertex in visited:
if(visited[vertex] == False):
return vertex
return None
def detect_cycle_undirected_graph_util(self, current_vertex, parent, visited):
# Mark the current_vertex as visited
visited[current_vertex] = True
# See the connected vertices to current_vertex one by one
for connected_vertex in self.graph[current_vertex]:
# If connected_vertex is not visited then make recursive call from the connected_vertex
# with current_vertex as parent and return True if it returns True.
if(visited[connected_vertex] == False):
if(self.detect_cycle_undirected_graph_util(connected_vertex, current_vertex, visited) == True):
return True
# Else if connected_vertex is already visited and it is not parent then cycle found return True.
elif(connected_vertex != parent):
print("Cycle Exists coz of {} ----- {}".format(current_vertex, connected_vertex))
return True
# Once the current_vertex is processed return False to show that
# cycle was not found while processing this current_vertex.
return False
def detect_cycle_undirected_graph(self, start_vertex):
# Mark every every vertex as unvisited initially
visited = {}
for vertex in self.graph:
visited[vertex] = False
# Call the detect_cycle_undirected_graph_util with start_vertex
cycle_exists = self.detect_cycle_undirected_graph_util(start_vertex, None, visited)
# Check if there is still any unvisited vertex and cycle still not found
# Only when graph is DISCONNECTED below lines will be executed
while(self.unvisited(visited) is not None and cycle_exists == False):
# Call the detect_cycle_undirected_graph_util from the unvisited vertex
cycle_exists = self.detect_cycle_undirected_graph_util(self.unvisited(visited), None, visited)
if(not cycle_exists):
print("Cycle doesn't exist!")
print("Example-1: Detect Cycle in Undirected Graph:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)
g.detect_cycle_undirected_graph(1)
print("\nExample-2: Detect Cycle in Undirected Graph:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.detect_cycle_undirected_graph(1)
print("\nExample-3: Detect Cycle in Undirected Graph:")
g = Graph()
g.add_edge("A", "B")
g.add_edge("B", "C")
g.add_edge("D", "E")
g.add_edge("D", "F")
g.add_edge("E", "G")
g.add_edge("E", "H")
g.add_edge("G", "H")
g.detect_cycle_undirected_graph("A")
Output:
Given a directed graph, check whether the graph contains a cycle or not.
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
def unvisited(self, visited):
for vertex in visited:
if(visited[vertex] == "white"):
return vertex
return None
def detect_cycle_directed_graph_util(self, current_vertex, color):
# Mark the current_vertex as "gray" i.e. processing
color[current_vertex] = "gray"
# See the connected vertices to current_vertex one by one
for connected_vertex in self.graph[current_vertex]:
# If connected_vertex is "white" i.e. still to be processed then
# make recursive call from the connected_vertex
# and return True if it returns True
if(color[connected_vertex] == "white"):
if(self.detect_cycle_directed_graph_util(connected_vertex, color) == True):
return True
# Else if connected_vertex is "gray" i.e. in processing then we have found the cycle return True
elif(color[connected_vertex] == "gray"):
print("Cycle Exists coz of {} -----> {}". format(current_vertex, connected_vertex))
return True
# If reaches here that means processing of current vertex is done, mark it black
# return False to show that cycle was not found while processing this current_vertex
color[current_vertex] = "black"
return False
def detect_cycle_directed_graph(self, start_vertex):
# Mark every every vertex as "white" i.e. still to be processed
color = {}
for vertex in self.graph:
color[vertex] = "white"
# Call the detect_cycle_directed_graph_util with start_vertex
cycle_exists = self.detect_cycle_directed_graph_util(start_vertex, color)
# Check if there is still any "white” vertex and cycle still not found
# Only when graph is UNREACHABLE or DISCONNECTED below lines will be executed
while(self.unvisited(color) is not None and cycle_exists == False):
# Call the detect_cycle_directed_graph_util from the "white" vertex
cycle_exists = self.detect_cycle_directed_graph_util(self.unvisited(color), color)
if(not cycle_exists):
print("Cycle doesn't exist!")
print("Example-1: Detect Cycle in Directed Graph:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 2)
g.add_edge(1, 5)
g.add_edge(5, 6)
g.add_edge(5, 8)
g.add_edge(8, 3)
g.add_edge(8, 6)
g.add_edge(8, 7)
g.detect_cycle_directed_graph(1)
print("\nExample-2: Detect Cycle in Directed Graph:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 5)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.detect_cycle_directed_graph(1)
print("\nExample-3: Detect Cycle in Directed Graph:")
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("D", "E")
g.add_edge("E", "G")
g.add_edge("F", "D")
g.add_edge("G", "H")
g.add_edge("H", "E")
g.detect_cycle_directed_graph("A")
Output:
What is Topological Sorting:
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
def unvisited(self, visited):
for vertex in visited:
if(visited[vertex] is False):
return vertex
return None
def topological_sort_util(self, current_vertex, visited, result_stack):
# Mark the current_vertex as visited
visited[current_vertex] = True
# See all the connected vertices to current_vertex one by one
for connected_vertex in self.graph[current_vertex]:
# If connected_vertex is not already visited then make recursive call from the connected_vertex
if(visited[connected_vertex] is False):
self.topological_sort_util(connected_vertex, visited, result_stack)
# Once processing of current_vertex is done push it to result_stack
result_stack.append(current_vertex)
def topological_sort(self, start_vertex):
# Mark every every vertex as unvisited
visited = {}
for vertex in self.graph:
visited[vertex] = False
# Take a result_stack to store the result
result_stack = []
# Call the topological_sort_util with start_vertex
self.topological_sort_util(start_vertex, visited, result_stack)
# Check if there is still any unvisited vertex
# Only when graph is UNREACHABLE or DISCONNECTED below lines will be executed
while(self.unvisited(visited) is not None):
# Call the topological_sort_util from the unvisited vertex
self.topological_sort_util(self.unvisited(visited), visited, result_stack)
# print the result_stack in reverse order
result_stack.reverse()
for vertex in result_stack:
print("{} ".format(vertex), end="")
print()
print("Example-1: Topological Sorting from vertex-1:")
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(1, 5)
g.add_edge(5, 6)
g.add_edge(5, 8)
g.add_edge(8, 3)
g.add_edge(8, 6)
g.add_edge(8, 7)
g.topological_sort(1)
print("\nExample-2: Topological Sorting from vertex-6:")
g = Graph()
g.add_edge(3, 4)
g.add_edge(4, 2)
g.add_edge(5, 1)
g.add_edge(5, 2)
g.add_edge(6, 1)
g.add_edge(6, 3)
g.topological_sort(6)
print("\nExample-3: Topological Sorting from vertex-A:")
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "C")
g.add_edge("D", "E")
g.add_edge("E", "G")
g.add_edge("F", "D")
g.add_edge("G", "H")
g.topological_sort("A")
Output:
A minimum spanning tree has |V – 1| edges where V is the number of vertices in the given graph.
Total spanning trees possible in a graph = ^{|E|}C_{|V-1|}- total cycles.
MST is not possible for disconnected graph.
import sys
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v, w):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append((v, w))
self.graph[v].append((u, w))
def get_min_key_vertex_not_in_mst(self, mst_set, key):
min_key = sys.maxsize
min_vertex = None
for k in key:
if(key[k] < min_key and mst_set[k] == False):
min_key = key[k]
min_vertex = k
return min_vertex
def prims_mst(self, start_vertex):
# Initially, set mst_set of every vertex as False,
# key of every vertex as "MAX" and parent of every vertex as "-".
mst_set = {}; key = {}; parent = {}
for vertex in self.graph:
mst_set[vertex] = False
key[vertex] = sys.maxsize
parent[vertex] = "-"
# Set the key[start_vertex] = 0 and min_vertex = start_vertex :
# From this vertex we will start the MST
key[start_vertex] = 0
min_vertex = start_vertex
while(min_vertex is not None):
# Add the min_vertex to the mst_set
mst_set[min_vertex] = True
# See all the connected vertices to min_vertex one by one
for connected_vertex in self.graph[min_vertex]:
con_vertex = connected_vertex[0]
con_vertex_weight = connected_vertex[1]
# If the connected_vertex is not in mst_set and also
# weight of the connected_vertex < key[connected vertex],
# then update the key of connected vertex and also it's parent to be the min_vertex
if(mst_set[con_vertex] == False and con_vertex_weight < key[con_vertex]):
key[con_vertex] = con_vertex_weight
parent[con_vertex] = min_vertex
# Again call the function to get new min_vertex with updated mst_set and key
min_vertex = self.get_min_key_vertex_not_in_mst(mst_set, key)
# Print the edges and their respective weights using parent and key dicts.
ordered_parent = sorted(parent.items(), key=lambda k: (k[1]))
print("="*23 + "\nEdges\t:\tWeights\n" + "="*23)
for vertex, parent_vertex in ordered_parent:
print("{} -- {} \t:\t {}".format(parent_vertex, vertex, key[vertex]))
print("Example: Prim's MST from vertex-A:")
g = Graph()
g.add_edge("A", "B", 4)
g.add_edge("A", "H", 8)
g.add_edge("B", "C", 8)
g.add_edge("B", "H", 11)
g.add_edge("C", "D", 7)
g.add_edge("C", "F", 4)
g.add_edge("C", "I", 2)
g.add_edge("D", "E", 9)
g.add_edge("D", "F", 14)
g.add_edge("E", "F", 10)
g.add_edge("F", "G", 2)
g.add_edge("G", "H", 1)
g.add_edge("G", "I", 6)
g.add_edge("H", "I", 7)
g.prims_mst("A")
Output:
Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph.
import sys
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, u, v, w):
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append((v, w))
self.graph[v].append((u, w))
def get_min_distant_vertex_not_in_spt(self, spt_set, vertex_distance):
min_vertex_distance = sys.maxsize
min_distant_vertex = None
for v in vertex_distance:
if(vertex_distance[v] < min_vertex_distance and spt_set[v] == False):
min_vertex_distance = vertex_distance[v]
min_distant_vertex = v
return min_distant_vertex
def dijkstras_spt(self, start_vertex):
# Initially, set spt_set of every vertex as False,
# vertex_distance of every vertex as "MAX" and parent of every vertex as "-".
spt_set = {}; vertex_distance = {}; parent = {}
for vertex in self.graph:
spt_set[vertex] = False
vertex_distance[vertex] = sys.maxsize
parent[vertex] = "-"
# Set the vertex_distance[start_vertex] = 0 and min_distant_vertex = start_vertex :-
# From this vertex we will start the SPT.
vertex_distance[start_vertex] = 0
min_distant_vertex = start_vertex
while(min_distant_vertex is not None):
# Add the min_distant_vertex to the spt_set
spt_set[min_distant_vertex] = True
# See all the connected vertices to min_distant_vertex one by one
for connected_vertex in self.graph[min_distant_vertex]:
con_vertex = connected_vertex[0]
con_vertex_weight = connected_vertex[1]
# If the connected_vertex is not in spt_set and also weight of connected_vertex +
# vertex_distance[min_distant_vertex] < vertex_distance[connected vertex],
# then update the vertex_distance of connected_vertex and also
# it's parent to be the min_distant_vertex
if(spt_set[con_vertex] == False and
con_vertex_weight + vertex_distance[min_distant_vertex] < vertex_distance[con_vertex]):
vertex_distance[con_vertex] = con_vertex_weight + vertex_distance[min_distant_vertex]
parent[con_vertex] = min_distant_vertex
# Again call the function to get new min_distant_vertex with updated spt_set and vertex_distance
min_distant_vertex = self.get_min_distant_vertex_not_in_spt(spt_set, vertex_distance)
# Print the edges and their respective weights using parent and vertex_distance dicts.
ordered_parent = sorted(parent.items(), key=lambda k: (k[0]))
print("="*56 + "\nVertex\t:\tDistance from source\t:\tReach By\n" + "="*56)
for vertex, parent_vertex in ordered_parent:
print("{}\t:\t\t{}\t\t:\t{} --> {}".format(vertex, vertex_distance[vertex], parent_vertex, vertex))
print("Example: Dijkstra's Shortest Path from vertex-A:")
g = Graph()
g.add_edge("A", "B", 4)
g.add_edge("A", "H", 8)
g.add_edge("B", "C", 8)
g.add_edge("B", "H", 11)
g.add_edge("C", "D", 7)
g.add_edge("C", "F", 4)
g.add_edge("C", "I", 2)
g.add_edge("D", "E", 9)
g.add_edge("D", "F", 14)
g.add_edge("E", "F", 10)
g.add_edge("F", "G", 2)
g.add_edge("G", "H", 1)
g.add_edge("G", "I", 6)
g.add_edge("H", "I", 7)
g.dijkstras_spt("A")
Output:
Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from source or 1st cell.Basically, the player has total control over outcome of dice throw and wants to find out minimum number of throws required to reach last cell.If the player reaches a cell which is base of a ladder, the player has to climb up that ladder and if reaches a cell is mouth of the snake, has to go down to the tail of snake without a dice throw.
def get_min_dice_throws_snake_ladder(N, moves):
# Mark every cell as unvisited and take an empty queue
visited = [False]*(N)
queue = []
# Mark the first_cell as visited and enqueue the first cell to the queue
# with dice_count=0 : We start from here.
visited[0] = True
queue.append((0, 0))
while(queue):
# Get the current element from the queue and then fetch the current_cell
# and current_dice_count from it.
current = queue.pop(0)
current_cell = current[0]
current_dice_count = current[1]
# if current_cell is last cell we are done, print the dice_count and break
if(current_cell == N-1):
print("No. of min dice count: {}".format(current_dice_count))
break
# Start seeing all the 6 reachable_cell from current_cell one by one
for reachable_cell in range(current_cell+1, current_cell+6):
# If reachable_cell is lesser than last cell and still not visited
# then mark the recahable_cell as visited
if(reachable_cell < N and visited[reachable_cell] is False):
visited[reachable_cell] = True
# If any of ladder or snake is available at reachable_cell
# modify the reachable_cell with the moves value
if(moves[reachable_cell] != -1):
reachable_cell = moves[reachable_cell]
# Update the queue with reachable_cell and dice_count needed to reach there.
queue.append((reachable_cell, current_dice_count+1))
print("Example-1:- Snake and Ladder:")
N = 30
moves = [-1] * N
# Ladders
moves[2] = 21
moves[4] = 7
moves[10] = 25
moves[19] = 28
# Snakes
moves[26] = 0
moves[20] = 8
moves[16] = 3
moves[18] = 6
get_min_dice_throws_snake_ladder(N, moves)
Output:
Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island.
Example:
Input :
matrix[][] : {1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
Output : 5 // Total 5 islands.
POSSIBLE_MOVES = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1,1)]
class Graph:
def __init__(self, matrix):
self.graph = matrix
self.row = len(matrix)
self.col = len(matrix[0])
def is_safe_cell(self, x, y, visited):
# Cell is safe if x is in range(row), y is in range(column),
# cell is still not visited and value of cell is 1.
return (x>=0 and x<self.row and
y>=0 and y<self.col and
not visited[x][y] and self.graph[x][y] ==1)
# Function to do DFS for a 2D boolean matrix, considers all the 8 neighbours as adjacent vertices.
def DFS(self, i, j, visited):
# Mark current_cell as visited
visited[i][j] = True
# For all neighbours check if the cell is safe then call the DFS again from that safe_cell.
for x_move, y_move in POSSIBLE_MOVES:
if(self.is_safe_cell(i+x_move, j+y_move, visited)):
self.DFS(i+x_move, j+y_move, visited)
def find_number_of_islands(self):
# Mark all cells as unvisited initially
visited = [[False]*self.col for i in range(self.row)]
islands_count = 0
for i in range(self.row):
for j in range(self.col):
# If a cell with value 1 is not visited yet, then new island is found
# Visit all cells in this island and increment islands_count
if(self.graph[i][j] == 1 and visited[i][j] is False):
self.DFS(i, j, visited)
islands_count += 1
print("Total islands: {}".format(islands_count))
print("Example-1:- Find number of Islands:")
matrix=[[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]]
g = Graph(matrix)
g.find_number_of_islands()
Output:
Output:
Output:
Output: