吃包子引发的问题……
今天早上，小豆吃了十个包子，然后感慨了一句，早知道吃第十个包子能吃饱，我直接吃第十个就好了，前面还能省下九个。
emmm……
在实际生活中，有很多事情存在先后的依赖性，就像前面吃了九个包子，第十个包子才能吃饱。穿衣服时，先穿内衣再穿外套。在学校里，需要学完A课程和B课程，然后才能选修C课程。
那么我们如果通过两两课程之间的关系，找出修完所有的课程的完整关系呢？
这个问题就是一个拓扑排序的问题，很像在图中寻找一条路径，从起点到终点，每一步像一个节点走到另一个节点。
但是拓扑排序得到的最后序列一定是唯一的吗？
来看一下吃包子的问题，第十个包子吃饱了建立在前九个包子的基础上，但是前九个包子什么顺序吃，并不是确定的。你可以先吃第一个，也可以先吃第二个，反正最后是要把前九个吃完，吃第十个才会饱。拓扑排序的结果并不是唯一的。
我们可以使用有向图表示顶点之间的关系，还有一点，这必须是一个有向无环图，如果存在环，那么就会进入死循环，拓扑排序就凉凉了。
我们先来看看第一种实现的算法——Kahn 算法，这种方法是使用了贪心的思想，思路极其简单。
假设当 s 需要在 t 之前执行时，我们就添加一条 s 指向 t 的边，如果一个顶点的入度为 0 ，那么没有任何事情要在这个顶点之前执行，它就可以执行了。
要做的就是寻找入度为 0 的节点，然后把它们打印出来，这个顶点达到的下一个顶点的入度减一操作。然后以这些顶点为基础的顶点，最后会变成入度为 0 的顶点，我们重复上面的操作，直到所有顶点都被打印输出一遍。这时候输出的序列就是满足依赖关系的序列。
这里做了两次不同的代码比较，发现了一些不一样的东西。
使用数组加链表的数据结构存放数据。当 s 指向 t 时，有两种不同的存储方式，t 的链表中添加 s，或者 s 的链表中 添加 t。
先来瞅瞅 t 中添加 s 的代码。
class GraphMe { public int v;// 顶点数量 public LinkedList<Integer>[] adj; public GraphMe(int v) { this.v = v; adj = new LinkedList[v]; for (int i = 0; i < v; i++) { adj[i] = new LinkedList(); } } public void add(int s, int t) { adj[t].add(s);// t 中添加 s } }
拓扑排序实现代码
public void topoSort(GraphMe graph) { int v = graph.v; int[] status = new int[v]; Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < v; i++) { status[i] = graph.adj[i].size(); if (status[i] == 0) { queue.add(i); } } while (!queue.isEmpty()) { int temp = queue.poll(); System.out.println(temp); for (int i = 0; i < v; i++) { if (status[i] != 0) { if (graph.adj[i].contains(temp)) { status[i]--; if (status[i] == 0) { queue.add(i); } } } } } }
再来瞅瞅 s 中添加 t 的代码实现
public class Graph { public int v;// 顶点数量 public LinkedList<Integer>[] adj; public Graph(int v) { this.v = v; adj = new LinkedList[v]; for (int i = 0; i < v; i++) { adj[i] = new LinkedList(); } } public void add(int s, int t) { adj[s].add(t);// s 中添加 t } }
对应的排序代码
public void topoSort(Graph graph) { int v = graph.v; // 统计节点的入度数量 int[] status = new int[v]; for (int i = 0; i < v; i++) { List<Integer> list = graph.adj[i]; for (int j = 0; j < list.size(); j++) { status[list.get(j)]++; } } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < v; i++) { if (status[i] == 0) { queue.add(i); } } while (!queue.isEmpty()) { int k = queue.poll(); System.out.println(k); List<Integer> list = graph.adj[k]; for (int temp : list) { if (--status[temp] == 0) { queue.add(temp); } } }
看起来好像差别也没那么大，emmm……
另外就是还可以使用 DFS 算法，通过深度优先遍历，遍历图中所有的顶点，这个下次一定实现……
如果存在环的情况下，那么怎么判断顶点之间存在环呢？
