图论算法

发表于 | 更新于 | 计算机技术

图论问题渗透整个计算机科学，图算法对于计算机学科至关重要。成百上千的计算问题最后都可以归约为图论问题。

基本概念

路径path 是一个顶点序列，$w_1,w_2,w_3, \cdots,w_N, \text{其中}(w_i,w_{i+1}) \isin E,1 \le i < N$，这条路径的长 length 是该路径上的边数，$length = N-1$。如果有一个顶点到它自身的路径：如路径不包含边，则长度为0，若包含边，那么路径(v,v)称作环 loop 。简单路径：路径上的所有顶点都互异，但允许第一个顶点和最后一个顶点相同。

在有向图中，回路(cycle) 是满足$w_1=w_N$且长度至少为1，如果该路径是简单路径那么这个回路就是简单回路。我们要求无向图的边是互异的（理由：无向图中(u,v)和(v,u)是同一条边，因此u,v,u不应该被认为是回路，但是在有向图中，(u,v)与(v,u)是不同的边，因此回路有意义）。如果一个有向图没有回路，则称其为无环的(acyclic)，有向无环图DAG(directed acyclic graph)。

连通性connectedness ：如果无向图中每个顶点到每个其他顶点都存在一条路径，则称该无向图是连通的（connected）。如果是这样的有向图，称该有向图是强连通的(strongly connected)，如果有向图不是强连通的，但是他的基础图（弧上去掉方向所形成的图）是连通的，则称该有向图是弱连通的(weakly connected)。完全图是每一对顶点间都存在一条边的图。

图的表示

  1. 邻接矩阵（Adjacency Matrix） ：用一个二维数组来表示图，对于有 $n$个顶点的图，邻接矩阵是一个 $n×n$ 的矩阵 $A$。如果 $A[i][j]=1$（或者边的权重值，对于加权图），表示顶点$i$ 和顶点 $j$ 之间有边相连（有向图中表示有从 $i$ 到 $j$ 的边）；如果 $A[i][j]=0$，则表示它们之间无边相连。优点是判断两点之间是否有边很方便，缺点是对于稀疏图（边的数量相对顶点数量很少的图）会浪费较多空间。
  2. 邻接表（Adjacency List） ：采用链表（或者动态数组等数据结构）来存储与每个顶点相邻的顶点。对于每个顶点，都有一个对应的链表（或列表），链表中存储的是与该顶点相邻的其他顶点。这种存储方式比较节省空间，尤其适合稀疏图，不过查询两顶点间是否有边相对邻接矩阵效率略低一些，需要遍历相应顶点的邻接链表。

图的遍历

深度优先搜索

深度优先搜索 (DFS, Depth-First Search): 从一个起始节点开始，尽可能深入地访问图中的节点，直到没有未访问的相邻节点，再回溯。常通过递归或者使用栈来辅助实现。例如遍历一个迷宫。它可以用于判断图的连通性、寻找图中的环等应用场景。

python

# 递归实现DFS
def DFS(graph, node, visited):
    if node not in visited:
        print(node)  # 访问当前节点
        visited.add(node)  # 标记当前节点为已访问
        for neighbor in graph[node]:
            DFS(graph, neighbor, visited)

DFS的应用

  1. 图的连通性检查 ：DFS可以用来判断一个图是否是连通图。如果从一个节点出发能够遍历到所有其他节点，则图是连通的。
  2. 寻找图中的强连通分量 (Kosaraju算法) ：对于有向图，可以使用DFS来寻找强连通分量，即图中每两个节点都是可达的子图。Kosaraju算法就是基于DFS来找强连通分量的。
  3. 拓扑排序 ：在有向无环图（DAG）中，DFS可以用来进行拓扑排序。具体方法是：从每个未访问的节点进行DFS，递归完成后将节点加入到一个栈中，最后逆序输出栈中的元素即可得到拓扑排序。
  4. 路径和环的检测 ：DFS可以用来检测图中是否存在环。例如，在DFS过程中，如果遇到一个节点已经在当前递归栈中，则说明图中存在环。
  5. 迷宫问题：经典的迷宫问题（如寻找从起点到终点的路径）可以用DFS来解决。DFS可以沿着一条路径不断探索，直到找到出口，或者回溯到上一个节点继续尝试其他路径。
  6. 生成树 DFS可以用来生成图的生成树（特别是树的深度优先遍历）。它可以帮助在无向图或有向图中构造树形结构。
  7. 寻找所有连通分量 ：对于一个无向图，DFS可以用来寻找所有的连通分量。每次从未访问的节点开始执行DFS，找到一个新的连通分量。
  8. 解图的路径问题：在一些图的应用中，例如航班网络、社交网络等，DFS可以用来寻找路径，或者计算路径的长度、寻找最短路径的近似解。
  9. 图着色问题：在图着色问题中，DFS可以用来尝试为图的节点着色，检查图是否是可着色的。

时间复杂度：对于一个图，DFS的时间复杂度通常为 $ O(V + E) $， 空间复杂度：DFS的空间复杂度通常为 $O(V)$，因为需要存储访问过的节点以及递归调用栈。

优点：实现简单，尤其是递归版本。在处理图的连通性、拓扑排序、强连通分量等问题时非常有效。 缺点：可能会在深度较深的图中导致栈溢出，尤其是在递归实现中。不适合用于寻找最短路径（比如在带权图中，Dijkstra算法通常更适合）。

cpp

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

// DFS的递归实现
void DFS(const vector<vector<int>>& graph, int node, unordered_set<int>& visited) {
    // 输出当前访问的节点
    cout << node << " ";

    // 标记当前节点为已访问
    visited.insert(node);

    // 遍历所有相邻的节点
    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {  // 如果相邻节点没有被访问过
            DFS(graph, neighbor, visited);
        }
    }
}

