基本的算法（续 1）之图算法上-阿里云开发者社区

前言

一、深度优先搜索（DFS）

深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，用于在图或树等数据结构中进行遍历和搜索。它的原理是从一个起始节点开始，沿着路径尽可能深地探索，直到达到最深的节点，然后回溯到上一层。DFS 通过栈或递归实现。

深度优先搜索算法的原理如下：

1. 选择一个起始节点。

2. 访问该节点，并标记为已访问。

3. 从该节点出发，选择一个相邻且未访问的节点，继续深入探索。

4. 如果没有未访问的相邻节点，则回溯到上一层节点，继续探索其他未访问的节点。

5. 重复步骤 3-4，直到所有节点都被访问或没有可访问的节点为止。

深度优先搜索算法的特点是会尽可能深入地搜索每条分支，直到无法再继续下去才回溯。它可以用于求解图的连通性、路径查找、拓扑排序等问题。由于使用栈或递归来存储访问路径，DFS 的空间复杂度较高，对于大规模的图可能会消耗较多的内存。

以下是用数值表示深度优先搜索算法的步骤：

1. 创建一个标记数组，用于记录节点是否被访问过。

- 用一个长度为 n 的布尔数组 `visited` 表示，初始值全为 `false`。

- `visited[i]` 表示第 i 个节点是否被访问过。

2. 从起始节点开始，将其标记为已访问，并进行相应的操作。

- `visited[start] = true`，表示起始节点 `start` 被访问过。

- 进行其他操作，例如打印节点值。

3. 遍历起始节点的所有相邻节点：

- 如果相邻节点未被访问过，则递归调用深度优先搜索算法，以该相邻节点为起始节点。

- `if (!visited[adjacent])`

- `dfs(adjacent)`，递归调用以相邻节点 `adjacent` 为起始节点。

4. 重复步骤 3，直到没有未访问的相邻节点为止。

- 考虑使用循环或递归来遍历相邻节点。

5. 若还有未被访问的节点，则选择其中一个作为新的起始节点，并重复步骤 2-4。

- 可以使用循环遍历所有节点，如果有节点未被访问，则将该节点作为新的起始节点，并重复步骤 2-4。

6. 当所有节点都被访问过时，搜索结束。

- 可以根据标记数组中的值来判断是否所有节点都被访问过，如果全为 `true`，则搜索结束。

1.C++ 编写的深度优先搜索算法

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph; // 图的邻接表表示
vector<bool> visited;      // 标记数组，记录节点是否被访问过
void dfs(int node) {
    visited[node] = true;  // 标记当前节点为已访问
    cout << node << " ";   // 打印当前节点（可根据需求进行其他操作）
    // 遍历当前节点的所有邻接节点
    for (int i = 0; i < graph[node].size(); i++) {
        int adjacent = graph[node][i];
        if (!visited[adjacent]) {
            dfs(adjacent);  // 递归调用深度优先搜索以邻接节点为起始节点
        }
    }
}
int main() {
    int numNodes, numEdges;
    cout << "请输入节点数和边数：" << endl;
    cin >> numNodes >> numEdges;
    graph.resize(numNodes);     // 调整邻接表大小
    visited.resize(numNodes);   // 调整标记数组大小
    cout << "请输入每条边的连接关系：" << endl;
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        cin >> u >> v;
        // 无向图，需要在两个节点的邻接列表中分别添加对方
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int startNode;
    cout << "请输入起始节点：" << endl;
    cin >> startNode;
    cout << "深度优先搜索结果：" << endl;
    dfs(startNode);
    return 0;
}

代码实现步骤：

1. 首先，程序使用 `vector` 头文件包含 `` 和 ``。

2. 接着定义了两个全局变量：`graph` 表示图的邻接表，`visited` 是一个标记数组用于记录节点是否被访问过。

3. 然后，定义了一个深度优先搜索函数 `dfs`，它的参数是一个节点 `node`。

4. 在 `dfs` 函数内部，将当前节点标记为已访问，并将该节点的值输出到控制台。

5. 使用 `for` 循环遍历当前节点的邻接节点列表。

6. 如果邻接节点未被访问过，则递归调用 `dfs` 函数以该邻接节点为起始节点进行深度优先搜索。

7. `main` 函数开始，先定义了两个变量 `numNodes` 和 `numEdges` 用于存储用户输入的节点数和边数。

8. 输出提示信息，要求用户输入节点数和边数。

9. 调用 `cin` 对象对用户输入进行读取，并将结果存储到 `numNodes` 和 `numEdges` 变量中。

10. 调用 `resize` 函数，调整 `graph` 和 `visited` 的大小，使其能够容纳要输入的节点数。

11. 输出提示信息，要求用户输入每条边的连接关系。

12. 使用 `for` 循环和 `cin` 对象，读取并存储每条边的连接关系到邻接表 `graph` 中。

