【图】：常用图搜索（图遍历）算法

概念

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

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

图遍历

深度优先搜索 (DFS)

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

function DFS(node):
    if node is not visited:
        mark node as visited
        for each neighbor of node:
            DFS(neighbor)
1
2
3
4
5

DFS 适用场景

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

DFS 优缺点

优点:

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

缺点:

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

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

---

广度优先搜索 (BFS)

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

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
1
2
3
4
5
6
7
8
9
10
11

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集合为空为止。

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

算法复杂度：

• 设带权有向图的边数为m，顶点数为n。
  • 用数组存储顶点方式实现复杂度为：$O(n^2)$
  • 用邻接表存储 + 二叉堆实现复杂度为：$O((m+n)logn)$
  • 用邻接表存储 + 斐波那契堆实现复杂度为：$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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

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次之后，操作完成！

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
1
2
3
4
5
6
7
8
9
10

---

Bellman-Ford算法

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

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

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
1
2
3
4
5
6
7
8
9
10
11
12
13

---

SPFA算法

SPFA算法也用于在带有负权边的图中找到单源最短路径。它采用了队列来优化Bellman-Ford算法，通过动态选择要松弛的节点，减少了不必要的松弛操作，提高了算法的效率。

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---