认识达内从这里开始

对于大多数软件编程开发程序员来说，掌握的编程算法越多，在遇到不同的编程开发需求的时候能够使用的解决方法也越多，而本文我们就通过案例分析来简单了解一下，常见的软件开发算法都有哪些类型。

一、图遍历(GraphTraversals)

遍历图的问题是指以特定顺序访问所有节点，通常沿途计算其他有用信息。

广度优先搜索(Breadth-FirstSearch)

广度优先搜索(BFS)算法是确定图是否连通的常用方法之一——或者换句话说，查找BFS源节点的连通分量。

BFS还用于计算源节点和所有其他节点之间的短距离。BFS的另一个版本是Lee算法，用于计算网格中两个单元格之间的短路径。

该算法先访问源节点，然后访问将被推入队列的邻居。队列中的一个元素被弹出。我们将访问它的所有邻居，并将之前未访问的邻居推入队列。重复该过程直到队列为空。当队列为空时，表示所有可达顶点都已访问完毕，算法结束。

深度优先搜索(Depth-FirstSearch)

深度优先搜索(DFS)算法是另一种常见的遍历方法。在检查图形的连通性时，它实际上是好的选择。

先，我们访问根节点并将其压入堆栈。虽然堆栈不为空，但我们检查顶部的节点。如果该节点有未访问的邻居，则选择其中一个并将其压入堆栈。否则，如果它的所有邻居都被访问过，我们就会弹出这个节点。当堆栈变空时，算法结束。

经过这样的遍历，就形成了一个DFS树。DFS树有很多应用;常见的一种是存储每个节点的“开始”和“结束”时间——它进入堆栈的时刻，分别是它从堆栈中弹出的时刻。

二、弗洛依德算法(Floyd-Warshall)

Floyd-Warshall/Roy-Floyd算法解决了所有对短路径问题：找到给定边加权有向图中每对顶点之间的短距离。

FW是一个动态规划应用程序。DP结构(矩阵)dist[][]用输入图矩阵初始化。然后我们将每个顶点视为其他两个节点之间的中间体。短路径在每两对节点之间更新，任何节点k作为中间顶点。如果k是i和j之间排序路径中的中间值，则dist[i][j]成为dist[i][k]+dist[k][j]和dist[i][j]之间的大值。

时间复杂度：O(n³)

空间复杂度：O(n²)

三、Dijkstra算法和Bellman-Ford算法

迪杰斯特拉(Dijkstra)算法

给定一个图和图中的一个源顶点，找出从源到给定图中所有顶点的短路径。

Dijkstra算法用于在加权图中找到这样的路径，其中所有的权重都是正的。

Dijkstra是一种贪心算法，它使用以源节点为根的短路径树(SPT)。SPT是一种自平衡二叉树，但该算法可以使用堆(或优先级队列)来实现。我们将讨论堆解决方案，因为它的时间复杂度是O(|E|*log|V|)。这个想法是使用图形的邻接列表表示。这样，节点将使用BFS(广度优先搜索)在O(|V|+|E|)时间内遍历。

所有顶点都用BFS遍历，那些短距离尚未终确定的顶点被存储到小堆(优先队列)中。

创建小堆并将每个节点连同它们的距离值一起推入其中。然后，源成为距离为0的堆的根。其他节点将无限分配为距离。当堆不为空时，我们提取小距离值节点x。对于与x相邻的每个顶点y，我们检查y是否在小堆中。在这种情况下，如果距离值大于(x,y)的权重加上x的距离值，那么我们更新y的距离值。

贝尔曼-福特(Bellman-Ford)算法

正如我们之前所说，Dijkstra仅适用于正加权图。贝尔曼解决了这个问题。给定一个加权图，我们可以检查它是否包含负循环。如果没有，那么我们还可以找到从我们的源到其他源的小距离(可能为负权重)。

Bellman-Ford非常适合分布式系统，尽管它的时间复杂度是O(|V||E|)。

我们初始化一个dist[]就像在Dijkstra中一样。对于*|V|-1次，对于每个(x,y)边，如果dist[y]>dist[x]+(x,y)的权重，那么我们用它更新dist[y]。

我们重复后一步以可能找到负循环。这个想法是，如果没有负循环，后一步保证小距离。如果有任何节点在当前步骤中的距离比上一步中的距离短，则检测到负循环。

四、克鲁斯卡尔算法(Kruskal’sAlgorithm)

我们之前已经讨论过什么是小生成树。

有两种算法可以找到图的MST：Prim(适用于密集图)和Kruskal(适用于大多数图)。现在我们将讨论Kruskal算法。

Kruskal开发了一种贪心算法来寻找MST。它在稀有图上很有效，因为它的时间复杂度是O(|E|*log|V|)。

该算法的方法如下：我们按权重的递增顺序对所有边进行排序。然后，选取小的边。如果它不与当前MST形成循环，我们将其包括在内。否则，丢弃它。重复后一步，直到MST中有|V|-1条边。

将边包含到MST中是使用Disjoint-Set-Union完成的，这也在前面讨论过。

五、拓扑排序(TopologicalSorting)

有向无环图(DAG)只是一个不包含循环的有向图。

DAG中的拓扑排序是顶点的线性排序，使得对于每个拱形(x,y)，节点x出现在节点y之前。

显然，拓扑排序中的一个顶点是一个入度为0的顶点(没有拱形指向它)。

另一个特殊属性是DAG没有的拓扑排序。

BFS(广度优先搜索)实现遵循此例程：找到一个入度为0的节点并将一个推入排序。该顶点已从图中删除。由于新图也是一个DAG，我们可以重复这个过程。

在DFS期间的任何时候，节点都可以属于以下三个类别之一：

我们完成访问的节点(从堆栈中弹出);

当前在堆栈上的节点;

尚未发现的节点。

如果在DAG中的DFS期间，节点x具有到节点y的输出边，则y属于一类或三类。如果y在堆栈上，则(x,y)将结束一个循环，这与DAG定义相矛盾。

这个属性实际上告诉我们一个顶点在它的所有传出邻居都被弹出后从堆栈中弹出。因此，要对图进行拓扑排序，我们需要跟踪弹出顶点的逆序列表。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。