13. 由于是无向图，所以需要在两个节点的邻接列表中分别添加对方。

14. 输出提示信息，要求用户输入起始节点。

15. 使用 `cin` 对象读取用户输入的起始节点，并存储到变量 `startNode` 中。

16. 输出提示信息，告知深度优先搜索的结果将被打印。

17. 调用深度优先搜索函数 `dfs`，并将起始节点 `startNode` 作为参数传入进行深度优先搜索。

18. 程序执行完毕，返回 0 结束。

2.以下是C和Python的深度优先搜索算法代码示例！

#include <stdio.h>
#define MAX_NODES 100
int graph[MAX_NODES][MAX_NODES];
int visited[MAX_NODES];
void dfs(int node, int numNodes) {
    visited[node] = 1;
    printf("%d ", node);
    for (int i = 0; i < numNodes; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i, numNodes);
        }
    }
}
int main() {
    int numNodes, numEdges;
    printf("请输入节点数和边数：\n");
    scanf("%d %d", &numNodes, &numEdges);
    printf("请输入每条边的连接关系：\n");
    for (int i = 0; i < numEdges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;
    }
    int startNode;
    printf("请输入起始节点：\n");
    scanf("%d", &startNode);
    printf("深度优先搜索结果：\n");
    dfs(startNode, numNodes);
    return 0;
}

def dfs(node, graph, visited):
    visited[node] = True
    print(node, end=" ")
    for adjacent in graph[node]:
        if not visited[adjacent]:
            dfs(adjacent, graph, visited)
numNodes, numEdges = map(int, input("请输入节点数和边数：").split())
graph = [[] for _ in range(numNodes)]
visited = [False] * numNodes
print("请输入每条边的连接关系：")
for _ in range(numEdges):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
startNode = int(input("请输入起始节点："))
print("深度优先搜索结果：")
dfs(startNode, graph, visited)

二、广度优先搜索（BFS）

广度优先搜索算法（BFS）是一种用于图的遍历的算法。它从指定的起始节点开始，逐层遍历图的节点，直到找到目标节点或遍历完整个图。BFS 通常使用队列来保存待访问的节点。

function BFS(graph, startNode):
    queue = []                    # 创建一个空队列
    queue.append(startNode)       # 将起始节点放入队列中
    visited = {}                  # 创建一个字典用于标记节点是否已访问（1表示已访问）
    visited[startNode] = 1        # 将起始节点的标记设为1
    while queue:                  # 当队列不为空时执行以下操作
         currentNode = queue.pop(0)         # 从队列中取出队首的节点编号作为当前节点
         process(currentNode)               # 访问当前节点，并执行相应的操作
         for neighbor in graph[currentNode]:         # 遍历当前节点的邻接节点
             if neighbor not in visited:             # 如果邻接节点未被访问过
                 visited[neighbor] = 1                # 将其标记设为1
                 queue.append(neighbor)               # 并将其编号放入队列中
         visited[currentNode] = 1          # 将当前节点标记为已处理（或已访问）
    for node in graph:                    # 如果图中还有未被访问的节点
        if node not in visited:           # 选择一个未被访问的节点作为新的起始节点
            queue.append(node)            # 并将其放入队列中
            visited[node] = 1             # 将其标记为1
            while queue:                  # 重复步骤1-4
                currentNode = queue.pop(0)
                process(currentNode)
                for neighbor in graph[currentNode]:
                    if neighbor not in visited:
                        visited[neighbor] = 1
                        queue.append(neighbor)
                visited[currentNode] = 1
    # 结束算法

1.C++ 编写的广度优先搜索算法

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
void BFS(std::unordered_map<int, std::vector<int>>& graph, int startNode) {
    std::queue<int> queue;                          // 创建一个空队列
    queue.push(startNode);                           // 将起始节点放入队列中
    std::unordered_map<int, bool> visited;           // 创建一个unordered_map用于标记节点是否已访问
    visited[startNode] = true;                       // 将起始节点的标记设为true
    while (!queue.empty()) {                         // 当队列不为空时执行以下操作
        int currentNode = queue.front();             // 从队列中取出队首的节点编号作为当前节点
        queue.pop();
        process(currentNode);                         // 访问当前节点，并执行相应的操作
        for (int neighbor : graph[currentNode]) {     // 遍历当前节点的邻接节点
            if (!visited[neighbor]) {                 // 如果邻接节点未被访问过
                visited[neighbor] = true;              // 将其标记设为true
                queue.push(neighbor);                  // 并将其编号放入队列中
            }
        }
        visited[currentNode] = true;                  // 将当前节点标记为已处理（或已访问）
    }
    for (auto iter : graph) {                          // 如果图中还有未被访问的节点
        int node = iter.first;
        if (!visited[node]) {                          // 选择一个未被访问的节点作为新的起始节点
            queue.push(node);                           // 并将其放入队列中
            visited[node] = true;                       // 将其标记为true
            while (!queue.empty()) {                    // 重复步骤1-4
                int currentNode = queue.front();
                queue.pop();
                process(currentNode);
                for (int neighbor : graph[currentNode]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.push(neighbor);
                    }
                }
                visited[currentNode] = true;
            }
        }
    }
}
int main() {
    std::unordered_map<int, std::vector<int>> graph;
    // 构建图的过程，将节点及其邻接节点加入graph中
    // 调用BFS函数，传入graph和起始节点
    BFS(graph, startNode);
    return 0;
}

