DIJKSTRA class Graph(): def _init_(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] for row in range(vertices)] def printSolution(self, dist): print("Vertex \t Distance from Source") for node in range(self.V): print(node, "\t\t", dist[node]) def minDistance(self, dist, sptSet): min = float('inf') for v in range(self.V): if dist[v] < min and not sptSet[v]: min = dist[v] min_index = v return min_index def dijkstra(self, src): dist = [float('inf')] self.V dist[src] = 0 sptSet = [False] self.V for cout in range(self.V): u = self.minDistance(dist, sptSet) sptSet[u] = True for v in range(self.V): if (self.graph[u][v] > 0 and not sptSet[v] and dist[v] > dist[u] + self.graph[u][v]): dist[v] = dist[u] + self.graph[u][v] self.printSolution(dist)

if _name_ == "_main_": V = int(input("Enter the number of vertices: ")) g = Graph(V) print("Enter the adjacency matrix (row-wise): ") for i in range(V): g.graph[i] = list(map(int, input().split())) source = int(input("Enter the source vertex: ")) g.dijkstra(source)

Driver program

g = Graph(9) g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0] ] g.dijkstra(0)

BELLMAN FORD: class Graph: def _init_(self, vertices): self.V = vertices self.graph = [] def add_edge(self, u, v, w): self.graph.append([u, v, w]) def distances(self, dist): print("Vertex from source:") for i in range(self.V): print("{0}\t\t{1}".format(i, dist[i])) def bellman_ford(self, src): dist = [float("Inf")] * self.V dist[src] = 0 for _ in range(self.V - 1): for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print("Graph contains negative weight cycle") return self.distances(dist) if _name_ == "_main_": num_vertices = int(input("Enter the number of vertices: ")) g = Graph(num_vertices) num_edges = int(input("Enter the number of edges: ")) print("Enter the edges (source, destination, weight):") for _ in range(num_edges): u, v, w = map(int, input().split()) g.add_edge(u, v, w) source_vertex = int(input("Enter the source vertex: ")) g.bellman_ford(source_vertex)

if name == 'main': g = Graph(5) g.addedges(0,1,-1) g.addedges(0, 2, 4) g.addedges(1, 2, 3) g.bellmanford(0) FLOYD WARSHALL: V = int(input("Enter the number of vertices: ")) INF = 99999 def floydWarshall(graph): dist = list(map(lambda i: list(map(lambda j: j, i)), graph)) 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]) printSolution(dist) def printSolution(dist): print("Following matrix shows the shortest distances between every pair of vertices") for i in range(V): for j in range(V): if dist[i][j] == INF: print("%7s" % ("INF"), end=" ") else: print("%7d\t" % (dist[i][j]), end=' ') if j == V-1: print() if _name_ == "_main_": print("Enter the adjacency matrix for the graph (use 'INF' for infinity):") graph = [] for _ in range(V): row = list(map(int, input().split())) graph.append(row) floydWarshall(graph)

if _name_ == "_main_": graph = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1], [INF, INF, INF, 0] ] floydWarshall(graph)

STRONGLY CONNECTED GRAPHS: class GFG:

# dfs Function to reach destination
def dfs(self, curr, des, adj, vis):
    # If current node is the destination, return True
    if curr == des:
        return True
    vis[curr] = 1
    for x in adj[curr]:
        if not vis[x]:
            if self.dfs(x, des, adj, vis):
                return True
    return False
# To tell whether there is a path from source to destination
def isPath(self, src, des, adj):
    vis = [0] * (len(adj) + 1)
    return self.dfs(src, des, adj, vis)
# Function to return all the strongly connected components of a graph.
def findSCC(self, n, a):
    # Stores all the strongly connected components.
    ans = []
    # Stores whether a vertex is a part of any Strongly Connected Component
    is_scc = [0] * (n + 1)
    adj = [[] for _ in range(n + 1)]
    for i in range(len(a)):
        adj[a[i][0]].append(a[i][1])

    # Traversing all the vertices
    for i in range(1, n + 1):
        if not is_scc[i]:
            # If a vertex i is not a part of any SCC, insert it into a new SCC list
            # and check for other vertices whether they can be part of this list.
            scc = [i]
            for j in range(i + 1, n + 1):
                # If there is a path from vertex i to vertex j and vice versa,
                # put vertex j into the current SCC list.
                if not is_scc[j] and self.isPath(i, j, adj) and self.isPath(j, i, adj):
                    is_scc[j] = 1
                    scc.append(j)
            # Insert the SCC containing vertex i into the final list.
            ans.append(scc)
    return ans