int main() {
    // 图的邻接表表示，假设图有5个节点，编号从0到4
    vector<vector<int>> graph = {
        {1, 2},     // 节点0与节点1和2相邻
        {0, 3},     // 节点1与节点0和3相邻
        {0, 3},     // 节点2与节点0和3相邻
        {1, 2, 4},  // 节点3与节点1,2和4相邻
        {3}         // 节点4与节点3相邻
    };

    unordered_set<int> visited;  // 用于记录访问过的节点

    cout << "DFS遍历结果: ";
    DFS(graph, 0, visited);  // 从节点0开始DFS
    cout << endl;

    return 0;
}

广度优先搜索

广度优先搜索 (BFS, Breadth-First Search): 从一个起始节点开始，先访问所有相邻节点，再逐层访问其他节点。通常借助队列来实现。常用于计算最短路径、判断图的连通分量等。

伪代码：

python

def BFS(graph, start):
    visited = set()  # 用集合记录访问过的节点
    queue = [start]  # 队列初始化，加入起始节点

    while queue:
        node = queue.pop(0)  # 从队列中取出一个节点
        if node not in visited:
            print(node)  # 访问当前节点
            visited.add(node)  # 标记节点为已访问

            # 将所有未访问的邻接节点加入队列
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
  1. 最短路径问题（无权图）BFS在无权图中是解决单源最短路径问题的理想选择。因为BFS按照层次逐步扩展，首次到达某个节点时的路径即为最短路径。
  2. 图的连通性检查：BFS可以用来检查一个图是否连通。通过从一个节点开始执行BFS，如果所有节点都能被访问到，则图是连通的。
  3. 查找两点间的最短路径：在无权图中，BFS能够找到从起始节点到目标节点的最短路径。适用于需要快速计算最短路径的情况。
  4. 层次遍历：BFS常用于树或图的层次遍历问题。例如，可以用BFS遍历一个树的每一层，或者用来计算从某个节点开始的图的距离。

优点：可以找到无权图中的最短路径。实现简单，适用于层次结构和分层搜索问题。缺点：由于需要存储大量的节点，可能会消耗较多的内存，尤其是在图比较稠密时。不适用于带权图中的最短路径问题（在有权图中，Dijkstra算法通常更合适）。

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// BFS的实现
void BFS(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;  // 用于记录访问过的节点
    queue<int> q;  // 使用队列来存储待访问节点

    q.push(start);  // 将起始节点加入队列

    while (!q.empty()) {
        int node = q.front();  // 获取队列中的第一个节点
        q.pop();  // 移除该节点

        if (visited.find(node) == visited.end()) {
            cout << node << " ";  // 输出当前访问的节点
            visited.insert(node);  // 标记为已访问

            // 将所有未访问的邻接节点加入队列
            for (int neighbor : graph[node]) {
                if (visited.find(neighbor) == visited.end()) {
                    q.push(neighbor);
                }
            }
        }
    }
}

int main() {
    // 图的邻接表表示，假设图有5个节点，编号从0到4
    vector<vector<int>> graph = {
        {1, 2},     // 节点0与节点1和2相邻
        {0, 3},     // 节点1与节点0和3相邻
        {0, 3},     // 节点2与节点0和3相邻
        {1, 2, 4},  // 节点3与节点1,2和4相邻
        {3}         // 节点4与节点3相邻
    };

    cout << "BFS遍历结果: ";
    BFS(graph, 0);  // 从节点0开始BFS
    cout << endl;

    return 0;
}

输出：

text

BFS遍历结果: 0 1 2 3 4

在这个例子中，BFS从节点0开始，访问节点的顺序为 0 → 1 → 2 → 3 → 4，按照广度优先的顺序进行遍历。

最小生成树

最小生成树（MST, Minimum Spanning Tree） 是一个无向加权图的子图，它包含图中的所有节点，并且这些节点通过最少的边连接起来，使得图中的边权之和最小。简单来说，最小生成树是一个连通的子图，它包含了所有的节点，但只选择了一部分边，且边的总权值最小。

  1. 包含所有节点：最小生成树包含原图中的所有节点。
  2. 连接性：最小生成树是一个连通图，所有的节点都是通过某些边连接的。
  3. 边的数量：对于一个有 $V$ 个节点的图，最小生成树有 $ V-1$ 条边，因为它是一个树结构，没有环，并且保证了所有节点是连通的。
  4. 最小权值和：最小生成树的边权之和是所有生成树中最小的。

在电信、计算机网络、交通等领域，最小生成树用于设计低成本的网络连接。比如，设计一个城市的最短电力传输线路，或者计算机网络的最短路径等。在计算机视觉领域，最小生成树被用于图像分割，连接图像的像素，确保图像的相似区域在树的同一分支中。在机器学习中，最小生成树可用于对数据点进行聚类，形成相似的数据点群组。

Kruskal算法

Kruskal算法的核心思想是“贪心算法”，它每次选择最小的边来扩展生成树，并且保证不会形成环。常用的数据结构是 并查集（Union-Find） 来检测环。

 1. 将所有边按权值排序。
 2. 从权值最小的边开始，检查加入该边后是否会形成环。如果不会，加入该边；如果会，则跳过这条边。
 3. 重复这个过程，直到树包含所有节点（即 $V-1$ 条边）。
cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// 边的结构体
struct Edge {
    int u, v, weight;
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
    bool operator<(const Edge &e) const {
        return weight < e.weight;  // 按边的权值排序
    }
};

// 并查集类
class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);  // 初始化父节点为自身
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    bool unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;  // 如果两个节点已经在同一集合中，返回false

        // 按秩合并，较小的树挂到较大的树下面
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        return true;
    }

private:
    vector<int> parent;
    vector<int> rank;
};

void Kruskal(int V, vector<Edge> &edges) {
    sort(edges.begin(), edges.end());  // 按权值升序排序边

    UnionFind uf(V);  // 初始化并查集
    int mstWeight = 0;  // 最小生成树的权值和
    vector<Edge> mstEdges;  // 存储最小生成树的边

    for (auto &edge : edges) {
        if (uf.unionSets(edge.u, edge.v)) {
            mstWeight += edge.weight;
            mstEdges.push_back(edge);
        }
    }

    cout << "最小生成树的权值和: " << mstWeight << endl;
    cout << "最小生成树的边: " << endl;
    for (auto &edge : mstEdges) {
        cout << edge.u << " - " << edge.v << " 权重: " << edge.weight << endl;
    }
}

