你好，我是王健伟。 这节课我们学习图的应用中的最后一个话题——关键路径问题。它解决的事估算完成某个工程所需要的最短时间的问题。说到“最短时间”，你应该就能反应过来，它是一个能帮助我们提高生产效率的算法。 我们还是从它涉及的基本概念开始说起。 “关键路...

你好，我是王健伟。 在我和你分享了两个图的应用，最小生成树和最短路径相关的算法之后，我们来说说拓扑排序。 拓扑排序主要是解决一个工程能否按顺序进行的问题。在正式讲解之前，我们首先来一起认识一下几个基本概念。 拓扑排序基本概念首先，有向无环图（Dire...

你好，我是王健伟。 上节课我和你分享了用迪杰斯特拉（Dijkstra）算法求解最短路径。除此之外，还有一个求解最短路径的方法——佛洛依德（Floyd）算法。 那他们有什么不同吗？ 如果说迪杰斯特拉算法比较适合一次性求某个顶点到其他各个顶点的最短路径信...

你好，我是王健伟。 前面我们讲解了用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法来寻找连通图的最小生成树，从而解决诸如如何修路费用最少这样的问题。这次我和你分享图的第二个实际用途——最短路径。那么，什么是最短路径呢？ 最短路径在带权图中，...

你好，我是王健伟。 上节课我带你实现了用普里姆算法寻找一个无向连通图的最小生成树，并且我们已经知道，普里姆算法比较适合顶点数比较少，边数比较多的图。 这节课我带你看一看另外一种寻找无向连通图最小生成树的方法——克鲁斯卡尔（Kruskal）算法。话不多...

你好，我是王健伟。 前面我们已经讲解了图的概念、图的存储结构以及图的遍历问题。那么你可能非常想知道图都有哪些具体的实际用途。这节课，我就和你分享图的第一个实际用途——最小生成树。 首先我们先一起看一看什么是最小生成树。 最小生成树前面我们曾经展示过生...