KahnsAlgorithm

KahnsAlgorithm.java

import java.util.*;

public class KahnsAlgorithm {
    public static void main(String[] args) {
        // Graph representation (adjacency list)
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            adjList.add(new ArrayList<>());
        }

        // Adding edges: A->B, A->C, B->D, C->D
        adjList.get(0).add(1);
        adjList.get(0).add(2);
        adjList.get(1).add(3);
        adjList.get(2).add(3);

        List<Integer> result = topologicalSort(adjList, 4);

        // Print the topological order
        for (int i : result) {
            System.out.print((char) ('A' + i) + " ");
        }
    }

    public static List<Integer> topologicalSort(List<List<Integer>> adjList, int numCourses) {
        int[] inDegree = new int[numCourses];
        for (List<Integer> edges : adjList) {
            for (int edge : edges) {
                inDegree[edge]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> topilogicalOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int course = queue.poll();
            topilogicalOrder.add(course);

            for (int nextCourse : adjList.get(course)) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    queue.add(nextCourse);
                }
            }
        }

        if (topilogicalOrder.size() != numCourses) {
            throw new IllegalArgumentException("Cycle detected in the graph");
        }

        return topilogicalOrder;
    }
}