2.C 编写的广度优先搜索算法

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_NODES 100
// 邻接链表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
// 邻接链表
typedef struct AdjList {
    Node* head;
} AdjList;
// 图
typedef struct Graph {
    int numNodes;
    AdjList* array;
} Graph;
// 创建一个节点
Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}
// 创建一个图
Graph* createGraph(int numNodes) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numNodes = numNodes;
    graph->array = (AdjList*)malloc(numNodes * sizeof(AdjList));
    for (int i = 0; i < numNodes; ++i)
        graph->array[i].head = NULL;
    return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    newNode = createNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}
// 广度优先搜索
void BFS(Graph* graph, int startNode) {
    bool visited[MAX_NODES] = { false };
    visited[startNode] = true;
    // 创建队列
    int queue[MAX_NODES];
    int front = 0, rear = 0;
    queue[rear++] = startNode;
    while (front != rear) {
        int currentNode = queue[front++];
        printf("%d ", currentNode); // 执行相应的操作，这里仅输出节点编号
        Node* temp = graph->array[currentNode].head;
        while (temp != NULL) {
            int neighbor = temp->vertex;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue[rear++] = neighbor;
            }
            temp = temp->next;
        }
    }
}
int main() {
    int numNodes = 6;
    Graph* graph = createGraph(numNodes);
    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);
    int startNode = 0;
    printf("BFS starting from node %d: ", startNode);
    BFS(graph, startNode);
    printf("\n");
    return 0;
}

三.最小生成树

最小生成树（Minimum Spanning Tree，简称MST）是一种在带权无向图中生成一棵树的算法。这棵树包含了图中的所有节点，并且将这些节点通过边连接起来，使得整个树的总权重最小。

最小生成树具有以下特点：

1. 包含所有的节点：最小生成树包含了图中的所有节点。

2. 无回路：最小生成树是一棵树，因此不存在回路。

3. 边的最小权重：最小生成树的边具有最小的总权重，即树上所有边的权重之和最小。

最小生成树有多种算法可用于求解，其中最流行的算法是Prim算法和Kruskal算法。

- Prim算法：从一个初始节点开始，逐步选择与当前生成树相邻且权重最小的边，直到将所有节点都包含在生成树中为止。

- Kruskal算法：按照边的权重从小到大的顺序逐步添加边，如果该边连接的两个节点不在同一个连通分量中，则加入生成树。

通过最小生成树可以找到一个连接图中所有节点且总权重最小的方式，应用广泛，如网络设计、电力传输、城市规划等领域。

1.Prim算法

Prim算法是一种用于求解最小生成树（Minimum Spanning Tree，简称MST）的贪心算法。Prim算法从一个起始节点开始，逐步选择与当前生成树相邻且权重最小的边，并将相邻节点加入生成树的集合中，直到将所有节点都包含在生成树中为止。

下面是Prim算法的基本步骤：

1. 随机选择一个节点作为起始节点。

2. 初始化一个空的生成树和一个辅助的集合用于存储已访问的节点。

3. 将起始节点加入已访问的节点集合中。

4. 对于已访问的节点，找到与其相邻且权重最小的边。

5. 选择权重最小的边所连接的节点，将其加入生成树，并将其加入已访问节点集合中。

6. 重复步骤4和步骤5，直到生成树包含了图中的所有节点。

7. 输出最小生成树。

Prim算法的核心思想是每次都选取和当前生成树连接的边中最小权重的边，并将其连接的节点加入生成树。通过不断选择权重最小的边来构建生成树，最终得到权重之和最小的最小生成树。

Prim算法的时间复杂度通常为 O(V^2)，其中 V 表示节点的数量。但是通过使用优先队列（例如二叉堆）来存储边的权重，可以将时间复杂度优化到 O(E log V)，其中 E 表示边的数量。这样可以提升Prim算法的效率，并适用于大规模图的求解。

