LintCode 127 · Topological Sorting.java

Topological Sorting:
note that: "BFS with indegree."

	/**
	* Definition for Directed graph.
	* class DirectedGraphNode {
	* int label;
	* List<DirectedGraphNode> neighbors;
	* DirectedGraphNode(int x) {
	* label = x;
	* neighbors = new ArrayList<DirectedGraphNode>();
	* }
	* }
	*/
	public class Solution {
	/**
	* @param graph: A list of Directed graph node
	* @return: Any topological order for the given graph.
	*/
	public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
	// write your code here
	ArrayList<DirectedGraphNode> orders = new ArrayList<>();
	if (graph == null || graph.size() == 0) {
	return orders;
	}
	Map<DirectedGraphNode, Integer> indegree = new HashMap<>();
	for (DirectedGraphNode node : graph) {
	for (DirectedGraphNode neighbor : node.neighbors) {
	if (indegree.containsKey(neighbor)) {
	indegree.put(neighbor, indegree.get(neighbor) + 1);
	} else {
	indegree.put(neighbor, 1);
	}
	}
	}
	Queue<DirectedGraphNode> queue = new ArrayDeque<>();
	for (DirectedGraphNode node : graph) {
	if (!indegree.containsKey(node)) {
	queue.add(node);
	}
	}
	while (!queue.isEmpty()) {
	DirectedGraphNode node = queue.poll();
	orders.add(node);
	for (DirectedGraphNode neighbor : node.neighbors) {
	if (indegree.containsKey(neighbor)) {
	indegree.put(neighbor, indegree.get(neighbor) - 1);
	if (indegree.get(neighbor) == 0) {
	queue.add(neighbor);
	indegree.remove(neighbor);
	}
	}
	}
	}
	return orders;
	}
	}

view raw 127 · Topological Sorting.java hosted with ❤ by GitHub