Java Topological Sort 🎯

Welcome to our deep dive into Java Topological Sort! This lesson is designed for both beginners and intermediates, so let's get started. 🚀

What is Topological Sort? 📝

Topological Sort is a popular algorithm used for linearizing the nodes in a directed acyclic graph (DAG) with no cycles. It's a powerful tool that helps in scheduling tasks, determining the order of prerequisites in a project, and more!

Why is it useful? 💡

Topological Sort helps us understand the dependencies between different tasks or nodes in a graph. By linearizing the graph, we can find the order in which the tasks can be executed without causing any circular dependencies, ensuring a correct and efficient execution order.

Prerequisites 📝

Basic understanding of Java programming
Knowledge of data structures like ArrayList and LinkedList
Familiarity with graph traversal algorithms (Breadth-First Search and Depth-First Search)

Java Topological Sort Algorithm 💡

In Java, we can implement the Topological Sort using Depth-First Search (DFS). Here's a step-by-step breakdown of the algorithm:

Create an adjacency list to represent the graph.
Initialize an ArrayList called indegree to store the incoming edges for each node.
Run Depth-First Search (DFS) to find the nodes with zero indegree (also known as topological sorted order nodes). Remove these nodes from the graph and their neighbors' indegree by one. Repeat this step until all nodes are processed.
If no nodes are found with zero indegree, the graph contains cycles and cannot be topologically sorted.

Code Example 💻

Here's a complete, working example of the Topological Sort algorithm in Java:

java

import java.util.*;

class Graph {
    Map<Integer, List<Integer>> adjacencyList;
    Map<Integer, Integer> indegree;

    Graph(int vertices) {
        adjacencyList = new HashMap<>();
        indegree = new HashMap<>();

        for (int i = 0; i < vertices; i++) {
            adjacencyList.put(i, new ArrayList<>());
            indegree.put(i, 0);
        }
    }

    void addEdge(int src, int dest) {
        adjacencyList.get(src).add(dest);
        indegree.put(dest, indegree.get(dest) + 1);
    }

    List<Integer> topologicalSort() {
        List<Integer> topologicallySorted = new ArrayList<>();

        List<Integer> zeroIndegreeNodes = getZeroIndegreeNodes();

        while (!zeroIndegreeNodes.isEmpty()) {
            int node = zeroIndegreeNodes.remove(0);
            topologicallySorted.add(node);

            for (int neighbor : adjacencyList.get(node)) {
                if (--indegree.get(neighbor) == 0) {
                    zeroIndegreeNodes.add(neighbor);
                }
            }
        }

        if (topologicallySorted.size() != adjacencyList.size()) {
            System.out.println("Graph contains cycles and cannot be topologically sorted.");
        }

        return topologicallySorted;
    }

    List<Integer> getZeroIndegreeNodes() {
        List<Integer> zeroIndegreeNodes = new ArrayList<>();

        for (int key : indegree.keySet()) {
            if (indegree.get(key) == 0) {
                zeroIndegreeNodes.add(key);
            }
        }

        return zeroIndegreeNodes;
    }
}

Practice 💻

Now that you've learned about Java Topological Sort, let's test your knowledge with a quiz:

Keep practicing and happy coding! 🤓💻💪