kahns algorithm long Algorithm

Kahn's algorithm, also known as topological sorting, is an efficient algorithm used to linearly order the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex 'u' comes before vertex 'v' in the ordering. This linear ordering of vertices is called a topological order, and it is particularly useful in scheduling tasks with dependencies, determining the sequence of courses to take in a curriculum, or many other applications where a partial order needs to be respected. The algorithm works by iteratively selecting vertices with no incoming edges, removing them from the graph, and adding them to the linear order. Initially, the algorithm starts by identifying all vertices with no incoming edges and adds them to a set or queue. Then, it repeatedly removes a vertex from the set, appends it to the topological order, and removes all its outgoing edges. After removing the outgoing edges, any vertices that now have no incoming edges are added to the set. This process continues until either all vertices are added to the topological order or the set becomes empty (which indicates that the graph has a cycle and a topological order is not possible). The algorithm's time complexity is O(V+E), where V represents the number of vertices and E represents the number of edges in the graph.
# Finding longest distance in Directed Acyclic Graph using KahnsAlgorithm
def longestDistance(graph):
    indegree = [0] * len(graph)
    queue = []
    longDist = [1] * len(graph)

    for key, values in graph.items():
        for i in values:
            indegree[i] += 1

    for i in range(len(indegree)):
        if indegree[i] == 0:
            queue.append(i)

    while queue:
        vertex = queue.pop(0)
        for x in graph[vertex]:
            indegree[x] -= 1

            if longDist[vertex] + 1 > longDist[x]:
                longDist[x] = longDist[vertex] + 1

            if indegree[x] == 0:
                queue.append(x)

    print(max(longDist))


# Adjacency list of Graph
graph = {0: [2, 3, 4], 1: [2, 7], 2: [5], 3: [5, 7], 4: [7], 5: [6], 6: [7], 7: []}
longestDistance(graph)

LANGUAGE:

DARK MODE: