Blog Details

Topological Sort

package com.frank.sort;

import java.util.LinkedList;

public class Graph {
	private int v; // number of vertex 
	private LinkedList<Integer> adj[]; // adjacent list
	
	@SuppressWarnings("unchecked")
	public Graph(int v) {
		this.v = v;
		adj = new LinkedList[v];
		for (int i = 0; i < v; i ++) {
			adj[i] = new LinkedList<Integer>();
		}
	}
	
	public void addEdge(int s, int t) {
		adj[s].add(t);
	}
	
	public int getV() {
		return v;
	}
	
	public void topoSortByKahn() {
		int[] inDegree = new int[v];
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < adj[i].size(); j ++) {
				int w = adj[i].get(j);
				inDegree[w] ++;
			}
		}
		
		LinkedList<Integer> queue = new LinkedList<Integer>();
		for (int i = 0; i < v; i ++) {
			if (inDegree[i] == 0) queue.add(i);
		}
		
		while (!queue.isEmpty()) {
			int i = queue.remove();
			System.out.print("->" + i);
			for (int j = 0; j < adj[i].size(); j++) {
				int k = adj[i].get(j);
				inDegree[k] --;
				if (inDegree[k] == 0) {
					queue.add(k);
				}
			}
		}
	}
	
	// DFS - Topological Sort
	public void topoSortByDFS() {
		// Create inverted linked list
		@SuppressWarnings("unchecked")
		LinkedList<Integer> inversedAdj[] = new LinkedList[v];
		
		for (int i = 0; i < v; i ++) {
			inversedAdj[i] = new LinkedList<Integer>();
		}
		
		for (int i = 0; i < v; i ++) {
			for (int j = 0; j < adj[i].size(); j ++) {
				int w = adj[i].get(j);
				inversedAdj[w].add(i);
			}
		}
		
		boolean[] isVisited = new boolean[v];
		
		for (int i = 0; i < v; i ++) {
			if (isVisited[i] == false) {
				isVisited[i] = true;
				dfs(i, inversedAdj, isVisited);
			}
		}
	}
	
	private void dfs(int vertex, LinkedList<Integer> inversedAdj[], boolean[] isVisited) {
		for (int i = 0; i < inversedAdj[vertex].size(); i++) {
			int w = inversedAdj[vertex].get(i);
			if (isVisited[w] == true) {
				continue;
			}
			isVisited[w] = true;
			dfs(w, inversedAdj, isVisited);
		}
		System.out.print("->" + vertex);
	}
}