拓扑排序

Q：不知道你是否也曾苦恼于生物里的求食物链数目的题目。如果现在任意给你一个食物网，你能用程序来求出这个食物网中食物链的数量吗？

A：你初次看到这个题目时，也许会不知从何下手。但如果你之前对拓扑排序有所了解的话，你会发现这个题目其实很好解决。数一条食物链，往往从生产者入手，即那些只能被吃的生物，给这些生产者们每人一个初始权重1，给那些能够食用这些生产者的动物，送去他们能食用的所有植物，每食用一种，就在他们的初始权重0的基础上加上这种植物的权重。把生产者们从食物链中去掉，你会发现食物链中又多了一批只能被别人吃的可怜生物，我们可以把它们当成新的生产者，然后重复上述步骤，直到最后遍历完所有的生物。

最后把*消费者身上的权重加起来，你会发现这个数字恰好就是食物网中食物链的总数。再回过头去看，你会发现，我们每次只去掉那些只能被吃的生物的操作，恰恰保证了我们我们遍历了所有可能的食物链，不多也不少，倘若在某次操作中不小心去掉了某个还能吃别人的生物，我们最后得到的结果肯定会偏小。

这就是拓扑排序的思想。

把一个食物网等效成一个有向图（其实它本来就是????），我们可以把初始入度为0的点存储在一个队列中，每次从队首弹出一个元素，把它指向的点的入度都-1，倘若减1之后该点的入度变成了0，那么我们把这个点也放进队列中，不断进行，直到最后队列为空，这就是拓扑排序。

Dijkstra算法

Dijkstra算法是一种求单源最短路径的算法

所谓求单源最短路径，就是求一个点到其他点的最短距离。它是与多源最短路径相对的一个概念，多源最短路径就是求每一点到其他点的最短路径

Dijkstra算法运用了贪心的策略：即每次都选最短的那条路径。

算法的基本思想：从源点（我姑且把要求的点命名为源点）开始，找出从该点延伸出去的所有路径中最短的那一条，我们可以肯定这条路径肯定是源点到路径另外一头的那个顶点（命名为A点）的最短路径，我们可以使这两点重合，并且给从A点延伸出去的所有路径，都加上刚刚因为两点重合而消失的那段路径，我们会发现这样操作并没有改变原有的路径长度，紧接着我们再从源点延伸出去的路径中找到最短的那一条，重复上述操作，最终便可以得到从源点到其他点的最短路径。

再回过头来看，发现我们其实根本没必要使两点重合，我们只需要给这些点做一个标记，标记已经求出来到它的最短路径，然后在选取最短路径的时候，把到这些已经求出最短路径的点排除在外即可。

Prim算法

Prim算法是一种求最小生成树的算法。最小生成树就是图的所有生成树中权值最小的那一颗树。

Prim算法和Dijkstra算法非常相似，它们都是从某一点出发，寻找到其他点的最短路径，然后把离他最近的点加入到树中，并用该点来更新到其他点的最短距离，不断重复该过程，直到把所有点都加入到树中。

你只需要在每次求得最小距离时，把相应的边的信息进行输出，最后便能得到一颗最小生成树。

你可能会很困惑？为什么这样求得的一颗树就是最小生成树呢？

我们可以利用反证法来证明这个算法的正确性。

因为我们每次选择的边都是相应的最短权值边。我们可以假设这条边不在最小生成树中。那么我们往最短生成树中加入这条最短权值边，一定会形成一个环，我们很容易发现最短权值边必定不是这个环里最长的边。也就是说，我们去掉环里的最长边，得到的树是比最小生成树要更小的，这与最小生成树的概念相矛盾。

Floyd算法

我们之前讲过Dijkstra算法，它是一种求单源最短路径的算法。而Floyd是一种求多元最短路径的算法。

Floyd算法的思想很简单。我们知道在一个图中，一个点到另外一个点的最短距离有两种可能：一种通过直接相连的路径到达另一个点，一种经由其他的点到达另一个点。直接相连的最短路径很简单，我们只需要考虑经由其他点的最短路径。

Floyd算法通过遍历来实现，先看看任意两点之间能不能通过第一点缩小两点之间的距离，如果更小，则更新这两点的距离；再看看能不能通过第二点缩小两点之间的距离，更小则更新，不断重复，直到遍历完所有顶点。最后我们存储的两点之间的距离就是两点之间的最小距离。

你可能还是有一点小困惑。倘若第一点到第六点的最短距离，需要从第一点先到第四点，最后再到第六点，用上述算法肯定是正确的。但是倘若最短距离是先从第一点到第八点，再到第六点，这样去更新得到的结果还正确吗？其实我们在遍历第八个点的时侯，同样会去判断第一点到第六点的路径是否能通过经由第八点而变得更小。倘若第一点到第六的的最短路径是先从第一点到第八点，再到第四点，最后到第六点，这样我们在遍历第八点时，会更新第一点到第四点的最短距离，紧接着会更新第一点到第六点的最短距离（因为我们会在遍历第四点的时候得到从第八点到第六点的最短距离，那么就可以通过第八点来更新第一点到第六点的最短距离）

一个点经由一些其他的点到另一个点，并且使得两点距离最小，这些其他的点要么出现一次，要么不出现。而我们对每一个点都进行了尝试，看其他点之间的距离能否通过该点使得距离变得更小，这就确保了算法的正确性。

如果您觉得我的文章对您有帮助的话，可以点个赞，点个关注，也可以扫描下方二维码关注我。我将在这个公众号上更新自己的学习笔记，以及分享一些算法知识

Study and progress together with me!