博客

上一遍分析了如何设计任务管理系统的算法，

拓扑排序之任务管理系统思路设计

。

今天我们就利用Kahn’s algorithm for Topological Sorting来实现任务管理系统算法。

设计一个数据结构Graph类来储存各个task之间的依赖关系，并根据每个task相互的依赖关系找出任务排列顺序。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Graph {
	private int V;    // No. of vertices
	private int minimumLevel;
	private int tasksInLevel;    // store the number of tasks in the same level
	private List<ArrayList<Integer>> adj;
	private List<String> tasks;
	private boolean isUnique = true;
	private boolean isCircle = false;
	private Queue<Integer> mCircleQueue = new LinkedList<Integer>();   // store the circle tasks in order
	private boolean isFound = false;    // If we find circle, then isFound is true
	
	public Graph() {
		this.V = 0;
		adj = new ArrayList<ArrayList<Integer>>();
		tasks = new ArrayList<String>();
	}
	
	public Graph(String loadTasks[]) {
		this.V = loadTasks.length;
		adj = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < V; i++) {
			adj.add(new ArrayList<Integer>());
		}
		tasks = new ArrayList<String>();
		for(String task : loadTasks) {
			tasks.add(task);
		}
	}
	
	public void addTask(String s) {
		if(!tasks.contains(s)) {
			adj.add(new ArrayList<Integer>());
			this.V++;
			tasks.add(s);
		} else {
			System.out.println("Task " + s + " is already in the system, please add another task or quit.");
		}
	}
	
	// Add dependency for last added task
	public void addDependency(String s) {
		if(!tasks.contains(s)) {
			System.out.println("Task " + s + " is not in the system, pl