int main() {
    int V = 6;  // 节点数
    vector<Edge> edges = {
        {0, 1, 4},
        {0, 2, 4},
        {1, 2, 2},
        {1, 3, 5},
        {2, 3, 3},
        {2, 4, 6},
        {3, 4, 7},
        {3, 5, 4},
        {4, 5, 2}
    };

    Kruskal(V, edges);
    return 0;
}

Kruskal算法的代码解析

补充：并查集

Union-Find（并查集）数据结构是处理不相交集合的合并与查询问题的一种高效数据结构，也常被称为 “disjoint-set data structure”（不相交集合数据结构）

并查集的实现是基于数组的，可以用一个数组 parent[] 来存储每个元素的父节点（初始时元素的父节点就是它自己，表示各自为独立集合）。比如 parent[3] 存储的是 3 这个元素的父元素。
通过不断访问元素的父元素，直到找到根元素（即父元素是自己的那个元素）为止实现查找操作。例如查找元素 x 所在集合的代表元素，代码示例如下：

python

def find(x):
    while x!= parent[x]:
        x = parent[x]
    return x

先找到两个要合并的集合的代表元素（通过查找操作），然后将其中一个代表元素的父节点设置为另一个代表元素，实现集合合并。示例代码如下：

python

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x!= root_y:
        parent[root_y] = root_x

优化一：按秩合并（Union by Rank）：

python

rank = [0] * n  # n是元素总个数，初始化秩都为0

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x!= root_y:
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

优化二：路径压缩（Path Compression）：
在执行查找操作时，当找到根元素后，可以顺便把沿途访问的元素的父节点直接修改为根元素，这样下次再查找这些元素所在集合时就能更快地找到根元素，相当于把查找路径进行了压缩，减少了树的高度。示例代码如下：

python

def find(x):
    if x!= parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

路径压缩主要目的是加速后续的查找操作，并查集中的每个元素都有一个 父节点，如果一个节点是其集合的根节点，则它的父节点指向自己。在查找（find）操作中，我们沿着父节点链向上遍历，直到找到根节点。每次执行 find 操作时，都需要沿着树走一段路径，而这段路径的长度会影响查找的效率。随着多个合并操作的进行，树可能会变得非常高（树的深度很大），这样每次查找一个元素时，都需要花费较长的时间。因此，我们希望减少树的高度，使得每次查找都更加高效。
路径压缩的核心思想是：在查找操作过程中，将路径上的所有节点直接指向根节点。这样做的目的是减小树的高度，以便加速后续的查找操作。通过路径压缩，每次执行 find 操作时，我们不仅找到根节点，还让查找路径上的每个节点都直接指向根节点，从而使得树的高度变小。

plaintext

      6
     /
    5
   /
  4
 /
3
/
2
/
1 (root)

如果我们执行 find(6)，我们会沿着父节点链查找到根节点 1。在传统的并查集实现中，每次查找时都需要遍历整个链条，直到找到根节点。然而，路径压缩的目的是让每个经过的节点都指向根节点，从而在下次查找时直接返回根节点。

在执行路径压缩后，树会变成这样：

plaintext

      1
     /|\
    2 3 4 5 6

现在，find 操作的时间复杂度几乎是常数时间，因为我们通过路径压缩把树变得非常扁平，所有节点直接指向根节点。
在并查集的 find 操作中，路径压缩是在递归的过程中实现的。具体来说，就是每次查找某个元素时，除了返回根节点，还会在返回的过程中，把路径上的每个节点的父节点指向根节点。

cpp

// 查找操作，路径压缩
int find(int x) {
    if (parent[x] != x) {
        // 递归查找父节点，直到找到根节点
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];  // 返回根节点
}

假设我们有如下的并查集，节点 0、1、2、3 最初是独立的，后来我们进行了 union(0, 1) 和 union(1, 2)，最终的父节点链如下：

plaintext

parent = [0, 0, 0, 3]

这意味着：

如果我们调用 find(2)，按照传统方式，递归查找会从 2 开始，先访问 1，然后访问 0，最后返回 0。在路径压缩的情况下，我们还会将路径上的每个节点的父节点直接指向根节点。执行完 find(2) 后，路径上的节点 1 和 2 的父节点都会直接指向 0。

执行后的 parent 数组变成：

plaintext

parent = [0, 0, 0, 3]

这个过程简化了树的结构，减少了后续查找时需要遍历的节点数。

通过路径压缩，find 操作的时间复杂度接近 $O(\alpha(N))$，其中 $\alpha$ 是 阿克曼函数的反函数，增长速度非常慢，几乎可以认为是常数时间。通过按秩合并，union 操作的时间复杂度同样是 $O(\alpha(N))$。 在大部分应用中，使用并查集处理的问题可以在接近常数时间内完成。

cpp

#include <iostream>
#include <vector>
#include <numeric>  // iota 用于初始化

using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);  // 初始化父节点为自身
    }

    // 查找操作，路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    // 合并操作，按秩合并
    bool unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;  // 已经在同一个集合中，不需要合并

        // 按秩合并，秩小的树挂到秩大的树下面
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;  // 如果秩相同，选择一棵作为根，并增加其秩
        }
        return true;
    }

private:
    //每个节点的父节点。如果某个节点是集合的根节点，它指向自己。
    vector<int> parent;  // parent[i]表示i的父节点
    //每个节点的秩（树的深度），用于优化合并操作
    vector<int> rank;    // rank[i]表示以i为根的树的深度
};

