图的遍历(Travering Graph):从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次，图的遍历算法是各种图的操作的基础。
复杂性:图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。
解决办法:在遍历过程中记下已被访问过的顶点。设置一个辅助向量 Visited[1…nl(n为顶点数)，其初值为0，一旦访问了顶点v后，使Visited[li]为1或为访问的次序号。

深度优先搜索（Depth First Search – DFS）

深度优先搜索（Depth-First Search，DFS） 是一种遍历或搜索树或图的算法。其基本思想是：从起始节点出发，沿着每一条路径一直走下去，直到无法继续为止，再回溯到最近的分叉点，继续沿着另一条路径走。这样递归地进行，直到所有节点都被访问到。

• DFS 适用于树和图这两种数据结构。DFS 的搜索方式“深度优先”，即尽量深入每一条路径，直到没有更多节点可以访问，再回溯并继续遍历其他路径。

DFS 工作流程
1.从起始节点开始：选择一个未被访问的节点作为起始节点。
2.访问当前节点：首先标记该节点为已访问，并处理该节点（例如打印或执行其他操作）。
3.递归访问邻居节点：然后继续访问该节点的一个未被访问的邻居节点，递归进行深度优先搜索。
4.回溯：当所有邻居节点都已经访问过时，回溯到上一个节点，继续探索其他未访问的邻居节点。
5.结束条件：直到所有节点都被访问过为止，DFS 完成。
深度优先搜索的特征：
1.递归：DFS 最自然的实现方式是递归。
2.回溯：DFS 通过回溯的方式，重新返回到上一个节点，继续探索。
3.栈结构：DFS 也可以通过显式栈来实现，栈结构符合 DFS 中的“后进先出”（LIFO）特性。
4.图的遍历：DFS 可以遍历图中的所有节点和边，适用于查找图的连通性、寻找环等问题。

DFS遍历下图C语言示例：

    0
   / \
  1   2
 / \   
3   4  

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 5  // 最大顶点数（本例中为 5）

// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES];

// visited 数组用于记录顶点是否被访问过
bool visited[MAX_VERTICES];

// 深度优先搜索函数
void dfs(int vertex, int n) {
    // 标记当前顶点为已访问
    visited[vertex] = true;
    printf("%d ", vertex);

    // 遍历所有相邻的顶点
    for (int i = 0; i < n; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) {
            dfs(i, n);  // 递归访问相邻的未访问顶点
        }
    }
}

int main() {
    int n = 5;  // 顶点数
    int m = 4;  // 边数

    // 初始化图的邻接矩阵和 visited 数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // 输入图的边（无向图）
    graph[0][1] = 1; graph[1][0] = 1;  // 0-1
    graph[0][2] = 1; graph[2][0] = 1;  // 0-2
    graph[1][3] = 1; graph[3][1] = 1;  // 1-3
    graph[1][4] = 1; graph[4][1] = 1;  // 1-4

    // 从顶点 0 开始进行 DFS
    printf("深度优先搜索的结果:\n");
    dfs(0, n);

    return 0;
}

广度优先搜索（Breadth First Search – BFS）

广度优先搜索（Breadth-First Search，BFS） 是一种图遍历算法，它从图的起始节点开始，首先访问该节点的所有邻居，然后访问这些邻居的邻居，依此类推，直到所有节点都被访问。

与**深度优先搜索（DFS）**不同，BFS 的搜索顺序是“广度优先”的，即先访问离起始节点较近的节点，然后逐渐向远离起始节点的地方扩展。

BFS 的核心思想是：
1.从起始节点开始，先访问当前节点的所有邻居。
2.将这些邻居节点按顺序加入一个队列。
3.然后从队列中取出下一个节点，访问该节点的所有未被访问过的邻居。
4.将这些邻居节点加入队列中，继续重复该过程，直到所有节点都被访问过为止。

BFS 的工作流程
1.初始化：首先，将起始节点加入队列，并标记为已访问。
2.队列操作：从队列中取出一个节点，访问它，并将该节点的所有未被访问的邻居加入队列。
3.重复操作：重复步骤 2，直到队列为空为止。
BFS 关键点：
1.队列（Queue）：BFS 使用队列来存储待访问的节点，队列保证了“先进先出”（FIFO）的顺序。
2.层次遍历：BFS 会按层次逐级访问图中的节点，层与层之间是按距离起始节点的远近来定义的。
3.适用于无权图的最短路径：BFS 能在无权图中找到从起始节点到目标节点的最短路径。
示例BFS遍历下图

    0
   / \
  1   2
 / \   
3   4  

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_VERTICES 5  // 最大顶点数（本例中为 5）
#define MAX_QUEUE_SIZE 100  // 队列的最大大小

// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES];

