数据结构---图的遍历

图的遍历(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-1graph[0][2] = 1; graph[2][0] = 1;  // 0-2graph[1][3] = 1; graph[3][1] = 1;  // 1-3graph[1][4] = 1; graph[4][1] = 1;  // 1-4// 从顶点 0 开始进行 DFSprintf("深度优先搜索的结果:\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-1graph[0][2] = 1; graph[2][0] = 1;  // 0-2graph[1][3] = 1; graph[3][1] = 1;  // 1-3graph[1][4] = 1; graph[4][1] = 1;  // 1-4// 从顶点 0 开始进行 BFSprintf("广度优先搜索的结果:\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;   // 起点到自身的距离为 0for (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;
}

---

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