int main() {
    int n = 7;  // 元素个数
    UnionFind uf(n);

    uf.unionSets(0, 1);  // 合并集合 {0} 和 {1}
    uf.unionSets(1, 2);  // 合并集合 {0, 1} 和 {2}
    uf.unionSets(3, 4);  // 合并集合 {3} 和 {4}
    uf.unionSets(4, 5);  // 合并集合 {3, 4} 和 {5}

    cout << "Find(0): " << uf.find(0) << endl;  // 输出 0
    cout << "Find(1): " << uf.find(1) << endl;  // 输出 0
    cout << "Find(2): " << uf.find(2) << endl;  // 输出 0
    cout << "Find(3): " << uf.find(3) << endl;  // 输出 3
    cout << "Find(5): " << uf.find(5) << endl;  // 输出 3

    uf.unionSets(2, 3);  // 合并集合 {0, 1, 2} 和 {3, 4, 5}

    cout << "Find(5) after union: " << uf.find(5) << endl;  // 输出 0
    return 0;
}

Prim算法

Prim算法是另一种基于贪心思想的算法，它通过逐步扩展最小生成树，逐步添加与已有生成树最短的边。

  1. 从一个起始节点开始，将其加入生成树。
  2. 用一个优先队列（通常使用最小堆）来维护所有与生成树相连的边，并且按照边的权重从小到大排序。
  3. 每次选择权重最小的边，加入到生成树中，并更新与新加入节点相连的所有边的权重。
  4. 重复该过程，直到生成树包含所有节点。
cpp

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 边的结构体
struct Edge {
    int v, weight;
    Edge(int v, int weight) : v(v), weight(weight) {}
};

void Prim(int V, vector<vector<Edge>> &graph) {
    vector<int> dist(V, INT_MAX);  // 记录节点到最小生成树的最小距离
    vector<bool> inMST(V, false);  // 标记节点是否在最小生成树中
    dist[0] = 0;  // 从节点0开始
    int mstWeight = 0;  // 最小生成树的权值和

    // 使用优先队列（最小堆），按权重升序排列
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});  // (权重, 节点)

    while (!pq.empty()) {
        int u = pq.top().second;  // 当前节点
        int weight = pq.top().first;  // 当前节点的边的权重
        pq.pop();

        if (inMST[u]) continue;  // 如果节点已经在最小生成树中，跳过

        inMST[u] = true;  // 将当前节点加入最小生成树
        mstWeight += weight;  // 更新最小生成树的权值和

        // 遍历当前节点的所有邻接节点
        for (auto &edge : graph[u]) {
            int v = edge.v;
            int edgeWeight = edge.weight;

            // 如果通过当前节点更新邻接节点的最短距离
            if (!inMST[v] && edgeWeight < dist[v]) {
                dist[v] = edgeWeight;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "最小生成树的权值和: " << mstWeight << endl;
}

int main() {
    int V = 6;  // 节点数
    vector<vector<Edge>> graph(V);

    // 构建图，graph[u] 存储与节点 u 相连的所有边
    graph[0].push_back(Edge(1, 4));
    graph[0].push_back(Edge(2, 4));
    graph[1].push_back(Edge(0, 4));
    graph[1].push_back(Edge(2, 2));
    graph[1].push_back(Edge(3, 5));
    graph[2].push_back(Edge(0, 4));
    graph[2].push_back(Edge(1, 2));
    graph[2].push_back(Edge(3, 3));
    graph[2].push_back(Edge(4, 6));
    graph[3].push_back(Edge(1, 5));
    graph[3].push_back(Edge(2, 3));
    graph[3].push_back(Edge(4, 7));
    graph[3].push_back(Edge(5, 4));
    graph[4].push_back(Edge(2, 6));
    graph[4].push_back(Edge(3, 7));
    graph[4].push_back(Edge(5, 2));
    graph[5].push_back(Edge(3, 4));
    graph[5].push_back(Edge(4, 2));

    Prim(V, graph);
    return 0;
}

算法总结

特性 Kruskal算法 Prim算法
基本思想 从边出发，按权值排序，逐步选择边加入生成树。 从节点出发，逐步扩展最小生成树，选择最小边。
数据结构 使用并查集（Union-Find）来管理节点的连通性。 使用优先队列（最小堆）来选择最小权边。
适用场景 边稀疏的图。 节点数较小且密集的图。
时间复杂度 $ O(E \log E)$ 或 $ O(E \log V) $ $O(E \log V) $
实现简便性 比较简单，易于实现。 较为复杂，需要维护优先队列。

网络设计：假设我们有多个城市，需要建立一条最低成本的道路网络连接所有城市。我们可以将城市看作图中的节点，道路看作图中的边，边的权重代表修建该道路的费用。使用最小生成树算法（例如Kruskal或Prim算法），我们可以得到一条最小成本的道路网络。

图像分割：在计算机视觉中，最小生成树常用于图像分割问题。将图像中的像素看作图的节点，像素之间的相似度（例如色彩相似度）作为边的权重。使用最小生成树算法可以将图像划分为不同的区域。

电力或通信网络：在电力传输和通信网络中，最小生成树算法可以帮助我们设计低成本的电力输送线路或通信线路，使得网络中的每个节点都能与其他节点连接，且总成本最小。

欧拉回路

欧拉回路（Eulerian Circuit）指的是在一个图中，能够通过每条边恰好一次，并且从起点回到终点的一个闭合路径。
如果一个图存在欧拉回路，那么我们称这个图是 欧拉图。
对于无向图，图中存在欧拉回路的充要条件是：

  1. 无向图存在欧拉回路的判定条件：

    • 图是连通的（即任意两个顶点之间都存在路径相连）。
    • 图中每个顶点的度（与该顶点相连的边的数量）都是偶数。因为要能每条边只走一次且回到起点，进入一个顶点的次数和离开一个顶点的次数必然要相等，所以每个顶点相连的边数得是偶数才行。

  2. 有向图存在欧拉回路的判定条件：

    • 图是强连通的（即对于图中任意两个顶点 $u$ 和 \$v$，既有从 $u$到 $v$ 的有向路径，也有从 $v$ 到 $u$ 的有向路径）。
    • 图中每个顶点的入度（指向该顶点的边的数量）和出度（从该顶点出发的边的数量）相等。这是因为沿着有向边行进时，进入顶点和离开顶点的次数得匹配，才能遍历所有边后回到起点。

欧拉路径（Eulerian Path）：是通过图中每条边恰好一次的路径，但不要求回到起点。一个图中可能存在欧拉路径，但不一定存在欧拉回路。存在欧拉路径的条件是：图是连通的，且恰好有两个节点的度数为奇数，其余节点的度数是偶数。如果图有欧拉回路，那么它肯定也有欧拉路径。

  1. 一笔画问题：经典的“一笔画”游戏其实就是在判断一个图形对应的图是否存在欧拉回路或者欧拉路径（欧拉路径是经过每条边一次且仅一次，但不要求回到起始点的路径，判定条件和欧拉回路稍有不同），比如判断一个复杂的迷宫图形能不能一笔画成，通过判断其对应的图是否满足欧拉回路或路径的条件就能知晓。
  2. 路线规划：在物流配送中，如果要让送货车辆遍历所有送货地点之间的道路各一次（假设道路都需要走一遍且能走通），且最后回到出发点，就可以借助欧拉回路相关知识来设计最优路线；还有像在景区规划游览路线，让游客能走过所有景点间的通道且回到起点，也可以利用其原理进行设计。
  3. 电路布线检测：在电路中，把各个电子元件的连接点看作顶点，导线看作边，判断是否能通过一种连续的检测方式遍历所有导线一次且回到起点，来检测电路布线是否符合预期等情况，可通过欧拉回路相关理论来辅助分析。

以下是一个简单的欧拉回路判断与构造的实现框架。

cpp

#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

class Graph {
public:
    int V;
    vector<list<int>> adj;

    Graph(int V) : V(V) {
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图
    }

    //判断图是否包含欧拉回路。首先检查所有节点的度数是否是偶数，如果有节点的度数是奇数，则返回 `false`。然后检查图是否是连通的（忽略没有边的节点）。
    bool isEulerianCycle() {
        // 1. 所有节点的度数必须是偶数
        for (int i = 0; i < V; i++) {
            if (adj[i].size() % 2 != 0) {
                return false; // 存在奇数度的节点
            }
        }

        // 2. 检查图是否是连通的
        if (!isConnected()) {
            return false;
        }

        return true;
    }

    //检查图是否连通。通过深度优先搜索（DFS）遍历所有节点，如果所有有边的节点都被访问到，则图是连通的。
    bool isConnected() {
        vector<bool> visited(V, false);
        dfs(0, visited);

        for (int i = 0; i < V; i++) {
            if (adj[i].size() > 0 && !visited[i]) {
                return false;
            }
        }
        return true;
    }

    void dfs(int v, vector<bool>& visited) {
        visited[v] = true;
        for (int u : adj[v]) {
            if (!visited[u]) {
                dfs(u, visited);
            }
        }
    }

    void eulerianCycle() {
        if (!isEulerianCycle()) {
            cout << "没有欧拉回路" << endl;
            return;
        }

        stack<int> path;
        list<int> circuit;
        path.push(0);

        while (!path.empty()) {
            int u = path.top();
            if (!adj[u].empty()) {
                int v = adj[u].front();
                adj[u].remove(v);  // 移除边
                adj[v].remove(u);  // 无向图，删除反向边
                path.push(v);
            } else {
                circuit.push_front(u);
                path.pop();
            }
        }

        cout << "欧拉回路：";
        for (int v : circuit) {
            cout << v << " ";
        }
        cout << endl;
    }
};

int main() {
    Graph g(5);

    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 0);

    g.eulerianCycle();

    return 0;
}

拓扑排序

拓扑排序(Topological Sort)是一种专门用于 DAG（有向无环图）的顶点的排序，使得每条边的起点在排序序列中出现在它的终点之前。如果图中存在回路，则不存在拓扑排序。
扑排序的结果不一定是唯一的。对于一个DAG，可能存在多种不同的拓扑排序结果，只要满足依赖关系即可。

Kahn算法是基于图的 入度（indegree）进行拓扑排序的一种方法。算法的步骤如下：

  1. 计算每个节点的入度。
  2. 将所有入度为0的节点加入队列。
  3. 从队列中取出节点，将其添加到拓扑排序中，并更新其邻接节点的入度。
  4. 重复上述步骤，直到所有节点都被处理。
cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
public:
    int V;  // 节点数
    vector<vector<int>> adj;  // 邻接表

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);  // 从u到v有一条边
    }

    // 拓扑排序（Kahn算法）
    void topologicalSort() {
        vector<int> in_degree(V, 0);  // 初始化每个节点的入度为0

        // 计算每个节点的入度
        for (int u = 0; u < V; u++) {
            for (int v : adj[u]) {
                in_degree[v]++;
            }
        }

        // 使用队列存储入度为0的节点
        queue<int> q;
        for (int i = 0; i < V; i++) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> topo_order;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topo_order.push_back(u);

            // 将u的邻接节点的入度减1，如果入度为0则加入队列
            for (int v : adj[u]) {
                in_degree[v]--;
                if (in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }

        // 如果拓扑排序的结果中包含所有节点，说明无环图存在拓扑排序
        if (topo_order.size() == V) {
            cout << "拓扑排序结果: ";
            for (int node : topo_order) {
                cout << node << " ";
            }
            cout << endl;
        } else {
            cout << "图中存在环，无法进行拓扑排序" << endl;
        }
    }
};

int main() {
    Graph g(6);

    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    g.topologicalSort();  // 输出拓扑排序

    return 0;
}

下面再介绍一种基于深度优先搜索的拓扑排序，适用于DAG。算法的步骤如下：

cpp

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Graph {
public:
    int V;  // 节点数
    vector<vector<int>> adj;  // 邻接表

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);  // 从u到v有一条边
    }

    // 深度优先搜索拓扑排序
    void dfs(int u, vector<bool>& visited, stack<int>& topo_order) {
        visited[u] = true;

        // 对所有邻接节点进行DFS
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, visited, topo_order);
            }
        }

        // 当前节点u的所有邻接节点都已经访问完，加入栈
        topo_order.push(u);
    }

    // 拓扑排序（DFS方法）
    void topologicalSort() {
        vector<bool> visited(V, false);
        stack<int> topo_order;

        // 对每个未被访问的节点执行DFS
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, visited, topo_order);
            }
        }

        // 输出拓扑排序结果（栈中的顺序即为拓扑排序的逆序）
        cout << "拓扑排序结果: ";
        while (!topo_order.empty()) {
            cout << topo_order.top() << " ";
            topo_order.pop();
        }
        cout << endl;
    }
};