// visited 数组用于记录顶点是否被访问过
bool visited[MAX_VERTICES];

// 队列结构
typedef struct {
    int items[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == -1;
}

// 队列入队
void enqueue(Queue* q, int value) {
    if (q->rear == MAX_QUEUE_SIZE - 1) {
        printf("队列已满！\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

// 队列出队
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("队列为空！\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front++;
    if (q->front > q->rear) {
        q->front = q->rear = -1;  // 队列为空
    }
    return value;
}

// 广度优先搜索（BFS）函数
void bfs(int startVertex, int n) {
    Queue q;
    initQueue(&q);

    // 将起始顶点入队，并标记为已访问
    visited[startVertex] = true;
    enqueue(&q, startVertex);

    while (!isEmpty(&q)) {
        int currentVertex = dequeue(&q);
        printf("%d ", currentVertex);

        // 遍历当前顶点的所有相邻顶点
        for (int i = 0; i < n; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;  // 标记相邻顶点为已访问
                enqueue(&q, i);  // 将未访问的相邻顶点入队
            }
        }
    }
}

int main() {
    int n = 5;  // 顶点数
    int m = 4;  // 边数

    // 初始化图的邻接矩阵和 visited 数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // 输入图的边（无向图）
    graph[0][1] = 1; graph[1][0] = 1;  // 0-1
    graph[0][2] = 1; graph[2][0] = 1;  // 0-2
    graph[1][3] = 1; graph[3][1] = 1;  // 1-3
    graph[1][4] = 1; graph[4][1] = 1;  // 1-4

    // 从顶点 0 开始进行 BFS
    printf("广度优先搜索的结果:\n");
    bfs(0, n);

    return 0;
}

BFS 与 DFS 的区别：
DFS（深度优先搜索） 是“深度优先”，BFS 是“广度优先”。
DFS 会一直沿着一条路径走下去，直到没有未访问的邻居，之后才会回溯；BFS 则是逐层访问，保证了先访问起始节点的所有邻居，再访问下一层。
BFS 在无权图中可以保证找到最短路径，而 DFS 不一定。

---

在图论中，**最小生成树（Minimum Spanning Tree，MST） **是一个无向连通加权图的生成树，其边的权重之和最小。生成树是图的一部分，它包含图中所有的节点，并且是一个树结构（无环连通图）。
最小生成树边与点的关系：最小生成树的顶点数n与边数e之间的关系：n=e+1

普里姆算法（Prim）算法

Prim 算法 是一种贪心算法，用来求解图的最小生成树。它从一个节点出发，逐步选择最小权重的边，直到图中的所有节点都被包含在内。与 Kruskal 算法 相比，Prim 算法更适用于稠密图。

Prim 算法的基本思想：
1.从图的任意一个节点开始，加入最小生成树的集合。
2.在已加入的节点集合所相连的边中，选择一条最小权重的边，将其相邻的节点加入集合。
3.重复步骤 2，直到所有节点都被加入最小生成树中。

#include <stdio.h>
#include <limits.h>  // 包含 INT_MAX

#define MAX_VERTICES 5  // 图中的顶点数

// 图的邻接矩阵表示（用 -1 表示没有边）
int graph[MAX_VERTICES][MAX_VERTICES] = {
    {0, 2, 3, 4, -1},
    {2, 0, -1, 5, -1},
    {3, -1, 0, 1, -1},
    {4, 5, 1, 0, -1},
    {-1, -1, -1, -1, 0}
};

// Prim 算法函数
void prim(int n) {
    int parent[MAX_VERTICES];  // 存储最小生成树的父节点
    int key[MAX_VERTICES];     // 存储每个顶点到生成树的最小边权值
    int inMST[MAX_VERTICES];   // 判断顶点是否在最小生成树中

    // 初始化所有值
    for (int i = 0; i < n; i++) {
        key[i] = INT_MAX;    // 关键值初始化为无穷大
        inMST[i] = 0;        // 所有顶点都不在最小生成树中
        parent[i] = -1;      // 没有父节点
    }
    key[0] = 0;  // 从顶点 0 开始

    for (int count = 0; count < n - 1; count++) {
        // 选择一个最小权值的顶点
        int u = -1;
        int min = INT_MAX;
        for (int v = 0; v < n; v++) {
            if (!inMST[v] && key[v] < min) {
                min = key[v];
                u = v;
            }
        }

        // 将选择的顶点 u 加入最小生成树
        inMST[u] = 1;

        // 更新与 u 相邻的顶点的关键值
        for (int v = 0; v < n; v++) {
            // graph[u][v] != -1 表示 u 和 v 之间有边
            if (graph[u][v] != -1 && !inMST[v] && graph[u][v] < key[v]) {
                key[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }

    // 输出最小生成树的边和权值
    printf("最小生成树的边和权值：\n");
    for (int i = 1; i < n; i++) {
        printf("%d - %d: %d\n", parent[i], i, graph[i][parent[i]]);
    }
}

int main() {
    int n = 5;  // 图中的顶点数
    prim(n);  // 调用 Prim 算法
    return 0;
}

克鲁斯卡尔(Kruskal)算法

Kruskal 算法 是求解最小生成树的另一种经典算法。它是一个贪心算法，选择图中权重最小的边，将它们逐步添加到生成树中，确保每次添加的边不会形成环。Kruskal 算法非常适合用于稀疏图。
Kruskal 算法的基本思想
1.排序：将图中的所有边按边的权重进行升序排序。
2.并查集：使用并查集（Union-Find）数据结构来判断添加边后是否形成环。若添加的边连接了两个不同的连通分量，则将这两个分量合并；若它们已经在同一个连通分量中，则跳过这条边。
3.构建最小生成树：从排序后的边中依次选择，若选择的边不形成环，则将其添加到最小生成树中，直到最小生成树中包含 V-1 条边（V 是节点的数量）。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5  // 顶点数

// 边的结构体
typedef struct {
    int u, v, weight;
} Edge;

// 并查集的数据结构
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];

// 初始化并查集
void initUnionFind(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;  // 每个顶点的父节点初始化为自己
        rank[i] = 0;     // 初始秩为 0
    }
}

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

// 合并操作（按秩合并）
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
        // 按秩合并
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// 比较函数，用于按权值升序排序边
int compare(const void* a, const void* b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

// 克鲁斯卡尔算法
void kruskal(Edge edges[], int n, int m) {
    // 初始化并查集
    initUnionFind(n);

    // 排序边
    qsort(edges, m, sizeof(Edge), compare);

    int mstWeight = 0;
    printf("最小生成树的边和权值：\n");

    // 遍历所有边，选择不形成环的边
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int weight = edges[i].weight;

        if (find(u) != find(v)) {
            unionSets(u, v);
            printf("%d - %d: %d\n", u, v, weight);
            mstWeight += weight;
        }
    }

    printf("最小生成树的总权值：%d\n", mstWeight);
}

int main() {
    // 图的边（每条边包含两个顶点和边的权值）
    Edge edges[] = {
        {0, 1, 2},
        {0, 2, 3},
        {0, 3, 4},
        {1, 3, 5},
        {2, 3, 1}
    };
    int n = 5;  // 顶点数
    int m = 5;  // 边数

    // 调用克鲁斯卡尔算法
    kruskal(edges, n, m);

    return 0;
}

迪杰斯特拉(Dijkstra)算法

#include <stdio.h>
#include <limits.h>  // 包含 INT_MAX，表示无穷大
#include <stdbool.h>

#define MAX_VERTICES 6  // 顶点数

// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES] = {
    {0, 7, -1, 9, 9, -1},
    {7, 0, 5, 6, -1, -1},
    {-1, 5, 0, -1, -1, 8},
    {9, 6, -1, 0, 4, 1},
    {9, -1, -1, 4, 0, 3},
    {-1, -1, 8, 1, 3, 0}
};

// 迪杰斯特拉算法
void dijkstra(int start, int n) {
    int dist[MAX_VERTICES];       // 存储起点到各个顶点的最短距离
    bool visited[MAX_VERTICES];   // 标记顶点是否已访问过

    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;    // 设置初始距离为无穷大
        visited[i] = false;   // 标记所有顶点为未访问
    }
    dist[start] = 0;   // 起点到自身的距离为 0

    for (int count = 0; count < n - 1; count++) {
        // 在未访问的顶点中找到最小的距离
        int u = -1;
        int minDist = INT_MAX;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && dist[v] < minDist) {
                minDist = dist[v];
                u = v;
            }
        }

        // 标记该顶点为已访问
        visited[u] = true;

        // 更新与 u 相邻的顶点的距离
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != -1 && !visited[v] && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];  // 更新最短距离
            }
        }
    }

    // 输出最短路径
    printf("从顶点 %d 到其他顶点的最短路径为：\n", start);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INT_MAX) {
            printf("%d 到 %d: 无路径\n", start, i);
        } else {
            printf("%d 到 %d: %d\n", start, i, dist[i]);
        }
    }
}

int main() {
    int n = 6;  // 图中的顶点数
    int start = 0;  // 起点选择 0

    // 调用 Dijkstra 算法
    dijkstra(start, n);

    return 0;
}

---

我们一天天地活着并不是理所当然，而是莫大的奇迹。归根结底，连我们此刻的心脏搏动都是一种奇迹。 ​ —星野道夫