图及图的相关算法(附习题)

2024-01-07 17:50:47

遍历算法:

  1. 深度优先搜索(DFS)

    • 深度优先搜索是一种用于遍历或搜索树或图的算法。
    • 它通过尽可能深的遍历图的分支来实现目标,再回溯到前面的节点。
    • 通常使用递归或栈来实现。
  2. 广度优先搜索(BFS)

    • 广度优先搜索也是一种用于遍历或搜索树或图的算法。
    • 它从根节点开始,沿着树的宽度遍历树的节点,直到找到目标节点为止。
    • 通常使用队列来实现。

图的最短路径相关的算法

下面是使用表格来说明Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法和Kruskal算法的区别:

算法适用范围边权重时间复杂度空间复杂度备注
Dijkstra算法单源最短路径非负权重O((V+E)logV)O(V)适用于无向图或有向图,边权重为非负数
Bellman-Ford算法单源最短路径任意权重O(VE)O(V)可以处理边权重为负数,但不能处理负权重环
Floyd-Warshall算法所有顶点对之间的最短路径任意权重O(V^3)O(V^2)适用于有向图或无向图,可以处理负权重边,不能处理负权重环
Kruskal算法最小生成树任意权重O(ElogE) 或 O(ElogV)O(E+V)适用于无向图,边权重可以为任意值,找到最小生成树的算法

以下是Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法和Kruskal算法的计算方式的简要描述:

  1. Dijkstra算法

    • 从源节点开始,维护一个距离数组,记录从源节点到各个节点的当前最短距离。
    • 选择距离数组中最小的节点,并更新与该节点相邻的节点的距离。
    • 重复以上步骤,直到所有节点都被遍历。
    • 该算法使用优先队列来高效选择距禽数组中的最小节点。
  2. Bellman-Ford算法

    • 初始化距离数组为无穷大,源节点距离设为0。
    • 通过松弛操作,不断更新各个节点的距离,直到没有更新为止。
    • 重复上述步骤,直到所有边都被松弛。
    • 该算法可以处理边权为负数,但不能处理负权重环。
  3. Floyd-Warshall算法

    • 初始化一个二维数组来记录节点之间的最短距离,初始时该数组的值为边的权重。
    • 通过三重循环,不断更新节点之间的最短距离,直到所有节点之间的最短距离都被计算出来。
    • 该算法适用于计算所有节点对之间的最短距离,可以处理负权重边,但不能处理负权重环。
  4. Kruskal算法

    • 将所有边按照权重从小到大排序。
    • 依次选择权重最小的边,如果该边的两个节点不在同一个连通分量中,则将其加入最小生成树中。
    • 重复上述步骤,直到最小生成树中包含了所有的节点。
    • 该算法用于寻找最小生成树,可以处理任意权重的边。

习题

假设有一个有向加权图,图中的顶点用字母表示,边的权重用数字表示。我们以图中的顶点和边的信息来举一个Dijkstra算法的习题。

假设有以下有向加权图:

顶点:A, B, C, D, E

边和权重:(A, B, 4), (A, C, 2), (B, C, 5), (B, D, 10), (C, D, 3), (C, E, 2), (D, E, 4)

现在假设我们要从顶点A出发,使用Dijkstra算法来找到从A到其他顶点的最短路径和距离。我们可以按照以下步骤进行计算:

思路

  1. 初始化距离数组,将A到各个顶点的距离初始化为无穷大,A到自身的距离初始化为0。
  2. 选择A作为起始节点,更新A的邻接节点B和C的距离为A到B的距离为4,A到C的距离为2。
  3. 选择当前距离数组中距离最小的节点C,更新C的邻接节点D和E的距离为A到D的距离为5,A到E的距离为4。
  4. 选择当前距离数组中距离最小的节点B,更新B的邻接节点D的距离为A到D的距离为5。
  5. 选择当前距离数组中距离最小的节点D,更新D的邻接节点E的距离为A到E的距离为4。
  6. 所有节点的最短路径已经计算完毕,得到A到各个顶点的最短路径和距离。

这样就完成了使用Dijkstra算法来计算从A到其他顶点的最短路径和距离的过程。

具体的计算过程

当使用Dijkstra算法解决这个问题时,我们可以按照以下步骤进行计算:

  1. 初始化距离数组,将A到各个顶点的距离初始化为无穷大,A到自身的距离初始化为0。
顶点ABCDE
距离0
  1. 选择A作为起始节点,更新A的邻接节点B和C的距离:

    • A到B的距离为4
    • A到C的距离为2
顶点ABCDE
距离042
  1. 选择当前距离数组中距离最小的节点C,更新C的邻接节点D和E的距离:

    • A到D的距离为5
    • A到E的距离为4
顶点ABCDE
距离04254
  1. 选择当前距离数组中距离最小的节点B,更新B的邻接节点D的距离:

    • A到D的距离为5
顶点ABCDE
距离04254
  1. 选择当前距离数组中距离最小的节点D,更新D的邻接节点E的距离:

    • A到E的距离为4
顶点ABCDE
距离04254

这样就完成了使用Dijkstra算法来计算从A到其他顶点的最短路径和距离的过程。

文章来源:https://blog.csdn.net/weixin_44808225/article/details/135395221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。