第九章 图论算法（最小生成树）
Prim算法Prim算法是一种用于寻找加权连通图的最小生成树（MST）的贪心算法。该算法从任意一个顶点开始，逐步将最近的未访问过的顶点添加到正在构建的最小生成树中，直到所有顶点都被包含在内。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;const int MAX = 100; // 假设图的最大顶点数为100int graph[MAX][MAX]; // 图的邻接矩阵表示bool visited[MAX]; // 访问标记数组int parent[MAX]; ...
第六章 优先队列（堆）
提醒注意vector元素之间赋值要调用move函数 二叉堆结构性质 类的声明123456789101112131415161718192021222324252627282930313233#pragma one#include<vector>#include<iostream>using namespace std;template<typename Comparable>class BinaryHeap{public: explicit BinaryHeap(vector<Comparable>& items) :this->array(items.size()+10),this->currentSize(items.size()) { for (int i = 0; i < items.size(); i++) { this->array[i + 1] =...
第四章 树（AVL树)
AVL树节点声明12345678910111213static const int ALLOWED_IMBALANCE = 1;//AVL树允许的最大高度差struct AvlNode{ int element; AvlNode* left;//左子节点 AvlNode* right;//右子节点 int height;//高度 AvlNode(const int& e, AvlNode* lt, AvlNode* rt, int h = 0) :element(e),left(lt),right(rt),height(h){} AvlNode(int && e,AvlNode*lt,AvlNode*rt,int h=0) :element(move(e)),left(lt),right(rt),height(h){}}; 函数height1234int height(AvlNode* t)//返回节点的高度，如果节点没有子节点则返回-1{ return t == nullptr...
第九章 图论算法（搜索和拓扑排序）
搜索图的类12345678910111213141516171819202122232425#include <iostream>#include <list>#include <vector>#include<queue>using namespace std;class Graph { int V; // 图的顶点数 vector<list<int>> adj; // 邻接表public: Graph(int V); // 构造函数 void addEdge(int v, int w); // 添加边 void DFSUtil(int v, bool visited[]); // 用于DFS的辅助递归函数 void DFS(int v); // 深度优先遍历函数 void BFS(int s); // 宽度优先遍历函数};Graph::Graph(int V) { this->V = V; ...
第九章 图论算法（最短路径）
Dijkstra算法Dijkstra算法是一种用于寻找带权重图中单源最短路径的经典算法。它适用于非负权重的图。算法的基本思想是从起点开始，逐步扩展到其他顶点，每次都选择当前距离最小的顶点进行扩展，直到所有顶点都被处理完毕。 在C++中，可以使用优先队列（通常使用std::priority_queue）来高效地实现Dijkstra算法。 代码实现Graph类123456789101112131415161718192021222324252627#include <iostream>#include <vector>#include <queue>#include <limits>#include <utility>using namespace std;const int INF = numeric_limits<int>::max();class Graph { int V; // 图的顶点数 vector<vector<pair<int,...