1.1Prim算法c++代码示例

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;   // 表示边的权重和终点的 pair
// 用于表示图的邻接列表
vector<vector<pii>> graph;
// Prim算法函数
void prim(int startNode) {
    int numNodes = graph.size();
    vector<bool> visited(numNodes, false);  // 用于标记节点是否已经访问
    vector<int> minWeight(numNodes, INT_MAX);  // 用于存储每个节点到生成树的最小权重
    priority_queue<pii, vector<pii>, greater<pii>> pq; // 最小堆，用于选择当前权重最小的边
    minWeight[startNode] = 0;  // 起始点到生成树的权重为0
    pq.push({0, startNode});  // 将起始点加入优先队列
    while (!pq.empty()) {
        int currentNode = pq.top().second;  // 当前权重最小的节点
        pq.pop();
        visited[currentNode] = true;  // 标记当前节点已访问
        // 遍历当前节点的所有邻接边
        for (auto edge : graph[currentNode]) {
            int weight = edge.first;
            int neighbor = edge.second;
            // 如果邻接节点未被访问且当前边的权重小于其到生成树的最小权重
            if (!visited[neighbor] && weight < minWeight[neighbor]) {
                minWeight[neighbor] = weight;  // 更新最小权重
                pq.push({weight, neighbor});  // 将邻接节点加入优先队列
            }
        }
    }
    // 输出生成树的信息
    cout << "Prim's Algorithm\n";
    cout << "Minimum Spanning Tree Edges: \n";
    for (int i = 1; i < numNodes; i++) {
        cout << i << " - " << (i < startNode ? (i + 1) : (i + 2)) << " (weight: " << minWeight[i] << ")\n";
    }
}
int main() {
    int numNodes = 6;
    graph.resize(numNodes);
    // 添加边
    graph[0].push_back({2, 1});
    graph[0].push_back({3, 2});
    graph[1].push_back({2, 0});
    graph[1].push_back({5, 2});
    graph[1].push_back({1, 3});
    graph[2].push_back({3, 0});
    graph[2].push_back({5, 1});
    graph[2].push_back({3, 3});
    graph[2].push_back({1, 4});
    graph[3].push_back({1, 1});
    graph[3].push_back({3, 2});
    graph[3].push_back({4, 4});
    graph[3].push_back({5, 5});
    graph[4].push_back({1, 2});
    graph[4].push_back({4, 3});
    graph[4].push_back({2, 5});
    graph[5].push_back({5, 3});
    graph[5].push_back({2, 4});
    int startNode = 0;
    prim(startNode);
    return 0;
}

该代码示例首先定义了一个用于表示图的邻接列表 graph，然后实现了 prim 函数进行 Prim 算法。在 prim 函数中，使用了优先队列 pq 存储当前权重最小的边，使用了 visited 数组记录节点是否已经访问过，使用了 minWeight 数组保存每个节点到生成树的最小权重。

具体实现步骤如下：

初始化节点是否已访问的标记 visited 和最小权重数组 minWeight，将起始节点加入优先队列 pq。
当优先队列不为空时，取出当前权重最小的节点 currentNode。
标记当前节点为已访问。
遍历当前节点的所有邻接边，如果邻接节点未被访问且当前边的权重小于其到生成树的最小权重，更新最小权重并将邻接节点加入优先队列。
重复步骤2到4，直到所有节点都被访问完毕。
输出生成树的信息，即最小生成树的边和对应的权重。

最后，在主函数中构建了一个包含6个节点的图，并设置了相应的边权重。通过调用 prim 函数，以起始节点为参数，执行 Prim 算法并输出最小生成树的边及对应的权重。

1.2Prim算法的c代码和python代码示例

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_NODES 6
// 邻接矩阵表示图
int graph[MAX_NODES][MAX_NODES];
// 找到图中未包含在生成树中的最小权重的节点
int findMinWeight(bool visited[], int minWeight[], int numNodes) {
    int minWeightVal = INT_MAX;
    int minWeightNode;
    for (int i = 0; i < numNodes; i++) {
        if (!visited[i] && minWeight[i] < minWeightVal) {
            minWeightVal = minWeight[i];
            minWeightNode = i;
        }
    }
    return minWeightNode;
}
// 执行Prim算法
void prim(int startNode, int numNodes) {
    bool visited[MAX_NODES];
    int minWeight[MAX_NODES];
    int parent[MAX_NODES];
    // 初始化visited、minWeight和parent数组
    for (int i = 0; i < numNodes; i++) {
        visited[i] = false;
        minWeight[i] = INT_MAX;
        parent[i] = -1;
    }
    // 起始节点到自身的权重为0
    minWeight[startNode] = 0;
    parent[startNode] = -1;
    // 找到最小生成树中的所有边
    for (int i = 0; i < numNodes - 1; i++) {
        int currentNode = findMinWeight(visited, minWeight, numNodes);
        visited[currentNode] = true;
        // 更新邻接节点的最小权重和父节点
        for (int j = 0; j < numNodes; j++) {
            if (graph[currentNode][j] != 0 && !visited[j] && graph[currentNode][j] < minWeight[j]) {
                minWeight[j] = graph[currentNode][j];
                parent[j] = currentNode;
            }
        }
    }
    // 输出生成树的信息
    printf("Prim's Algorithm\n");
    printf("Minimum Spanning Tree Edges:\n");
    for (int i = 1; i < numNodes; i++) {
        printf("%d - %d (weight: %d)\n", parent[i] + 1, i + 1, minWeight[i]);
    }
}
int main() {
    int numNodes = 6;
    // 构建邻接矩阵表示的图
    graph[0][1] = 2;
    graph[0][2] = 3;
    graph[1][0] = 2;
    graph[1][2] = 5;
    graph[1][3] = 1;
    graph[2][0] = 3;
    graph[2][1] = 5;
    graph[2][3] = 3;
    graph[2][4] = 1;
    graph[3][1] = 1;
    graph[3][2] = 3;
    graph[3][4] = 4;
    graph[3][5] = 5;
    graph[4][2] = 1;
    graph[4][3] = 4;
    graph[4][5] = 2;
    graph[5][3] = 5;
    graph[5][4] = 2;
    int startNode = 0;
    prim(startNode, numNodes);
    return 0;
}

