【图】:常用图搜索(图遍历)算法

这篇具有很好参考价值的文章主要介绍了【图】:常用图搜索(图遍历)算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

概念

图遍历和图搜索是解决图论问题时常用的两种基本操作。

  • 图遍历是指从图中的某一个节点出发,访问图中所有的节点,确保每个节点都被访问到且不会重复访问。图遍历有两种主要方式:深度优先搜索(DFS)广度优先搜索(BFS)
  • 图搜索是指在图中寻找特定目标的过程。搜索可能是无目标的(即只是为了遍历整个图),也可能是有目标的,希望找到特定的节点或路径。最常用的有目标图搜索算法是Dijkstra算法(用于找到单源最短路径)和A*算法(结合了BFS和启发式搜索,用于找到最优路径)。

图遍历

深度优先搜索 (DFS)

深度优先搜索(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。它从起始顶点开始,沿着一条路径直到不能继续为止,然后返回到最近的一个未访问过的节点,继续相同的过程,直到所有节点都被访问过。

【图】:常用图搜索(图遍历)算法,数据结构,算法,图搜索算法,图遍历,DFS,BFS,Dijkstra

function DFS(node):
    if node is not visited:
        mark node as visited
        for each neighbor of node:
            DFS(neighbor)

DFS 适用场景

  • 寻找路径:DFS 在寻找路径方面非常强大,可以用于解决迷宫问题、寻找图中两个节点之间的路径等。
  • 拓扑排序:DFS 可以用于在有向图中进行拓扑排序,例如在编译器优化、任务调度等领域中应用广泛。
  • 检测环路:DFS 可以用于检测图中是否存在环路,对于拓扑排序来说,有向无环图 (DAG) 才有拓扑排序的结果。
  • 生成最小生成树:DFS 可以用于生成最小生成树,例如在 Prim 算法中。

DFS 优缺点

优点:

  1. 节省空间:相比较于 BFS,DFS 使用递归实现时,不需要额外的数据结构来保存访问状态,因此可能会更节省空间。
  2. 发现深层次的节点:DFS 会尽可能深地探索某一条分支,因此在找到目标节点或解之前,会一直沿着一条路径向下探索。

缺点:

  1. 可能陷入死循环:如果图中包含循环,且没有合适的终止条件,DFS 可能会陷入无限循环。可能

  2. 找到的不是最短路径:由于 DFS 是尽可能深地探索某一条分支,所以找到的路径不一定是最短路径。


广度优先搜索 (BFS)

广度优先搜索(Breadth First Search,BFS)也是一种用于遍历或搜索树或图的算法。它从起始顶点开始,首先访问所有与起始顶点相邻的节点,然后逐层向下访问。

【图】:常用图搜索(图遍历)算法,数据结构,算法,图搜索算法,图遍历,DFS,BFS,Dijkstra

function BFS(start):
    create a queue Q
    enqueue start into Q
    mark start as visited

    while Q is not empty:
        current = dequeue from Q
        for each neighbor of current:
            if neighbor is not visited:
                mark neighbor as visited
                enqueue neighbor into Q

BFS 适用场景

  • 寻找最短路径:BFS 可以用于寻找图中两个节点之间的最短路径,因为它会逐层扩展,所以找到的路径一定是最短的。
  • 最小生成树 (Prim 算法):BFS 也可以用于 Prim 算法中生成最小生成树的过程。

BFS 优缺点

优势:

  1. 找到最短路径:BFS 适用于需要找到最短路径的情况,因为它会优先访问距离起点更近的节点。
  2. 避免陷入死循环:BFS 通常不容易陷入死循环,因为它会逐层扩展,不会无限制地向下探索。

缺点:

  1. 可能占用更多内存:BFS 通常需要一个队列来保存待访问节点,可能会占用比DFS更多的内存。
  2. 不一定能找到最深层次的节点:BFS 在发现目标节点时,不一定会沿着一条深度较大的路径找到它。

DFS & BFS 异同点

相同点:

DFS 和 BFS 都是图遍历算法,用于访问图中的所有节点,确保每个节点都被访问到。

不同点:

  1. 搜索方式:
    - DFS:尽可能深地探索某一条分支,直到不能继续为止,然后回溯。
    - BFS:先访问与起始节点直接相邻的所有节点,然后逐层向下访问。

  2. 适用场景:
    - DFS 适用于寻找路径、拓扑排序、检测环路等问题。
    - BFS 适用于寻找最短路径、最小生成树等问题。

  3. 找到的路径:
    - DFS 找到的路径不一定是最短路径。
    - BFS 一定能找到最短路径。

  4. 空间复杂度:
    - DFS 可能会节省一些空间,特别是使用递归实现时。
    - BFS 通常会占用更多的内存,因为需要一个队列来保存待访问节点。

总的来说,选择使用DFS还是BFS取决于具体的问题和需求。如果需要寻找最短路径或最优解,通常选择BFS。如果问题需要深度搜索或者对内存消耗有限制,可能会选择DFS


图搜索

图搜索根据目标可以分为,目标节点搜索目标路径搜索。

Dijkstra算法

给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题,如下图所示。

算法思想:将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中,S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点,并加入到集合S中,并把这个点从集合T删除。直到T集合为空为止。

【图】:常用图搜索(图遍历)算法,数据结构,算法,图搜索算法,图遍历,DFS,BFS,Dijkstra

function Dijkstra(Graph, source):
    create empty set S
    create a set Q containing all nodes
    create a map distance and set distance[source] = 0
    
    while Q is not empty:
        u = node in Q with smallest distance[u]
        remove u from Q
        add u to S
        
        for each neighbor v of u:
            if distance[u] + weight(u, v) < distance[v]:
                distance[v] = distance[u] + weight(u, v)
    
    return distance

算法复杂度:

  • 设带权有向图的边数为m,顶点数为n。
    • 用数组存储顶点方式实现复杂度为: O ( n 2 ) O(n^2) O(n2)
    • 用邻接表存储 + 二叉堆实现复杂度为: O ( ( m + n ) l o g n ) O((m+n)logn) O((m+n)logn)
    • 用邻接表存储 + 斐波那契堆实现复杂度为: O ( m + n l o g n ) O(m+nlogn) O(m+nlogn)

A*算法

A*算法结合了启发式搜索和Dijkstra算法的思想,用于在加权图中找到起点到目标节点的最短路径。它使用一个启发式函数来估计从当前节点到目标节点的距离,并根据这个估计值选择下一个要扩展的节点。

适用于带有启发式函数的加权图,找到起点到目标节点的最短路径。

function AStar(Graph, source, target):
    create empty set openSet and add source to it
    create empty set closedSet
    create a map gScore and set gScore[source] = 0
    create a map fScore and set fScore[source] = heuristic(source, target)
    
    while openSet is not empty:
        current = node in openSet with lowest fScore
        if current == target:
            return reconstructPath(cameFrom, current)
        
        remove current from openSet
        add current to closedSet
        
        for each neighbor of current:
            if neighbor is in closedSet:
                continue
            tentative_gScore = gScore[current] + distance(current, neighbor)
            
            if neighbor is not in openSet or tentative_gScore < gScore[neighbor]:
                cameFrom[neighbor] = current
                gScore[neighbor] = tentative_gScore
                fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, target)
                if neighbor is not in openSet:
                    add neighbor to openSet
    
    return failure

