算法设计与分析课程算法编程实训

实验题目：Prim算法生成最小生成树(MST)原理及算法实现 一、实验目的 本实验旨在理解和掌握Prim算法的基本原理，并通过编程实现该算法，以求解给定无向加权图的最小生成树。通过本实验，能够加深对最小生成树概念的理解，并提升编程能力。 二、实验原理 Prim算法是一种求解最小生成树的贪心算法。其基本原理是：从任意一个顶点开始，每次选择连接已选择的顶点集合与未选择的顶点集合之间的最短边，并将该边的另一个顶点加入已选择的顶点集合，直到所有顶点都被选择为止。最终，所选的边构成的就是最小生成树。 实验题目：克鲁斯卡尔（Kruskal）算法生成最小生成树(MST)原理及算法实现 一、实验目的 本实验旨在理解和掌握克鲁斯卡尔（Kruskal）算法的基本原理，并通过编程实现该算法，以求解给定无向加权图的最小生成树。通过本实验，能够加深对最小生成树概念的理解，并提升编程能力。 二、实验原理 克鲁斯卡尔算法是一种求解最小生成树的贪心算法。其基本原理是：首先，将所有边按照权重从小到大进行排序；然后，从权重最小的边开始，如果这条边连接的两个顶点不在同一个集合中（即不构成环），则将其加入最小生成树中，并将… ### 知识点一：Prim算法生成最小生成树(MST) #### 实验目的 - **理解与掌握**：深入理解Prim算法的基本原理及其在解决最小生成树问题中的应用。 - **编程实现**：通过编程实践，熟悉Prim算法的实现过程，并能够应用于具体的无向加权图上。 - **深化理解**：通过对最小生成树概念的学习，进一步提高对贪心算法策略的认识。 - **编程能力提升**：在实验过程中，增强解决实际问题的能力，特别是利用C++编程语言实现算法的能力。 #### 实验原理 Prim算法是基于贪心策略的一种高效算法，用于寻找给定无向加权图的最小生成树(Minimum Spanning Tree, MST)。算法的核心思想是从任意一个顶点开始逐步构建最小生成树，每次选择连接当前已选顶点集合与未选顶点集合之间的最短边，直至所有顶点均被包含在内。 #### 实验步骤 1. **初始化**： - 创建两个集合：已加入最小生成树的顶点集合(U)和未加入最小生成树的顶点集合(V-U)。 - 初始化minCut数组，用于记录V-U中各顶点到U的距离。将初始顶点设为0，其余顶点的距离设为无穷大。 - 初始化isInMST数组，用于标识顶点是否已被添加到最小生成树中。 - 初始化parent数组，用于记录最小生成树中的父节点关系。 2. **选择顶点**： - 在minCut数组中选择距离最小的顶点v1，并将其添加到U集合中。 - 更新V-U中与v1相邻的所有顶点的距离，如果新边的权重小于当前顶点的minCut值，则更新该顶点的minCut值，并将父节点设为v1。 3. **迭代过程**： - 重复上述选择顶点和更新距离的过程，直到所有顶点均被加入到U集合中。 - 最终，parent数组中存储了最小生成树的边信息。 #### 算法实现 采用C++编程语言实现Prim算法的关键代码如下： ```cpp #include <iostream> #include <vector> #define _CRT_SECURE_NO_WARNINGS using namespace std; int findNextVertex(vector<bool>& isInMst, vector<int>& minCut) { int minDist = INT_MAX; int index = -1; for (int i = 0; i < isInMst.size(); i++) { if (isInMst[i] == false && minCut[i] < minDist) { minDist = minCut[i]; index = i; } } return index; } vector<int> primMST(vector<vector<int>>& graph) { if (graph.size() == 0) { return vector<int>(); } vector<int> parents(graph.size(), -1); vector<bool> isInMst(graph.size(), false); vector<int> minCut(graph.size(), INT_MAX); minCut[0] = 0; for (int i = 0; i < isInMst.size(); i++) { int index = findNextVertex(isInMst, minCut); isInMst[index] = true; // 更新相邻顶点的距离 // 省略具体实现细节 } // 返回最小生成树的边信息 return parents; } ``` ### 知识点二：克鲁斯卡尔（Kruskal）算法生成最小生成树(MST) #### 实验目的 - **理解与掌握**：深入了解克鲁斯卡尔算法的基本原理及其在求解最小生成树问题中的应用。 - **编程实现**：通过编程实践，熟悉克鲁斯卡尔算法的实现过程，并能够应用于具体的无向加权图上。 - **深化理解**：通过学习克鲁斯卡尔算法，进一步理解贪心算法策略以及并查集数据结构的应用。 - **编程能力提升**：在实验过程中，增强解决实际问题的能力，特别是在C++编程语言中实现算法的能力。 #### 实验原理 克鲁斯卡尔算法也是一种基于贪心策略的算法，用于寻找给定无向加权图的最小生成树(MST)。与Prim算法不同的是，克鲁斯卡尔算法先对所有的边按权重大小排序，然后依次选择边加入最小生成树，只要这条边不会形成环路。 #### 实验步骤 1. **排序**：将所有边按照权重从小到大排序。 2. **选择边**：依次检查每条边，如果该边的两个端点不在同一个集合中（即加入该边不会形成环路），则将该边加入到最小生成树中，并将两个端点所在的集合合并。 3. **迭代过程**：重复上述选择边的过程，直到最小生成树包含了所有的顶点或所有边都被检查过。 #### 算法实现 采用C++编程语言实现克鲁斯卡尔算法的关键代码如下： ```cpp #include <iostream> #include <vector> #include <algorithm> #define _CRT_SECURE_NO_WARNINGS using namespace std; struct Edge { int src, dest, weight; }; bool compare(Edge e1, Edge e2) { return e1.weight < e2.weight; } int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } void unionSets(int parent[], int x, int y) { int xset = find(parent, x); int yset = find(parent, y); parent[xset] = yset; } vector<Edge> kruskalMST(vector<Edge>& edges, int numVertices) { sort(edges.begin(), edges.end(), compare); vector<Edge> result; int e = 0; int i = 0; int parent[numVertices]; for (int i = 0; i < numVertices; i++) parent[i] = -1; while (e < numVertices - 1) { Edge nextEdge = edges[i++]; int x = find(parent, nextEdge.src); int y = find(parent, nextEdge.dest); if (x != y) { result.push_back(nextEdge); unionSets(parent, x, y); e++; } } return result; } ``` 通过以上两个知识点的详细阐述，不仅介绍了Prim算法和克鲁斯卡尔算法的基本原理和实现方法，还提供了相应的C++代码示例，有助于读者更深入地理解和掌握这些核心算法。