不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

拓扑排序

拓扑排序可以用来检测是否又环,或者顺序执行任务。
当输出的入度为0的结点数量小于 总的结点数量,说明存在环。

Java Demo

package algorithm;

/**
 * @Author laijinhan
 * @date 2021/7/21 下午10:42
 */

import java.util.*;

/**
 * 实现拓扑排序
 */
public class TuopuSort {
	public void getAnswer(HashMap<String, V> directedGraph) {
		// 优先队列,入度为0的顶点入队,按字典顺序排序
		PriorityQueue<V> queue = new PriorityQueue<>((a, b) -> a.name.compareTo(b.name));
		for (V value : directedGraph.values()) {
			if (value.inDegree == 0) {
				queue.offer(value);
			}
		}
		while (!queue.isEmpty()) {
			V poll = queue.poll();
			System.out.print(poll.name + " ");
			for (E e : poll.adjEdges) {
				if (--e.endV.inDegree == 0) {
					queue.offer(e.endV);
				}
			}
		}
	}

	/**
	 * 第一行输入一个正整数N。
	 * 接下来N行,每行一个字符串,分别表示每个任务的名称
	 * 再接下来N行,每行首先输入一个整数M,然后输入M个整数i:表示有M 个约束,i 表示第i个函数 是 当前函数的依赖
	 * 必须先完成依赖的函数,当有多个函数可以被同时实现的时候,按照字典序的顺序来实现函数。
	 * 10
	 * K
	 * A
	 * B
	 * C
	 * D
	 * E
	 * F
	 * G
	 * H
	 * I
	 * 0
	 * 0
	 * 2 1 1
	 * 1 2
	 * 1 3
	 * 1 4
	 * 1 5
	 * 1 6
	 * 1 7
	 * 1 8
	 * ====================
	 * 3
	 * B
	 * C
	 * A
	 * 1 1
	 * 0
	 * 1 1
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
        
        //  构造拓扑排序的有向图
		HashMap<String, V> directedGraph = new HashMap<>();

		String[] labels = new String[n];
		for (int i = 0; i < n; i++) {
			String s = sc.nextLine();
			labels[i] = s;
			directedGraph.put(s, new V(s));

		}
		for (int i = 0; i < n; i++) {// i 表示结束结点
			String[] temp = sc.nextLine().split(" ");
			V endNode = directedGraph.get(labels[i]);
			for (int j = 1; j < temp.length; j++) { // 表示开始结点
				V startNode = directedGraph.get(labels[Integer.parseInt(temp[j])]);
				startNode.adjEdges.add(new E(endNode));
				directedGraph.get(labels[i]).inDegree++;// 指向那个结点入度+1;
			}
		}
        
		new TuopuSort().getAnswer(directedGraph);
	}
}

/**
 * V表示开始顶点,adjEdges里面包含指向的顶点
 * 指向A->B的含义是,完成B必须先完成A
 */
class V {
	String name;// 顶点的名字
	List<E> adjEdges;// 顶点相关的边,当前顶点为开始顶点,数组里面包含的是结束的顶点
	int inDegree;// 顶点的入度

	public V(String name) {
		this.name = name;
		this.inDegree = 0;
		adjEdges = new LinkedList<E>();
	}
}

class E {
	V endV;
	public E(V endV) {
		this.endV = endV;
	}
}


目录