Driver Code Starts

if _name_ == "_main_": obj = GFG() V = 5 edges = [ [1, 3], [1, 4], [2, 1], [3, 2], [4, 5] ] ans = obj.findSCC(V, edges) print("Strongly Connected Components are:") for x in ans: for y in x: print(y, end=" ") print()

TOPOLOGICAL SORT: from collections import defaultdict class Graph: def _init_(self, vertices): self.graph = defaultdict(list) # dictionary containing adjacency List self.V = vertices # No. of vertices def addEdge(self, u, v): self.graph[u].append(v) def topologicalSortUtil(self, v, visited, stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i, visited, stack) stack.insert(0, v) def topologicalSort(self): visited = [False] * self.V stack = [] for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i, visited, stack) print("Following is a Topological Sort of the given graph") print(stack) if _name_ == "_main_": num_vertices = int(input("Enter the number of vertices: ")) g = Graph(num_vertices) num_edges = int(input("Enter the number of edges: ")) print("Enter edges as u v (source and destination vertices):") for _ in range(num_edges): u, v = map(int, input().split()) g.addEdge(u, v)

g.topologicalSort()

DRIVERS CODE:

g= Graph(6) g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); print ("Following is a Topological Sort of the given graph") g.topologicalSort()

KRUSHKAL MST: class Graph: def _init_(self, vertices): self.V = vertices self.graph = [] def addEdge(self, u, v, w): self.graph.append([u, v, w]) def find(self, parent, i): if parent[i] != i: parent[i] = self.find(parent, parent[i]) return parent[i] def union(self, parent, rank, x, y): if rank[x] < rank[y]: parent[x] = y elif rank[x] > rank[y]: parent[y] = x else: parent[y] = x rank[x] += 1 def KruskalMST(self): result = [] i = 0 e = 0 self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, w = self.graph[i] i = i + 1 x = self.find(parent, u) y = self.find(parent, v) if x != y: e = e + 1 result.append([u, v, w]) self.union(parent, rank, x, y) minimumCost = 0 print("Edges in the constructed MST") for u, v, weight in result: minimumCost += weight print("%d -- %d == %d" % (u, v, weight)) print("Minimum Spanning Tree", minimumCost) if _name_ == '_main_': num_vertices = int(input("Enter the number of vertices: ")) g = Graph(num_vertices) num_edges = int(input("Enter the number of edges: ")) print("Enter edges as u v w (source, destination, weight):") for _ in range(num_edges): u, v, w = map(int, input().split()) g.addEdge(u, v, w) g.KruskalMST()

if _name_ == '_main_': g = Graph(4) g.addEdge(0, 1, 10) g.addEdge(0, 2, 6) g.addEdge(0, 3, 5) g.addEdge(1, 3, 15) g.addEdge(2, 3, 4) g.KruskalMST()

PRIMS MST import sys class Graph: def _init_(self, vertices): self.V = vertices self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)] def printMST(self, parent): print("Edge \tWeight") for i in range(1, self.V): print(parent[i], "-", i, "\t", self.graph[i][parent[i]]) def minKey(self, key, mstSet): min = sys.maxsize for v in range(self.V): if key[v] < min and mstSet[v] == False: min = key[v] min_index = v return min_index def primMST(self): key = [sys.maxsize] self.V parent = [None] self.V key[0] = 0 mstSet = [False] * self.V parent[0] = -1 for _ in range(self.V): u = self.minKey(key, mstSet) mstSet[u] = True for v in range(self.V): if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]: key[v] = self.graph[u][v] parent[v] = u self.printMST(parent)

Driver's code

if _name_ == '_main_': num_vertices = int(input("Enter the number of vertices: ")) g = Graph(num_vertices) print("Enter the adjacency matrix for the graph:") for i in range(num_vertices): row = list(map(int, input().split())) for j in range(num_vertices): g.graph[i][j] = row[j]

g.primMST()

if name == 'main': g = Graph(5) g.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]] g.primMST()