Category Archives: Graph

Topological Sort

Topological sorting for a graph is not possible if the graph is not a DAG.

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.vertices = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)

def getDegree(graph, vertices):
    degrees = [0]*vertices
    for v in graph:
        for vv in graph[v]:
            degrees[vv] += 1
    return degrees

BFS TopologicalSort

def topologicalSort(graph) :
    indegrees = getDegree(graph.graph, graph.vertices)
    visited = set()
    path = []
    for v in range(graph.vertices):
        #print(v)
        if indegrees[v] == 0:
            bfs_ts(graph.graph, v, visited, path)
    return path

import collections
def bfs_ts(graph, v, visited, path):
    queue = collections.deque()
    queue.append(v)
    visited.add(v)
    while queue:
        v = queue.popleft()
        path.append(v)
        for nei in graph[v]:
            if nei not in visited:
                visited.add(nei)
                queue.append(nei)
# If vertices left, indegree ==0 will add the path

DFS TopologicalSort

def topologicalSort(graph):
    degree = getDegree(graph.graph, graph.vertices)
    visited = set()
    path = []
    for v in range(graph.vertices):
        if degree[v] == 0:
            dfs_ts(graph.graph, v, visited, path)
    return path[::-1]

def dfs_ts(graph, v, visited, path):
    visited.add(v)
    for nb in graph[v]:
        if nb not in visited:
            dfs_ts(graph, nb, visited, path)
    path.append(v)

Test topologicalSort

myGraph = Graph(5)
myGraph.addEdge(0, 1)
myGraph.addEdge(0, 3)
myGraph.addEdge(1, 2)
myGraph.addEdge(2, 3)
myGraph.addEdge(2, 4)
myGraph.addEdge(3, 4)

print(topologicalSort(myGraph)) # [0, 1, 2, 3, 4]

myGraph = Graph(6)
myGraph.addEdge(5, 2)
myGraph.addEdge(5, 0)
myGraph.addEdge(4, 0)
myGraph.addEdge(4, 1)
myGraph.addEdge(2, 3)
myGraph.addEdge(3, 1)

print(topologicalSort(myGraph))  # [5, 4, 2, 3, 1, 0]"