from collections import defaultdict, deque class DirectedGraph: def __init__(self, nodes): self.adjList = [[] for _ in range(nodes)] self.nodes = nodes def addEdge(self, source, destination): self.adjList[source].append(destination) def displayGraph(self): for node, adjNodes in enumerate(self.adjList): print(node, "-> ", adjNodes) def inDegreeZeroNodes(self): nodesToIndegree = [0] * self.nodes for adjNodes in self.adjList: for node in adjNodes: nodesToIndegree[node] += 1 # print(nodesToIndegree) return nodesToIndegree def isCyclicGraphUsingDfs(self): visited = set() pathVisited = set() def checkCycle(node): visited.add(node) pathVisited.add(node) for adjNode in self.adjList[node]: if adjNode in visited: if adjNode in pathVisited: return True else: if checkCycle(adjNode) == True: return True pathVisited.remove(node) return False for i in range(self.nodes): if checkCycle(i) == True: return True return False def isCyclicGraphUsingBfs(self): in_degree = self.inDegreeZeroNodes() visitedNodesCount = 0 q = deque([]) for i in range(len(in_degree)): if in_degree[i] == 0: q.append(i) while q: node = q.popleft() visitedNodesCount += 1 for adjNode in self.adjList[node]: in_degree[adjNode] -= 1 if in_degree[adjNode] == 0: q.append(adjNode) if visitedNodesCount == self.nodes: return False return True def topologicalSortUsingBfs(self): indegree = [0] * self.nodes for adjNodes in self.adjList: for node in adjNodes: indegree[node] += 1 q = deque([]) for i in range(len(indegree)): if indegree[i] == 0: q.append(i) output = [] while q: node = q.popleft() output.append(node) for adjNode in self.adjList[node]: indegree[adjNode] -= 1 if indegree[adjNode] == 0: q.append(adjNode) return output def topologicalSortUsingDfs(self): def dfs(node): visited[node] = True for adjNode in self.adjList[node]: if visited[adjNode] == False: dfs(adjNode) stack.append(node) stack = [] visited = [False] * self.nodes for n in range(self.nodes): if visited[n] == False: dfs(n) return stack[::-1] def topologicalSortUsingDfs(self): def dfs(node): visited.add(node) for adjNode in self.adjList[node]: if adjNode not in visited: dfs(adjNode) stack.append(node) visited = set() stack = [] for n in range(self.nodes): if n not in visited: dfs(n) return stack[::-1] g = DirectedGraph(6) g.addEdge(5,0) g.addEdge(5,2) g.addEdge(2,3) g.addEdge(3,1) g.addEdge(4,0) g.addEdge(4,1) # g.displayGraph() # print(g.isCyclicGraphUsingDfs()) # print(g.isCyclicGraphUsingBfs()) # print(g.topologicalSortUsingBfs()) # print(g.topologicalSortUsingDfs()) class UndirectedGraph: def __init__(self, nodes) -> None: self.nodes = nodes self.adjList = [[] for _ in range(nodes)] def addEdge(self, source, destination): self.adjList[source].append(destination) self.adjList[destination].append(source) def displayGraph(self): for node, adjNodes in enumerate(self.adjList): print(node, " -> ", adjNodes) def isCyclicGraphUsingDfs(self): def checkCycle(node, parent): visited[node] = True for adjNode in self.adjList[node]: if not visited[adjNode]: if checkCycle(adjNode, node): return True elif adjNode != parent: return True return False visited = [False] * self.nodes for n in range(self.nodes): if not visited[n] and checkCycle(n, -1): return True return False def shortestPathUsingDijkstra(self, source, destination): q = deque([source]) distance = [float('inf')] * self.nodes distance[source] = 0 visited = set([source]) while q: node = q.popleft() if node == destination: print(distance) return distance[node] for neighbor in self.adjList[node]: if neighbor not in visited: distance[neighbor] = distance[node] + 1 q.append(neighbor) visited.add(neighbor) # path = [] # current = destination # while current != 0: # path.append(current) # current = parent[destination] # print(path) return -1 v = 8 e = 10 edges = [ [0,1], [1,2], [0,3], [3,4], [4,7], [3,7], [6,7], [4,5], [4,6], [5,6] ] ug = UndirectedGraph(v) for i in range(e): source, destination = edges[i] ug.addEdge(source, destination) # ug.addEdge(0, 2) # ug.addEdge(0, 3) # ug.addEdge(1, 2) # ug.addEdge(3, 4) ug.displayGraph() # print(ug.isCyclicGraphUsingDfs()) print(ug.shortestPathUsingDijkstra(2, 6))