int main() {
    Graph g(6);

    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    g.topologicalSort();  // 输出拓扑排序

    return 0;
}

最短路径算法

单源最短路径算法是计算从图中的一个特定节点（称为源节点）到其他所有节点的最短路径的算法。常见的单源最短路径问题包括计算图中每一对节点之间的最短路径、网络路由、地图路径规划等。
Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
Bellman-Ford 算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。
Floyd-Warshall算法是用于解决所有节点对最短路径问题。
A*算法是一种用于图搜索和路径规划的启发式搜索算法。

Dijkstra算法

Dijkstra 算法是由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出的，用于解决带权重的有向图或者无向图（正权重情况，即边的权重都大于等于 0）中。

  1. 初始化距离数组 dist[]，将源节点的距离设为0，其余节点的距离设为无穷大。
  2. 使用一个优先队列（最小堆）存储当前距离最小的节点，优先队列确保每次都能快速地选出最小距离节点。
  3. 从队列中提取最小距离节点，更新它的邻居节点的最短路径。如果邻居节点的距离被更新，插入或更新优先队列。
  4. 重复步骤3，直到队列为空。

如果使用邻接矩阵表示图，Dijkstra的时间复杂度是 $O(V^2)$，其中 $V$ 是节点的数量。若使用优先队列（最小堆）和邻接表表示图，时间复杂度为 $O((V + E) \log V)$，其中$ E$ 是边的数量。算法的空间复杂度为 $O(V + E)$，因为需要存储图的邻接表、最短路径数组和优先队列。

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> pii;  // 用于存储 (距离, 节点) 的pair

void Dijkstra(const vector<vector<pii>>& graph, int start) {
    int n = graph.size();  // 节点数
    vector<int> dist(n, INT_MAX);  // 初始化所有节点的距离为无穷大
    dist[start] = 0;  // 起始节点的距离为0

    priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆（优先队列）
    pq.push({0, start});  // 将起始节点加入堆中，距离为0

    while (!pq.empty()) {
        int current_dist = pq.top().first;  // 当前节点的最短距离
        int node = pq.top().second;  // 当前节点
        pq.pop();  // 弹出堆顶元素

        // 如果当前节点的距离已经大于已知的最短距离，跳过
        if (current_dist > dist[node]) continue;

        // 遍历当前节点的所有邻居
        for (auto& neighbor : graph[node]) {
            int next_node = neighbor.first;
            int weight = neighbor.second;

            // 如果通过当前节点更新邻接节点的距离更短，更新并加入队列
            if (dist[node] + weight < dist[next_node]) {
                dist[next_node] = dist[node] + weight;
                pq.push({dist[next_node], next_node});
            }
        }
    }

    // 输出每个节点到起始节点的最短路径
    for (int i = 0; i < n; i++) {
        cout << "从节点 " << start << " 到节点 " << i << " 的最短路径为: ";
        if (dist[i] == INT_MAX) {
            cout << "不可达" << endl;
        } else {
            cout << dist[i] << endl;
        }
    }
}

int main() {
    // 图的邻接表表示，假设图有5个节点，编号从0到4
    vector<vector<pii>> graph = {
        {{1, 10}, {2, 5}},        // 节点0与节点1 (权重10) 和节点2 (权重5) 相连
        {{2, 2}, {3, 1}},         // 节点1与节点2 (权重2) 和节点3 (权重1) 相连
        {{1, 3}, {3, 9}, {4, 2}}, // 节点2与节点1 (权重3)、节点3 (权重9) 和节点4 (权重2) 相连
        {{4, 4}},                 // 节点3与节点4 (权重4) 相连
        {{3, 6}}                  // 节点4与节点3 (权重6) 相连
    };

    Dijkstra(graph, 0);  // 从节点0开始计算最短路径

    return 0;
}

图使用邻接表表示。每个节点的邻接节点通过 pair<int, int> 存储，其中第一个值是邻接节点的编号，第二个值是边的权重。
使用一个优先队列 pq 来存储待处理的节点，其中 pq 按照节点到源节点的距离升序排列。

Bellman-Ford 算法

cpp

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int u, v, weight;
    Edge(int _u, int _v, int _weight) : u(_u), v(_v), weight(_weight) {}
};

void bellmanFord(int V, int E, const vector<Edge>& edges, int src) {
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    // 执行 V-1 次松弛操作
    for (int i = 1; i < V; i++) {
        for (const Edge& edge : edges) {
            if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.weight;
            }
        }
    }

    // 检查负权环
    for (const Edge& edge : edges) {
        if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
            cout << "图中存在负权环！" << endl;
            return;
        }
    }

    // 输出最短路径
    for (int i = 0; i < V; i++) {
        if (dist[i] == INT_MAX) {
            cout << "节点 " << i << " 不可达\n";
        } else {
            cout << "源节点到节点 " << i << " 的最短路径为 " << dist[i] << endl;
        }
    }
}

int main() {
    int V = 5;  // 节点数
    vector<Edge> edges = {
        Edge(0, 1, -1),
        Edge(0, 2, 4),
        Edge(1, 2, 3),
        Edge(1, 3, 2),
        Edge(1, 4, 2),
        Edge(3, 2, 5),
        Edge(3, 1, 1),
        Edge(4, 3, -3)
    };
    int src = 0;  // 源节点
    bellmanFord(V, edges.size(), edges, src);
    return 0;
}

Bellman-Ford算法的时间复杂度为 $O(V \times E)$，其中 $V$ 是节点数，$E$ 是边数。由于每次需要对每一条边进行松弛操作，总共需要执行 $V-1$ 次。

Floyd-Warshall算法

