Write a program to implement topological sort.
Example 1:
Input: n=6 , edges={{1,2},{2,3},{4,3},{5,3},{6,2}}
Output: 1 4 5 6 2 3
Approach:
Java
import java.util.ArrayList;import java.util.HashMap;import java.util.LinkedList;import java.util.Queue;public class TopologicalSort {// visited listpublic static ArrayList<Integer> visited = new ArrayList<>();// traversal listpublic static ArrayList<Integer> ans = new ArrayList<>();// store the indegree of all the nodesstatic HashMap<Integer, Integer> indegre = new HashMap<>();public static void main(String[] args) {// Adjacency ListsArrayList<ArrayList<Integer>> adj = new ArrayList<>();int v = 7;for (int i = 0; i < v; i++)adj.add(new ArrayList<>());addEdge(adj, 1, 2);addEdge(adj, 2, 3);addEdge(adj, 4, 3);addEdge(adj, 5, 3);addEdge(adj, 6, 2);// bfs callingtopologicalSort(adj, v);// print traversal listans.forEach(i -> System.out.print(i + " "));}private static void topologicalSort(ArrayList<ArrayList<Integer>> adj, int v) {// create queueQueue<Integer> queue = new LinkedList<>();// if indegree of the vertex is// zero then insert into the queuefor (int i = 1; i < v; i++) {if (indegre.get(i) == null) {queue.add(i);}}// Iterate till the queue is not emptywhile (!queue.isEmpty()) {// current node from the queueint curr = queue.poll();// insert the current data into the resultans.add(curr);// iterate for all the adjacency// of the cuurent nodefor (int node : adj.get(curr)) {// decrease the indegre of the nodeindegre.put(node, indegre.getOrDefault(node, 0) - 1);// if indegree becomes zero// add into the queueif (indegre.get(node) == null|| indegre.get(node) == 0) {queue.add(node);}}}}/*** @Desc : Method used for add edges* @param u* @param v*/private static void addEdge(ArrayList<ArrayList<Integer>> g,int u, int v) {// directed graphg.get(u).add(v);// check and add indegreeindegre.put(v, indegre.getOrDefault(v, 0) + 1);}}
C++
#include <bits/stdc++.h>using namespace std;//ajdacency list to//store all the edgesvector<int> arr[100001];//store the indegree of//all the nodesint indegre[100001];//function to add the edgevoid addEdge(int u,int v){//directed grapharr[u].push_back(v);//increment the indegeeindegre[v]++;}//funtion to find the topological//sort of the graphvector<int> topologicalSort(int n){//queue to store the nodes//of the graphqueue<int> q;//store the resultvector<int> res;//if indegre of the vertex is//zero then insert into the//queuefor(int i=1;i<=n;i++){if(indegre[i]==0){q.push(i);}}//iterate till the queue is//not emptywhile(!q.empty()){//current node from the queueint curr=q.front();//insert the current data into//the resultres.push_back(curr);//popped from the queueq.pop();//iterate for all the adjacency//of the cuurent nodefor(int node:arr[curr]){//decrease the indegre of the nodeindegre[node]--;//if indegree becomes zero//add into the queueif(indegre[node]==0)q.push(node);}}//return the topological sortreturn res;}int main(){int n=6;int edges=5;addEdge(1,2);addEdge(2,3);addEdge(4,3);addEdge(5,3);addEdge(6,2);vector<int> topo=topologicalSort(n);cout<<"Topological Sort is ";for(int i=0;i<n;i++)cout<<topo[i]<<" ";return 0;}
No comments:
Post a Comment