Топологическая сортировка:
Это линейное упорядочение вершин графа таким образом, что если существует ребро из u и v, то u должно быть раньше v в упорядочении.
Примечание:
- Топологическая сортировка применима только к направленному графу.
- Мы не можем иметь топологическую сортировку, если направленный граф имеет цикл. Так как он не будет удовлетворять определению топологической сортировки.
Подход DFS:
Временная сложность :O(N+E) и пространственная сложность : O(N)+O(N)+O(N)+O(N)+O(N) = O(N)*4 (Вспомогательное пространство стека для рекурсивного вызова, N для посещенного массива, N для массива результатов и 4-е N для стека).
/*Complete the function below*/
/*Topological sorting:
* A linear ordering of vertices such that if there is an edge between u->v, then
u appears before v in the ordering
*/
class Solution
{
//Function to return list containing vertices in Topological order.
static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj)
{
//we will use depth first search for this
//we have to make sure that u appears before v , if there is
//an edge between u and v
//hence using depth first search would be a better approach.
Stack<Integer> stack = new Stack<>();
int visited[] = new int[V];
for(int i =0;i<V;i++){
if(visited[i] ==0){
dfs(i,visited,stack,adj);
}
}
int result[] = new int[V];
int index =0;
while(!stack.isEmpty()){
result[index] = stack.pop();
index++;
}
return result;
}
public static void dfs(int node, int[] visited,Stack<Integer> stack, ArrayList<ArrayList<Integer>> adj){
visited[node] = 1;
for(Integer i: adj.get(node)){
if(visited[i] ==0){
dfs(i,visited,stack,adj);
}
}
stack.push(node);
}
}
BFS подход к топологической сортировке: Использование алгоритма Кана
Временная сложность : O(N+E) и пространственная сложность будет O(n)*3 для однородного массива, очереди и массива результатов.
/*Complete the function below*/
class Solution
{
//Function to return list containing vertices in Topological order.
static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj)
{
//we will use Kahn's algorithm for getting topological sorting, it uses
//breadh first search algorithm
// we will be required to calculate the indegree of all the nodes;
int indegree[] = new int[V];
/// calculating indegrees of all the nodes
for(int i =0;i<V;i++){
for(Integer j : adj.get(i)){
indegree[j]++;
}
}
Queue<Integer> q = new LinkedList<>();
//putting those nodes in the queue whose indegrees are 0
//because these are the nodes that have no incoming edge to them hence they
//can be at the start of the topological sorting as it will not cause any issue
//because we are maintaining order of u followed by v where u->v (u has edge directed towards v)
for(int i =0;i<V;i++){
if(indegree[i]==0){
q.add(i);
}
}
int result[] = new int[V];
int index =0;
while(!q.isEmpty()){
Integer i = q.remove();
result[index++] = i;
for(Integer node : adj.get(i)){
// here we re reducing the indegrees as the nodes that are alredy there
// the queue are getting removed hence there edges with the node 'node' will
//also be removed hence there indegrees will decrease by one
indegree[node]--;
//and as soon as there indegrees becomes 0 means they are independent now and they have no incoming edge to them
//hence they can be added to queue just like we did earlier.
if(indegree[node]==0){
q.add(node);
}
}
}
return result;
}
}