Floyd-Warshall算法用于解决 所有节点对最短路径问题（All-Pairs Shortest Path）。它可以计算给定图中任意两点之间的最短路径，适用于带权图（无论权重是否为负），但前提是图中不能有负权环。
Floyd-Warshall算法的基本思路是通过动态规划的方式，逐步更新从每对节点 $i$ 到 $j$ 的最短路径。

假设有一个图 $ G = (V, E) $，其中 $V$ 是节点集合，$E$ 是边集合。定义一个二维数组 dist[i][j] 来表示从节点 $i$ 到节点 $j$ 的最短路径的长度。Floyd-Warshall算法通过以下的递推公式来更新距离：

$$ \text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j]) $$

其中：

Floyd-Warshall算法的步骤

  1. 初始化：创建一个 $V \times V$ 的二维矩阵 dist[][]，其中 dist[i][j] 表示从节点 $i$ 到节点 $j$ 的最短路径。如果存在从节点 $i$ 到节点 $j$ 的边，则 dist[i][j] 等于该边的权重。如果不存在从节点 $i$ 到节点 $j$ 的边，则 dist[i][j] 设为无穷大。对于每个节点 $i$，将 dist[i][i] 设为0，因为任何节点到自身的距离为0。
  2. 动态规划迭代：遍历每个节点 $k$（作为中间节点）。对于每一对节点 $i$ 和 $j$，更新 dist[i][j]，使其为当前路径和经过节点 $k$ 的路径中的较小值。
  3. 终止条件：当所有节点都被作为中间节点使用过后，矩阵 dist[][] 中的每个元素即为从节点 $i$ 到节点 $j$ 的最短路径。
cpp

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

#define INF INT_MAX  // 定义无穷大

void floydWarshall(int V, vector<vector<int>>& dist) {
    // 使用Floyd-Warshall算法更新最短路径
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 输出最短路径矩阵
    cout << "最短路径矩阵：\n";
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                cout << "INF" << "\t";
            } else {
                cout << dist[i][j] << "\t";
            }
        }
        cout << endl;
    }
}

int main() {
    int V = 4;  // 图中的节点数
    vector<vector<int>> dist(V, vector<int>(V, INF));

    // 初始化图的边权
    dist[0][0] = 0;
    dist[0][1] = 3;
    dist[0][2] = INF;
    dist[0][3] = 7;

    dist[1][0] = INF;
    dist[1][1] = 0;
    dist[1][2] = 1;
    dist[1][3] = INF;

    dist[2][0] = INF;
    dist[2][1] = INF;
    dist[2][2] = 0;
    dist[2][3] = 2;

    dist[3][0] = INF;
    dist[3][1] = INF;
    dist[3][2] = INF;
    dist[3][3] = 0;

    // 调用Floyd-Warshall算法计算最短路径
    floydWarshall(V, dist);

    return 0;
}

Floyd-Warshall算法的时间复杂度为 $O(V^3)$，其中 $V$ 是图中的节点数。由于算法需要对每对节点（共 $V^2$ 对）进行 $V$ 次更新，因此总体复杂度为 $O(V^3)$。空间复杂度为 $O(V^2)$，因为需要一个 $V \times V$ 的二维矩阵来存储节点之间的最短路径。

A*算法

A*算法（A-star 算法）是一种用于图搜索和路径规划的启发式搜索算法，广泛应用于游戏开发、导航系统、机器人路径规划等领域。它结合了 广度优先搜索 和 贪心算法 的特点，通过一个评估函数来平衡探索路径和目标的优先级，从而高效地找到从起点到目标的最短路径。

  1. 初始化：起始节点的 $g(n)$ = 0， $h(n)$ 为起始节点到目标节点的估计距离（一般用欧几里得距离或曼哈顿距离）。将起始节点放入开启列表（Open List），开启列表用于存储待探索的节点。
  2. 搜索过程：从开启列表中选取 $f(n)$ 最小的节点作为当前节点。对当前节点的所有邻接节点进行处理，计算它们的 $f(n)$ 值，并更新相关的路径信息。如果邻接节点不在开启列表中，加入开启列表，并更新 $f(n)$ 和 $g(n)$ 值。如果邻接节点已经在开启列表中，检查是否需要更新它的 $g(n)$ 值（即通过当前节点来优化路径）。
  3. 终止条件：当目标节点被加入到开启列表中时，表示找到了一条最短路径，搜索终止。如果开启列表为空，说明没有路径可达目标节点，算法终止。
  4. 路径回溯：一旦目标节点被找到，可以通过回溯每个节点的父节点，构建出从起点到目标的最短路径。

启发式函数 $h(n)$ 是 A* 算法的核心之一，决定了搜索的效率和路径的质量。常用的启发式函数有：

欧几里得距离（Euclidean Distance）：适用于连续空间中的路径规划。

$$ h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
其中，$(x_1, y_1)$ 和 $(x_2, y_2)$ 是两个点的坐标。

曼哈顿距离（Manhattan Distance）：适用于网格地图（例如棋盘格）中的路径规划，假设只能水平或垂直移动。

$$ h(n) = |x_1 - x_2| + |y_1 - y_2| $$

切比雪夫距离（Chebyshev Distance）：适用于允许在八个方向（包括对角线）上移动的情况。

$$ h(n) = \max(|x_1 - x_2|, |y_1 - y_2|) $$

A*算法的优点

  1. 高效性：A*算法能够在较少的探索节点中找到最短路径，特别是当启发式函数合理时，效率很高。
  2. 最优性：在启发式函数是一致（即满足三角不等式）且是可接受的情况下，A*算法保证找到最短路径。
  3. 灵活性：可以根据不同的应用需求调整启发式函数，影响搜索策略。

以下是一个简单的 A* 算法的实现示例，假设在一个二维网格中进行路径规划，使用曼哈顿距离作为启发式函数。

cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <climits>
using namespace std;

// 定义坐标结构体
struct Node {
    int x, y;
    Node(int _x, int _y) : x(_x), y(_y) {}
    bool operator==(const Node& other) const {
        return x == other.x && y == other.y;
    }
};