import sys
def findMinWeight(visited, minWeight, numNodes):
    minWeightVal = sys.maxsize
    minWeightNode = -1
    for i in range(numNodes):
        if not visited[i] and minWeight[i] < minWeightVal:
            minWeightVal = minWeight[i]
            minWeightNode = i
    return minWeightNode
def prim(startNode, numNodes):
    visited = [False] * numNodes
    minWeight = [sys.maxsize] * numNodes
    parent = [-1] * numNodes
    minWeight[startNode] = 0
    for _ in range(numNodes - 1):
        currentNode = findMinWeight(visited, minWeight, numNodes)
        visited[currentNode] = True
        for j in range(numNodes):
            if graph[currentNode][j] != 0 and not visited[j] and graph[currentNode][j] < minWeight[j]:
                minWeight[j] = graph[currentNode][j]
                parent[j] = currentNode
    print("Prim's Algorithm")
    print("Minimum Spanning Tree Edges:")
    for i in range(1, numNodes):
        print(f"{parent[i] + 1} - {i + 1} (weight: {minWeight[i]})")
numNodes = 6
graph = [
    [0, 2, 3, 0, 0, 0],
    [2, 0, 5, 1, 0, 0],
    [3, 5, 0, 3, 1, 0],
    [0, 1, 3, 0, 4, 5],
    [0, 0, 1, 4, 0, 2],
    [0, 0, 0, 5, 2, 0]
]
startNode = 0
prim(startNode, numNodes)

2.Kruskal算法

Kruskal算法是一种用于求解最小生成树的贪心算法。最小生成树是指在一个连通带权无向图中，选择一棵包含所有顶点且边权重之和最小的子图。Kruskal算法的目标是找到最小生成树。

Kruskal算法的基本思想是从图中的边集合中按照权重递增的顺序选择边，并将其逐步加入到最小生成树的集合中。在选择每条边之前，检查是否加入该边会导致出现环路，如果不会，就将该边加入到最小生成树的集合中。

下面是Kruskal算法的基本步骤：

1. 初始化一个空的最小生成树集合。

2. 对图的所有边根据权重进行排序。

3. 依次遍历排序后的边集合，对于每条边，如果加入该边不会导致出现环路（即不与已有的边构成环路），则将其加入到最小生成树集合中。

4. 继续遍历，直到最小生成树的边数达到图的顶点数减1为止。

Kruskal算法的时间复杂度取决于排序边的时间复杂度，常见的实现方式是使用并查集（Union-Find）数据结构来判断是否形成环路，并使用快速排序或堆排序对边进行排序。总体而言，Kruskal算法的时间复杂度为O(ElogE)，其中E为边的数量。