Floyd算法

Floyd算法用于解决所有节点对之间的最短路径问题。它采用动态规划的思想,通过中间节点的遍历来更新任意两个节点之间的最短路径。

通过Floyd计算图G=(V,E)中各个顶点的最短路径时,需要引入一个矩阵S,矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

假设图G中顶点个数为N,则需要对矩阵S进行N次更新。初始时,矩阵S中顶点a[i][j]的距离为顶点 i 到顶点 j 的权值;如果 i 和 j 不相邻,则a[i][j]=∞。 接下来开始,对矩阵 S 进行N次更新

第1次更新时,如果"a[i][j]的距离" > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示" i 与 j 之间经过第1个顶点的距离"),则更新a[i][j]为"a[i][0]+a[0][j]“。 同理,第k次更新时,如果"a[i][j]的距离” > “a[i][k]+a[k][j]”,则更新a[i][j]为"a[i][k]+a[k][j]"。更新N次之后,操作完成!

【图】:常用图搜索(图遍历)算法,数据结构,算法,图搜索算法,图遍历,DFS,BFS,Dijkstra

function FloydWarshall(Graph):
    let dist be a matrix of size VxV, initialized with infinity
    for each edge (u, v) in Graph:
        dist[u][v] = weight(u, v)
    for k from 1 to V:
        for i from 1 to V:
            for j from 1 to V:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Bellman-Ford算法

Bellman-Ford算法用于在带有负权边的图中找到单源最短路径。它通过对边进行松弛操作来逐步优化到达每个节点的最短距离。解题思路就是假设有一条边 {begin,end,value} ,如果 dis[begin] + value < dis[end] ,我们可以更新 dis[end] 的值为 dis[begin] + value

Bellman-Ford不能计算有负权回路的图,因为在负权回路中,如果一直转圈的话,值就会一直变小。

【图】:常用图搜索(图遍历)算法,数据结构,算法,图搜索算法,图遍历,DFS,BFS,Dijkstra

function BellmanFord(Graph, source):
    create a list of size V called distance and set distance[source] = 0
    
    for i from 1 to V-1:
        for each edge (u, v) in Graph:
            if distance[u] + weight(u, v) < distance[v]:
                distance[v] = distance[u] + weight(u, v)
    
    for each edge (u, v) in Graph:
        if distance[u] + weight(u, v) < distance[v]:
            return "Graph contains a negative-weight cycle"
    
    return distance

SPFA算法

SPFA算法也用于在带有负权边的图中找到单源最短路径。它采用了队列来优化Bellman-Ford算法,通过动态选择要松弛的节点,减少了不必要的松弛操作,提高了算法的效率。文章来源地址https://www.toymoban.com/news/detail-743222.html

function SPFA(Graph, source):
    create a queue Q
    enqueue source into Q
    create a set visited and add source to it
    create a map distance and set distance[source] = 0
    
    while Q is not empty:
        current = dequeue from Q
        remove current from visited
        
        for each neighbor of current:
            if distance[current] + weight(current, neighbor) < distance[neighbor]:
                distance[neighbor] = distance[current] + weight(current, neighbor)
                if neighbor is not in visited:
                    enqueue neighbor into Q
                    add neighbor to visited
    
    return distance

到了这里,关于【图】:常用图搜索(图遍历)算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包