// 定义节点的哈希函数（用于unordered_map）
namespace std {
    template <>
    struct hash<Node> {
        size_t operator()(const Node& node) const {
            return hash<int>()(node.x) ^ hash<int>()(node.y);
        }
    };
}

// 计算曼哈顿距离
int manhattanDistance(const Node& a, const Node& b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

// A*算法实现
vector<Node> aStar(const Node& start, const Node& goal, const vector<vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();

    // 启动列表（Open List）和关闭列表（Closed List）
    priority_queue<pair<int, Node>, vector<pair<int, Node>>, greater<pair<int, Node>>> openList;
    unordered_map<Node, Node> cameFrom;  // 记录路径
    unordered_map<Node, int> gScore;     // 从起点到当前节点的实际代价
    unordered_map<Node, int> fScore;     // 从起点到当前节点的总代价

    // 初始化
    openList.push({0, start});
    gScore[start] = 0;
    fScore[start] = manhattanDistance(start, goal);

    // 四个方向（上下左右）
    vector<Node> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (!openList.empty()) {
        Node current = openList.top().second;
        openList.pop();

        // 如果到达目标，构建路径
        if (current == goal) {
            vector<Node> path;
            while (cameFrom.find(current) != cameFrom.end()) {
                path.push_back(current);
                current = cameFrom[current];
            }
            path.push_back(start);
            reverse(path.begin(), path.end());
            return path;
        }

        // 探索相邻的节点
        for (const auto& dir : directions) {
            int newX = current.x + dir.x;
            int newY = current.y + dir.y;
            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 0) {  // 确保合法且没有障碍
                Node neighbor(newX, newY);
                int tentativeGScore = gScore[current] + 1;  // 假设每步代价为1

                if (gScore.find(neighbor) == gScore.end() || tentativeGScore < gScore[neighbor]) {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeGScore;
                    fScore[neighbor] = tentativeGScore + manhattanDistance(neighbor, goal);
                    openList.push({fScore[neighbor], neighbor});
                }
            }
        }
    }

    return {};  // 如果没有路径可达目标，返回空路径
}

int main() {
    // 网格（0表示可走，1表示障碍物）
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };

    Node start(0, 0);  // 起点
    Node goal(4, 4);   // 目标

    vector<Node> path = aStar(start, goal, grid);

    // 输出路径
    if (!path.empty()) {
        cout << "找到路径：\n";
        for (const auto& node : path) {
            cout << "(" << node.x << ", " << node.y << ")\n";
        }
    } else {
        cout << "没有找到路径。\n";
    }

    return 0;
}

A*算法在很多领域有广泛应用，尤其是在地图导航、游戏开发、机器人路径规划等需要从起点到目标寻找最短路径的场景中。

NP完全问题

在计算复杂性理论中，我们通常会根据算法解决问题所需的时间和空间资源（也就是时间复杂度和空间复杂度）来对问题进行分类，以此来衡量问题的难易程度。这里涉及到几个重要的概念：

  1. P类问题（Polynomial time）：指的是能够在多项式时间内用确定性算法解决的一类问题。也就是说，存在某个算法，对于这类问题中的任意一个实例，该算法可以在输入规模（比如问题中元素的数量等）的多项式函数表示的时间内得出答案。例如，排序问题（如冒泡排序、快速排序等算法可以在 $O(n^2)$ 、$O(n \log n)$ 等多项式时间复杂度内完成排序，这里的 $n$ 是待排序元素的数量）就属于 P 类问题。

  2. NP 类问题（Nondeterministic Polynomial time，非确定型多项式时间）：问题必须属于 NP类（Nondeterministic Polynomial time）。NP类问题的定义是：如果一个问题的解能够在多项式时间内被验证（即给定一个候选解，能够在多项式时间内确认这个解是否有效），那么这个问题就属于NP类。例如，对于一个给定的路径，能否验证它是一个合法的路径，属于NP问题。

  3. NP-hard：问题必须至少与所有其他NP问题一样难。具体来说，NP完全问题具有“最难”的性质，即所有NP类问题都可以被归约到它。换句话说，如果一个NP完全问题可以在多项式时间内求解，那么所有的NP问题都可以在多项式时间内求解。

一些经典的NP完全问题包括： 1. 旅行商问题（TSP, Travelling Salesman Problem）：给定一组城市和城市之间的距离，求一个最短的路径，使得旅行商访问每个城市一次且只访问一次，最终返回起始城市。该问题在物流配送、巡回计划等领域有广泛应用。
2. 0-1背包问题（0/1 Knapsack Problem）：给定一个背包的最大重量和一组物品，每个物品有重量和价值，求选取物品的最优组合，使得背包内物品的总价值最大且总重量不超过背包的容量。广泛应用于资源分配、财务投资、生产调度等问题中。
3. 集合覆盖问题（Set Cover Problem）：给定一个集合的子集，选择最少数量的子集来覆盖整个集合。 4. 顶点覆盖问题（Vertex Cover Problem）：给定一个图，求一个最小的顶点集合，使得图中所有的边都至少与集合中的一个顶点相连。 5. 独立集问题（Independent Set Problem）：在一个图中，找出最大独立集（图中没有两个相邻的节点）。应用于网络中的冲突避免、图像处理等领域。

P ≠ NP问题：这是计算机科学中的一个未解的核心问题。简单来说，问题是：是否所有能在多项式时间内验证解的NP问题，也能在多项式时间内解决？如果P = NP，意味着所有的NP问题（包括NP完全问题）都能在多项式时间内被解决。如果P ≠ NP，意味着没有多项式时间算法能够解决所有的NP问题，至少有些NP问题是非常难的，需要指数时间才能解决。

在很多实际领域都会遇到 NP 完全问题，像资源分配、物流调度、电路设计等。例如在物流调度中安排送货路线，要满足各种约束条件并使成本最小（类似旅行商问题的思路），由于是 NP 完全问题，很难找到绝对最优的高效解决方案，往往只能采用一些近似算法、启发式算法（比如遗传算法、模拟退火算法等）来获取一个比较满意的、接近最优的结果，而不能保证找到的就是理论上的最优解。

参考资料