Let's assume that we have some tasks to do, and each of the tasks has some dependencies that mean that the dependent tasks should be done first before doing the actual task. The problem arises when we have an interrelationship between tasks and dependencies. Now, we need to come up with a proper order for completing the tasks. We need a special type of sorting so that we can sort these connected tasks without violating our rules for finishing the tasks. Topological sorting will be the right choice for solving such problems. In topological sorting, a directed edge AB from vertex A to B is sorted in such a way that A will always come before B in the ordering. This will be applicable for all the vertices and edges. Another important factor for applying a topological sort is that the graph must be a DAG. Any DAG has at least one topological sorting. Most of the time, there are multiple topological sortings that are possible for a given graph. There are two popular algorithms available for topological sorting: Kahn's algorithm and the DFS approach. We will talk about Kahn's algorithm here as we have already discussed DFS a few times in this book.

Kahn's algorithm has the following steps to find the topological ordering from a DAG:

1. Calculate the indegree (incoming edges) for each of the vertex and put all vertices in a queue where the indegree is 0. Also, initialize the count for the visited node to 0.

2. Remove a vertex from the queue and perform the following operations on it:

1. Increment the visited node count by 1.

2. Reduce the indegree for all adjacent vertices by 1.

3. If the indegree of the adjacent vertex becomes 0, add it to the queue.

3. Repeat step 2 until the queue is empty.
4. If the count of the visited node is not the same as the count of the nodes, then topological sorting is not possible for the given DAG.

Let's consider the following graph. It is a perfect example of DAG. Now, we want to sort it using topological sorting and Kahn's algorithm:

Now let us represent this graph using an adjacency matrix as we did previously for the other graphs. The matrix will look as follows:

$graph = [ 
    [0, 0, 0, 0, 1], 
    [1, 0, 0, 1, 0], 
    [0, 1, 0, 1, 0], 
    [0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0], 
];

Now, we will implement Kahn's algorithm as per our defined steps. Here is the implementation for it:

function topologicalSort(array $matrix): SplQueue { 
    $order = new SplQueue; 
    $queue = new SplQueue; 
    $size = count($matrix); 
    $incoming = array_fill(0, $size, 0); 


    for ($i = 0; $i < $size; $i++) { 
      for ($j = 0; $j < $size; $j++) { 
          if ($matrix[$j][$i]) { 
          $incoming[$i] ++; 
          } 
      } 
      if ($incoming[$i] == 0) { 
          $queue->enqueue($i); 
      } 
    } 

    while (!$queue->isEmpty()) { 
      $node = $queue->dequeue(); 

      for ($i = 0; $i < $size; $i++) { 
          if ($matrix[$node][$i] == 1) { 
            $matrix[$node][$i] = 0; 
            $incoming[$i] --; 
            if ($incoming[$i] == 0) { 
                $queue->enqueue($i); 
            } 
          } 
      } 
      $order->enqueue($node); 
    } 

    if ($order->count() != $size) // cycle detected 
      return new SplQueue; 

    return $order; 
} 

As we can see from the preceding implementation, we have actually considered every step we mentioned for Kahn's algorithm. We started by finding the indegree for vertices and also putting the 0 indegree vertices in a queue. Then, we checked each node of the queue and reduced the indegree of the neighbor vertices and again added any neighbor with 0 indegrees to the queue. At the end, we returned the sorted queue, or an empty queue if the count of ordered vertices and actual vertices count does not match. We can now call the function to return the sorted list of vertices as a queue. Here is the code to do this:

$sorted = topologicalSort($graph);

while (!$sorted->isEmpty()) {
    echo $sorted->dequeue() . "	";
} 

Now, this will go through each of the queue elements and print them. The output will look like this:

    2       1       0       3       4

The output corresponds to our expectations. As we can see from the earlier diagram, vertex 2 has a direct edge to vertex 1 and vertex 3, and vertex 1 has a direct edge to vertex 0 and vertex 3. Since vertex 2 has no incoming edges, we will start from vertex 2 for the topological sorting. Vertex 1 has one incoming edge and vertex 3 has two, so, after vertex 2, we will visit vertex 1 as per the algorithm. The same principle will take us to vertex 0 followed by vertex 3 and at the end to vertex 4. We have to also remember that there can be multiple topological orderings possible for a given graph. The complexity of Kahn's algorithm is O (V+E), where V is the number of vertices and E is the number of edges.