2.1Kruskal算法c++代码示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int src, dest, weight;
};
// 按照边的权重进行排序的比较函数
bool compareEdges(Edge a, Edge b) {
    return a.weight < b.weight;
}
// 查找节点所属的集合
int findSet(vector<int>& parent, int i) {
    if (parent[i] == -1)
        return i;
    return findSet(parent, parent[i]);
}
// 合并两个集合
void unionSets(vector<int>& parent, int x, int y) {
    int xset = findSet(parent, x);
    int yset = findSet(parent, y);
    parent[xset] = yset;
}
// Kruskal算法实现
void kruskalMST(vector<Edge>& edges, int numVertices) {
    vector<Edge> minimumSpanningTree; // 存储最小生成树的边
    vector<int> parent(numVertices, -1); // 用于存储节点的父节点，初始为-1
    int numEdges = 0; // 记录加入最小生成树的边数
    // 按照边的权重进行排序
    sort(edges.begin(), edges.end(), compareEdges);
    for (auto edge : edges) {
        // 检查边的两个节点是否属于同一集合（是否形成环路）
        int x = findSet(parent, edge.src);
        int y = findSet(parent, edge.dest);
        if (x != y) {
            // 边不会导致环路，将其加入最小生成树，并合并两个集合
            minimumSpanningTree.push_back(edge);
            unionSets(parent, x, y);
            numEdges++;
            if (numEdges == numVertices - 1)
                break; // 达到最小生成树的边数要求，结束算法
        }
    }
    // 输出最小生成树的边和权重
    cout << "Kruskal's Algorithm" << endl;
    cout << "Minimum Spanning Tree Edges:" << endl;
    for (auto edge : minimumSpanningTree) {
        cout << edge.src << " - " << edge.dest << " (weight: " << edge.weight << ")" << endl;
    }
}
int main() {
    int numVertices = 6;
    vector<Edge> edges;
    // 添加图的边信息
    edges.push_back({0, 1, 2});
    edges.push_back({0, 2, 3});
    edges.push_back({1, 2, 5});
    edges.push_back({1, 3, 1});
    edges.push_back({2, 3, 3});
    edges.push_back({2, 4, 1});
    edges.push_back({3, 4, 4});
    edges.push_back({3, 5, 5});
    edges.push_back({4, 5, 2});
    kruskalMST(edges, numVertices);
    return 0;
}

Kruskal算法通过维护一个最小生成树集合和一个并查集，按照边的权重递增的顺序选择边。对于每条边，它首先通过并查集判断该边的两个节点是否属于同一个集合（是否形成环路），如果不是，则将该边加入最小生成树集合，并将两个集合合并。最终得到的最小生成树就是所求。

该代码使用了一个结构体Edge来表示图的边，包括起始节点、目标节点和权重。compareEdges函数用于比较边的权重大小，findSet函数用于查找节点所属的集合，unionSets函数用于合并两个集合。kruskalMST函数是Kruskal算法的主要实现部分，它按照边的权重进行排序，然后依次遍历每条边，并根据并查集判断是否加入该边到最小生成树中。最后，输出最小生成树的边和权重。

这段代码运行的时间复杂度取决于边的数量和顶点的数量。在排序边的步骤上，使用了快速排序算法，其时间复杂度为O(ElogE)，其中E为边的数量。在循环内部的并查集操作上，时间复杂度近似为O(logV)，其中V为顶点的数量。因此，Kruskal算法的总体时间复杂度为O(ElogE + ElogV)。

2.2Kruskal算法的c代码和python代码示例

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_NODES 6
// 邻接矩阵表示图
int graph[MAX_NODES][MAX_NODES];
// 找到图中未包含在生成树中的最小权重的节点
int findMinWeight(bool visited[], int minWeight[], int numNodes) {
    int minWeightVal = INT_MAX;
    int minWeightNode;
    for (int i = 0; i < numNodes; i++) {
        if (!visited[i] && minWeight[i] < minWeightVal) {
            minWeightVal = minWeight[i];
            minWeightNode = i;
        }
    }
    return minWeightNode;
}
// 执行Prim算法
void prim(int startNode, int numNodes) {
    bool visited[MAX_NODES];
    int minWeight[MAX_NODES];
    int parent[MAX_NODES];
    // 初始化visited、minWeight和parent数组
    for (int i = 0; i < numNodes; i++) {
        visited[i] = false;
        minWeight[i] = INT_MAX;
        parent[i] = -1;
    }
    // 起始节点到自身的权重为0
    minWeight[startNode] = 0;
    parent[startNode] = -1;
    // 找到最小生成树中的所有边
    for (int i = 0; i < numNodes - 1; i++) {
        int currentNode = findMinWeight(visited, minWeight, numNodes);
        visited[currentNode] = true;
        // 更新邻接节点的最小权重和父节点
        for (int j = 0; j < numNodes; j++) {
            if (graph[currentNode][j] != 0 && !visited[j] && graph[currentNode][j] < minWeight[j]) {
                minWeight[j] = graph[currentNode][j];
                parent[j] = currentNode;
            }
        }
    }
    // 输出生成树的信息
    printf("Prim's Algorithm\n");
    printf("Minimum Spanning Tree Edges:\n");
    for (int i = 1; i < numNodes; i++) {
        printf("%d - %d (weight: %d)\n", parent[i] + 1, i + 1, minWeight[i]);
    }
}
int main() {
    int numNodes = 6;
    // 构建邻接矩阵表示的图
    graph[0][1] = 2;
    graph[0][2] = 3;
    graph[1][0] = 2;
    graph[1][2] = 5;
    graph[1][3] = 1;
    graph[2][0] = 3;
    graph[2][1] = 5;
    graph[2][3] = 3;
    graph[2][4] = 1;
    graph[3][1] = 1;
    graph[3][2] = 3;
    graph[3][4] = 4;
    graph[3][5] = 5;
    graph[4][2] = 1;
    graph[4][3] = 4;
    graph[4][5] = 2;
    graph[5][3] = 5;
    graph[5][4] = 2;
    int startNode = 0;
    prim(startNode, numNodes);
    return 0;
}

