Find ranking with topological sorting – DFS and BFS

Find ranking with topological sorting is to find winner and ranking in tournament. Topological sorting is a graph traversal in which node v is visited only after all its dependencies are visited. The graph has to be directed and has no cycles, aks directed acyclic graph (DAG). Once the graph is built, we can use the algorithms to find the order. The result is not necessary unique.


topo sort dfs and bfs

The algorithms of topological sorting are depth first search (DFS) and breadth first search(BFS). They both have linear time O(V+E), V is number of vertices, E is number of edges. Topological sort are usually applied to ranking and scheduling problems. Here is an example to find tournament ranking.

Facebook Interview Question:
(Modified) In a tennis tournament of N players. The following condition always hold-If player P1 has won the match with P2 and player P2 has won from P3, then Player P1 has also defeated P3. Find winner and ranking of players.


Solution 1. DFS with stack

This algorithm based on depth first search is using the data structure stack this time. For each node and its followers (or losers in this example), call the recursion helper. For any node returns from call stack, put it in the stack. The reverse of the stack is the final sorted result.

Java

JavaScript

Python

Doodle

topo sort dfs doodle


Solution 2. BFS with queue

This is also known as Kahn’s algorithm. First find a list of start nodes which has no incoming edges, ie indegree is 0. Insert them into a queue. Then pull out items from the queue, update and check its followers (or losers in this example)’ indegrees. If the indegree is 0, add to the queue. Repeat until all nodes are checked. The sequence pulled from the queue is the final sorted result.

Java

JavaScript

Python

Doodle

topo sort bfs doodle

Output:
{P1=[P5], P2=[P5], P3=[P2], P4=[P3, P1], P5=[]}
Topological sort dfs: [P4, P3, P2, P1, P5]
Topological sort bfs: [P4, P3, P1, P2, P5]

O Notation:
Time complexity: O(V+E)
Space complexity: O(V)
V is number of nodes, E is number of edges

What algorithms can be used for topological sorting?

Topological sorting is used in graph (more specifically, directed acyclic graph DAG). It can be solved using depth first search(stack or recursion) and breadth first search (more specifically, Kahn’s algorithm). They both have time complexity O(V+E) and space complexity O(V). V is number of nodes (vertices), E is number of edges.


Download


Download FindRankingWithTopoSort.java
Download FindRankingWithTopoSort.js
Download FindRankingWithTopoSort.py
Big O notation cheat sheet DFS and BFS

Comments are closed