import sys
def findMinWeight(visited, minWeight, numNodes):
    minWeightVal = sys.maxsize
    minWeightNode = -1
    for i in range(numNodes):
        if not visited[i] and minWeight[i] < minWeightVal:
            minWeightVal = minWeight[i]
            minWeightNode = i
    return minWeightNode
def prim(startNode, numNodes):
    visited = [False] * numNodes
    minWeight = [sys.maxsize] * numNodes
    parent = [-1] * numNodes
    minWeight[startNode] = 0
    for _ in range(numNodes - 1):
        currentNode = findMinWeight(visited, minWeight, numNodes)
        visited[currentNode] = True
        for j in range(numNodes):
            if graph[currentNode][j] != 0 and not visited[j] and graph[currentNode][j] < minWeight[j]:
                minWeight[j] = graph[currentNode][j]
                parent[j] = currentNode
    print("Prim's Algorithm")
    print("Minimum Spanning Tree Edges:")
    for i in range(1, numNodes):
        print(f"{parent[i] + 1} - {i + 1} (weight: {minWeight[i]})")
numNodes = 6
graph = [
    [0, 2, 3, 0, 0, 0],
    [2, 0, 5, 1, 0, 0],
    [3, 5, 0, 3, 1, 0],
    [0, 1, 3, 0, 4, 5],
    [0, 0, 1, 4, 0, 2],
    [0, 0, 0, 5, 2, 0]
]
startNode = 0
prim(startNode, numNodes)

四.单源最短路径

单源最短路径是图论中的一个经典问题，它求解的是从图中的一个指定源节点到图中的其他各节点的最短路径。

在一个加权有向图或加权无向图中，每条边都有一个关联的权重或距离。单源最短路径问题的目标是找到从给定的源节点到其余节点的最短路径。其中，最短路径可以根据两个节点之间边的权重之和来衡量。

有几种常见的算法可以解决单源最短路径问题，其中最著名的算法包括Dijkstra算法和Bellman-Ford算法。

- Dijkstra算法：适用于图中不存在负权边的情况。它以贪心的方式逐步构建最短路径树，通过选择当前节点距离最短的邻接节点来不断扩展最短路径。

- Bellman-Ford算法：适用于存在负权边的情况。该算法通过进行多轮的松弛操作，逐步减小从源节点到其他节点的估计距离，直到达到最短路径。

这些算法中，Dijkstra算法对于非负权边的图有较好的性能，而Bellman-Ford算法则可以处理存在负权边的情况。这些算法的实现方式多种多样，可以使用不同的数据结构来表示图和距离信息，具体的实现可能会有所不同。

1.Dijkstra算法

Dijkstra算法是一种用于求解单源最短路径问题的贪心算法。它能够找到有向图或无向图中，从给定源节点到各个节点的最短路径。

Dijkstra算法的基本思想是逐步构建最短路径树，通过选择当前源节点到其他节点距离最短的节点来不断扩展最短路径。

下面是Dijkstra算法的基本步骤：

1. 初始化距离数组，用于存储源节点到各个节点的距离。将源节点的距离设为0，其他节点的距离设为无穷大（表示尚未确定）。

2. 选择距离最短的节点作为当前节点，并将其标记为已访问。

3. 对于当前节点的每个邻接节点，计算通过当前节点到达该邻接节点的距离，如果该距离小于邻接节点的当前距离，则更新邻接节点的距离。

4. 重复步骤2和步骤3，直到所有节点都被访问过或者没有可以扩展的节点为止。

在上述步骤中，通过使用距离数组和一个标记数组来追踪节点距离和访问状态。在每一轮的选择节点时，都会选择当前距离最短且未被访问过的节点。通过不断更新节点的距离，可以得到源节点到所有其他节点的最短路径。

Dijkstra算法适用于非负权边的图，但对负权边的图无法正确处理，因为它无法处理已经确定最短路径的节点的更新。如果图中存在负权边，可以考虑使用其他算法如Bellman-Ford算法来解决单源最短路径问题。

1.1Dijkstra算法c++代码示例

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 定义无穷大表示距离为未确定状态
const int INF = INT_MAX;
// Dijkstra算法实现
void dijkstra(vector<vector<int>>& graph, int source) {
    int numVertices = graph.size();
    // 创建距离数组，用于存储源节点到各个节点的最短距离
    vector<int> distance(numVertices, INF);
    // 创建标记数组，用于记录节点的访问状态
    vector<bool> visited(numVertices, false);
    // 设置源节点的距离为0
    distance[source] = 0;
    // 循环遍历所有节点
    for (int count = 0; count < numVertices - 1; ++count) {
        int minDistance = INF;
        int minDistanceVertex = -1;
        // 选择距离最短的节点作为当前节点
        for (int v = 0; v < numVertices; ++v) {
            if (!visited[v] && distance[v] <= minDistance) {
                minDistance = distance[v];
                minDistanceVertex = v;
            }
        }
        // 标记当前节点为已访问
        visited[minDistanceVertex] = true;
        // 更新当前节点的邻接节点的距离
        for (int v = 0; v < numVertices; ++v) {
            if (!visited[v] && graph[minDistanceVertex][v] != 0 &&
                distance[minDistanceVertex] != INF &&
                distance[minDistanceVertex] + graph[minDistanceVertex][v] < distance[v]) {
                distance[v] = distance[minDistanceVertex] + graph[minDistanceVertex][v];
            }
        }
    }
    // 输出节点距离
    cout << "Dijkstra's Algorithm" << endl;
    cout << "Shortest Distance from Source Node to Each Node:" << endl;
    for (int v = 0; v < numVertices; ++v) {
        cout << "Node " << v << ": " << distance[v] << endl;
    }
}
int main() {
    int numVertices = 9;
    vector<vector<int>> graph = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

Dijkstra算法的实现步骤如下：

创建距离数组distance和标记数组visited，分别用于存储源节点到各个节点的最短距离和节点的访问状态。初始时，所有节点的距离设为无穷大（表示未确定）。
将源节点的距离设为0，并依次遍历所有节点。
在遍历的过程中，选择距离最短且未被访问过的节点作为当前节点。
标记当前节点为已访问，然后更新当前节点的邻接节点的距离。如果通过当前节点到达邻接节点的距离小于邻接节点的当前距离，则更新邻接节点的距离。
重复步骤3和步骤4，直到所有节点都被访问过或者没有可以扩展的节点为止。
输出节点距离，即源节点到每个节点的最短距离。

这段代码使用了一个二维向量graph来表示图的邻接矩阵，其中graph[i][j]表示从节点i到节点j的边的权重。dijkstra函数是Dijkstra算法的主要实现部分，它通过遍历所有节点，并利用最小堆（使用线性搜索）找到当前距离最短的节点。然后，它将该节点标记为已访问，并更新其邻接节点的距离。最后，输出节点的最短距离。

这段代码的运行时间复杂度取决于节点的数量和边的数量。在每一轮的选择最短距离节点时，需要进行线性搜索，时间复杂度为O(V)。在每一轮的更新邻接节点距离时，需要遍历所有节点，时间复杂度为O(V^2)。综合起来，Dijkstra算法的总体时间复杂度为O(V^2)，其中V为节点的数量。

1.2Dijkstra算法的c代码和python代码示例

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 9
int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX;
    int minIndex;
    for (int v = 0; v < V; v++) {
        if (visited[v] == false && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}
void printSolution(int dist[]) {
    printf("Dijkstra's Algorithm\n");
    printf("Shortest Distance from Source Node to Each Node:\n");
    for (int v = 0; v < V; ++v) {
        printf("Node %d: %d\n", v, dist[v]);
    }
}
void dijkstra(int graph[V][V], int source) {
    int dist[V];
    bool visited[V];
    for (int v = 0; v < V; ++v) {
        dist[v] = INT_MAX;
        visited[v] = false;
    }
    dist[source] = 0;
    for (int count = 0; count < V - 1; ++count) {
        int u = minDistance(dist, visited);
        visited[u] = true;
        for (int v = 0; v < V; ++v) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX &&
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    printSolution(dist);
}
int main() {
    int graph[V][V] = {
        { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
        { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
    };
    dijkstra(graph, 0);
    return 0;
}

import sys
V = 9
def minDistance(dist, visited):
    min = sys.maxsize
    minIndex = -1
    for v in range(V):
        if visited[v] == False and dist[v] <= min:
            min = dist[v]
            minIndex = v
    return minIndex
def printSolution(dist):
    print("Dijkstra's Algorithm")
    print("Shortest Distance from Source Node to Each Node:")
    for v in range(V):
        print("Node", v, ":", dist[v])
def dijkstra(graph, source):
    dist = [sys.maxsize] * V
    visited = [False] * V
    dist[source] = 0
    for count in range(V - 1):
        u = minDistance(dist, visited)
        visited[u] = True
        for v in range(V):
            if (not visited[v] and graph[u][v] and dist[u] != sys.maxsize and
                    dist[u] + graph[u][v] < dist[v]):
                dist[v] = dist[u] + graph[u][v]
    printSolution(dist)
graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0]
]
dijkstra(graph, 0)

基本的算法（续 1）之图算法上

前言