数据结构与算法(长期更新)

栈与队列

逆波兰表达式

中缀表达式转化为后缀表达式

转换规则（调度场算法）：

• 操作数直接输出。
• 运算符根据优先级处理，优先级高的先输出，同优先级左结合。
• 左括号 ( 入栈；遇到右括号 ) 时，弹出栈内运算符直到遇到左括号。
• 扫描完毕后，将栈中剩余运算符依次弹出。

举例

原始表达式：a/b+(c*d-e*f)/g

最终后缀表达式：ab/cd*ef*-g/+

后缀表达式求值

算法步骤

• 从左到右扫描后缀表达式
• 遇到操作数 → 压入操作数栈
• 遇到运算符 → 弹出两个操作数（先右后左），计算结果压回栈中
• 扫描结束，栈顶即为表达式值

补充：先弹出的操作数对应运算符右侧的操作数，后弹出的对应运算符左侧的操作数。

举例

设：a=8, b=2, c=3, d=4, e=5, f=6, g=2 后缀表达式：ab/cd*ef*-g/+

结果：-5

代码实现

// 运算符优先级
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 中缀转后缀
string infixToPostfix(const string& infix) {
    stack<char> st;
    string postfix = "";
    
    for (char ch : infix) {
        // 如果是操作数（字母或数字）
        if (isalnum(ch)) {
            postfix += ch;
            postfix += ' ';  // 用空格分隔
        }
        // 如果是左括号
        else if (ch == '(') {
            st.push(ch);
        }
        // 如果是右括号
        else if (ch == ')') {
            while (!st.empty() && st.top() != '(') {
                postfix += st.top();
                postfix += ' ';
                st.pop();
            }
            st.pop();  // 弹出 '('
        }
        // 如果是运算符
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            while (!st.empty() && precedence(st.top()) >= precedence(ch)) {
                postfix += st.top();
                postfix += ' ';
                st.pop();
            }
            st.push(ch);
        }
    }
    
    // 弹出栈中剩余运算符
    while (!st.empty()) {
        postfix += st.top();
        postfix += ' ';
        st.pop();
    }
    
    return postfix;
}

// 后缀表达式求值
double evaluatePostfix(const string& postfix, map<char, double>& values) {
    stack<double> st;
    
    for (int i = 0; i < postfix.length(); i++) {
        char ch = postfix[i];
        
        // 跳过空格
        if (ch == ' ') continue;
        
        // 如果是操作数
        if (isalpha(ch)) {
            st.push(values[ch]);
        }
        // 如果是数字（多位数处理）
        else if (isdigit(ch)) {
            double num = 0;
            while (i < postfix.length() && isdigit(postfix[i])) {
                num = num * 10 + (postfix[i] - '0');
                i++;
            }
            i--;  // 回退一格
            st.push(num);
        }
        // 如果是运算符
        else {
            double b = st.top(); st.pop();
            double a = st.top(); st.pop();
            
            switch (ch) {
                case '+': st.push(a + b); break;
                case '-': st.push(a - b); break;
                case '*': st.push(a * b); break;
                case '/': st.push(a / b); break;
            }
        }
    }
    
    return st.top();
}

字符串

KMP算法

关键定义

前缀表（next数组）

定义

记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

• 前缀：不包含最后一个字符的所有以第一个字符开头的连续子串。
• 后缀：不包含第一个字符的所有以最后一个字符结尾的连续子串。

举例

作用

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

代码实现

void getNext(int* next, const string& s) { 
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
}
// j指向前缀末尾位置，i指向后缀末尾位置
// j还代表着当前i之前（包括i）子串的最长相等前后缀的长度。
// 主要聚焦于i指针，代表当前遍历到的子串的最后一个位置
int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        vector<int> next(needle.size());
        getNext(next,needle);
        int j=0;
        for(int i=0;i<haystack.size();i++){
            while(j>0&&haystack[i]!=needle[j]) j=next[j-1];
            if(haystack[i]==needle[j]) j++;
            if(j==needle.size()) return i-j+ 1;
        }
        return -1;
}
// i为当前遍历到的haystack字符串的位置
// j为当前遍历到的needle字符串的位置

• 时间复杂度: O(n + m)
• 空间复杂度: O(m)

二叉树

理论基础

遍历方式

DFS

递归遍历

递归三部曲

• 确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
• 确定终止条件 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
• 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 递归函数中，什么时候需要返回值？ 如果需要搜索整棵二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。

前序遍历

 void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }

中序遍历

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

迭代遍历

前序遍历

vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }

后序遍历

vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }

中序遍历

 vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }

统一迭代法

BFS(层序遍历)

vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }

应用

• 对称二叉树（双指针遍历）
• 另一棵树的子树
• 二叉树的最大深度
• 二叉树的最小深度
• 二叉树的最近公共祖先（空节点做标记）

二叉搜索树

验证二叉搜索树

• 关键点：中序遍历下，输出的二叉搜索树节点的数值是升序序列。

看到题目中出现二叉搜索树，首先想到该特性。

二叉搜索树的插入

TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root)           return new TreeNode(val);
        if(root->val>val)   root->left=insertIntoBST(root->left,val);
        if(root->val<val)   root->right=insertIntoBST(root->right,val);
        return  root;
}

二叉搜索树的删除

TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
}

平衡二叉树（AVL树）

理论理解

代码模板

#include <iostream>
#include <algorithm> 
using namespace std;

struct AVLNode {
    int val;         
    AVLNode* left;    
    AVLNode* right;   
    int height;       // 节点高度（叶子节点高度=1，空节点高度=0）

    AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};

// 1. 获取节点高度（空节点高度为0）
int getHeight(AVLNode* node) {
    if (node == nullptr) return 0;
    return node->height;
}

// 2. 更新节点高度：当前节点高度 = 左右子树高度的最大值 + 1
void updateHeight(AVLNode* node) {
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}

// 3. 计算平衡因子：平衡因子 = 左子树高度 - 右子树高度
// 平衡因子绝对值>1 时，节点失衡
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// ===================== 旋转操作（核心） =====================
/**
 * 右旋转（处理LL型失衡）
 * 失衡场景：节点的平衡因子>1，且左孩子的平衡因子≥0
 * 旋转逻辑：
 *        y                            x
 *       / \                         /   \
 *      x   T3  右旋转 (y)          z     y
 *     / \       ------->         / \   / \
 *    z   T2                     T1 T4 T2 T3
 *   / \
 *  T1 T4
 */
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;    // x是y的左孩子
    AVLNode* T2 = x->right;  // T2是x的右子树

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新高度（先更子节点y，再更父节点x）
    updateHeight(y);
    updateHeight(x);

    return x;  // 返回旋转后的新根节点x
}

/**
 * 左旋转（处理RR型失衡）
 * 失衡场景：节点的平衡因子<-1，且右孩子的平衡因子≤0
 * 旋转逻辑：
 *    y                            x
 *   / \                         /   \
 *  T1  x  左旋转 (y)          y     z
 *     / \  ------->         / \   / \
 *    T2  z                 T1 T2 T3 T4
 *       / \
 *      T3 T4
 */
AVLNode* leftRotate(AVLNode* y) {
    AVLNode* x = y->right;   // x是y的右孩子
    AVLNode* T2 = x->left;   // T2是x的左子树

    // 执行旋转
    x->left = y;
    y->right = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;  // 返回旋转后的新根节点x
}

// ===================== 插入操作 =====================
/**
 * 递归插入节点（核心逻辑）
 * 步骤：
 * 1. 普通二叉搜索树的插入
 * 2. 更新当前节点高度
 * 3. 计算平衡因子，判断是否失衡
 * 4. 失衡则根据类型旋转恢复平衡
 */
AVLNode* insert(AVLNode* root, int val) {
    // 第一步：普通BST插入
    if (root == nullptr) {
        return new AVLNode(val);  // 空节点，创建新节点
    }
    if (val < root->val) {
        root->left = insert(root->left, val);  // 插入左子树
    } else if (val > root->val) {
        root->right = insert(root->right, val); // 插入右子树
    } else {
        return root;  // 不允许重复值，直接返回
    }

    // 第二步：更新当前节点的高度
    updateHeight(root);

    // 第三步：计算平衡因子，检查是否失衡
    int balance = getBalanceFactor(root);

    // 第四步：处理4种失衡情况
    // 1. LL型：平衡因子>1，左孩子平衡因子≥0 → 右旋转
    if (balance > 1 && getBalanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }
    // 2. RR型：平衡因子<-1，右孩子平衡因子≤0 → 左旋转
    if (balance < -1 && getBalanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }
    // 3. LR型：平衡因子>1，左孩子平衡因子<0 → 先左旋左孩子，再右旋当前节点
    if (balance > 1 && getBalanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    // 4. RL型：平衡因子<-1，右孩子平衡因子>0 → 先右旋右孩子，再左旋当前节点
    if (balance < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    // 未失衡，返回原根节点
    return root;
}

哈夫曼树

定义

哈夫曼树（也叫最优二叉树）：对于一组带有确定权值的叶子节点，构造的二叉树中带权路径长度（WPL）最小的二叉树。

构建思路

反复合并最小权值的两棵树，直到只剩一棵

struct Compare{
    bool operator()(HuffmanNode* a,HuffmanNode* b){
        return a->weight>b->weight;
    }
};
HuffmanNode* buildHuffmanTree(const vector<int> &weights){
    priority_queue<HuffmanNode*,vector<HuffmanNode*>,Compare> minHeap;
    for(int weight:weights) minHeap.push(new HuffmanNode(weight));
    while(minHeap.size()>1){
        HuffmanNode* left=minHeap.top();
        minHeap.pop();
        HuffmanNode* right=minHeap.top();
        minHeap.pop();
        HuffmanNode* parent= new HuffmanNode(left->weight+right->weight);
        parent->left=left;
        parent->right=right;
        minHeap.push(parent);
    }
    return minHeap.top();
}
int calculateWPL(HuffmanNode* root,int depth){
    if(!root) return 0;
    if(!root->left&&!root->right) return root->weight*depth;
    return calculateWPL(root->left,depth+1)+calculateWPL(root->right,depth+1);
}

哈夫曼编码

左分支标记为 0，右分支标记为 1

m阶B-树

性质

• 阶数约束：每个节点最多有 m 个子节点。
• 关键字数量范围： 非根节点（无论叶子或非叶子）：关键字数 k 满足 ⌈m/2⌉ - 1 ≤ k ≤ m - 1； 根节点：若为非叶子节点，1 ≤ k ≤ m - 1；若为树中唯一节点（叶子），k 可为 0 或 1。 子节点与关键字数量关系：节点的子节点数 = 关键字数 + 1。
• 有序性与范围约束： 单个节点内的关键字严格升序排列； 子树关键字范围由父节点关键字划分，左子树关键字小于对应父关键字，右子树关键字大于对应父关键字。
• 平衡性质：所有叶子节点都位于同一层。
• 动态维护性质：插入时节点关键字数超上限则触发分裂，删除时节点关键字数低于下限则触发借关键字或合并，操作后仍保持所有核心性质。

区别

• B - 树：关键字分布在所有节点，叶子节点和非叶子节点都存数据；
• B + 树：仅叶子节点存数据，非叶子节点只存索引，叶子节点通过链表相连（更适合范围查询）；

查找

查找方法评价指标

• 平均查找长度(ASL)：查找过程中主要操作是关键字的比较，查找过程中关键字的平均比较次数（平均查找长度）作为衡量一个查找算法效率高低的标准。
• ASL=Pi*Ci(累加)
• Pi为查找第i个元素的概率
• Ci为找到第i个元素所需的关键字与给定值的比较次数

查找方法分类

• 顺序表和链表的查找
• 哈希表的查找
• 索引查找表的查找

二分查找

代码模板

// 关键：确定好循环不变量的定义。确定好if()括号内判断的逻辑。
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

经典题

• 跳石头

哈希表

理论基础

排序

排序算法的稳定性

• 在待排序序列中，若存在两个或多个关键字相等的元素，排序后它们的相对顺序与排序前保持一致，则称该排序算法是「稳定的」；反之则为「不稳定的」。

衡量排序方法的标准

• 平均比较次数
• 平均移动
• 平均辅助存储空间
• 稳定性

插入排序

直接插入排序

基本思想

将数组划分为已排序（初始仅首个元素）和未排序区间，依次取出未排序区间的元素，向前插入到已排序区间的合适位置（保证已排序区间始终有序），直至所有元素插入完成。

代码模板

void insertionSort(std::vector<T>& arr) {
    // 空数组或单元素数组无需排序
    if (arr.size() <= 1) return;

    // 已排序区间初始为 [0]，未排序区间从 i=1 开始遍历
    for (int i = 1; i < arr.size(); ++i) {
        // 保存当前待插入的元素（避免移动过程中被覆盖）
        T temp = arr[i];
        // j 指向已排序区间的最后一个元素，向前遍历找插入位置
        int j = i - 1;

        // 向前比较：若已排序元素 > 待插入元素，则后移（腾出插入位置）
        // 相等元素不移动 → 保证稳定性
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];  // 元素后移
            --j;                  // 继续向前找
        }

        // 找到插入位置（j+1），放入待插入元素
        arr[j + 1] = temp;
    }
}

• 时间复杂度：O (n²)
• 稳定排序

举例

以数组 [5, 2, 9, 3, 7] 为例，直接插入排序过程如下（已排序区间用「」标注，未排序区间用 () 标注）： 初始状态：「5」，(2, 9, 3, 7) 取未排序首元素 2，插入「5」的合适位置 → 「2, 5」，(9, 3, 7) 取 9，插入「2, 5」末尾（9>5）→ 「2, 5, 9」，(3, 7) 取 3，向前比较：5>3 则后移，2≤3 则插入 → 「2, 3, 5, 9」，(7) 取 7，向前比较：9>7 则后移，5≤7 则插入 → 「2, 3, 5, 7, 9」（完成）。

希尔排序

基本思想

希尔排序基本思想：作为直接插入排序的改进算法，先按递减的增量（步长）将数组划分为若干个子序列，对每个子序列分别执行直接插入排序；逐步缩小增量直至为 1，最后对整个数组执行一次直接插入排序（此时数组已基本有序，大幅降低插入排序的时间开销）。

代码模板

template <typename T>
void insertionSortWithGap(std::vector<T>& arr, int gap) {
    int n = arr.size();
    if (n <= 1) return;

    // 逻辑和普通插入排序完全一致，仅将“1”改为“gap”
    for (int i = gap; i < n; ++i) {
        T temp = arr[i]; // 保存待插入元素
        int j = i-gap; // 已排序序列最后一个元素
        // 向前遍历子序列（步长gap），找到插入位置
        while (j >= 0 && arr[j] > temp) {
            arr[j + gap] = arr[j]; // 元素后移（步长gap）
            j -= gap;
        }
        arr[j + gap] = temp; // 插入到合适位置
    }
}

// 希尔排序
template <typename T>
void shellSort(std::vector<T>& arr) {
    int n = arr.size();
    if (n <= 1) return;

    // 外层仅控制步长（增量），核心排序逻辑复用插入排序
    for (int gap = n / 2; gap > 0; gap /= 2) {
        std::cout << "当前步长gap=" << gap << "，调用带步长的插入排序" << std::endl;
        insertionSortWithGap(arr, gap); // 复用插入排序处理当前步长的子序列
    }
}

• 时间复杂度：O (n log n) ~ O (n²) 之间
• 不稳定排序

举例

数组：[8,5,9,1,7,2,6,4] 选短数组 + 简单间隔（8→4→2→1） 初始状态 数组：[8, 5, 9, 1, 7, 2, 6, 4]数组长度 n=8，初始间隔（gap）=8/2=4 第一步：gap=4（大间隔分组粗排） 分组规则：索引差 4 为一组，共 4 组 组 1（索引 0、4）：8、7 → 插入排序后：7、8 组 2（索引 1、5）：5、2 → 插入排序后：2、5 组 3（索引 2、6）：9、6 → 插入排序后：6、9 组 4（索引 3、7）：1、4 → 插入排序后：1、4 排序后数组：[7, 2, 6, 1, 8, 5, 9, 4]（从完全乱序→初步有序） 第二步：gap=2（缩小间隔再粗排） 分组规则：索引差 2 为一组，共 2 组 组 1（索引 0、2、4、6）：7、6、8、9 → 插入排序后：6、7、8、9 组 2（索引 1、3、5、7）：2、1、5、4 → 插入排序后：1、2、4、5 排序后数组：[6, 1, 7, 2, 8, 4, 9, 5]（更接近有序，仅需微调） 第三步：gap=1（间隔 1 = 普通插入排序） 此时数组[6,1,7,2,8,4,9,5]已基本有序，插入排序仅需少量调整： 1 插到 6 前 → [1,6,7,2,8,4,9,5] 2 插到 6 前 → [1,2,6,7,8,4,9,5] 4 插到 6 前 → [1,2,4,6,7,8,9,5] 5 插到 9 前 → 最终：[1,2,4,5,6,7,8,9]

交换排序

冒泡排序

基本思想

• 俩俩比较待排序对象的关键字

代码模板

void bubbleSort(int arr[], int n) {
    // 外层循环：控制排序轮数（n个元素最多需要n-1轮）
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false; // 优化：标记本轮是否发生交换（提前终止）
        // 内层循环：每轮比较相邻元素，把最大的"冒泡"到末尾
        // 每轮结束后，末尾i个元素已排好，无需重复比较
        for (int j = 0; j < n - 1 - i; ++j) {
            // 相邻元素逆序，交换位置
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); 
                swapped = true; // 标记有交换发生
            }
        }
        // 本轮无交换 → 数组已完全有序，直接退出（优化效率）
        if (!swapped) break;
    }
}

• 时间复杂度：O(n²)
• 稳定排序（判断条件为arr[j] ==>== arr[j+1]）

举例

数组初始状态：21 25 49 25* 16 8 第一趟：21 25 25* 16 8 49 第二趟：21 25 16 8 25* 49 第三趟：21 16 8 25 25* 49 第四趟：16 8 21 25 25* 49 第五趟：8 16 21 25 25* 49

快速排序

思路

• 选一个基准值； 遍历数组，将比基准小的放左、大的放右，基准归位（最终排序位置）； 递归对基准左右的子数组重复操作，直到子数组仅 1 个元素（天然有序）。

代码模板

vector<int> sortArray(vector<int>& nums) {
        sort(nums,0,nums.size()-1);
        return nums;
    }

    void sort(vector<int> &nums,int l,int r){
        if(l>=r) return;
        int x=nums[l],i=l-1,j=r+1;
        while(i<j){
            do i++;while(nums[i]<x);
            do j--;while(nums[j]>x);
            if(i<j) swap(nums[i],nums[j]);
        }
        sort(nums,l,j);
        sort(nums,j+1,r);
    }

• 时间复杂度：复杂度 O (n log n)
• 不稳定排序 适用于n较大的情况

选择排序

简单选择排序

基本思想

• 外层循环：遍历数组，确定每轮要归位的位置（第i轮处理索引i）； 内层循环：在[i, 数组末尾]的未排序区间，找到最小值的索引； 交换：将最小值与未排序区间的第一个元素（索引i）交换，完成该位置的归位； 重复上述步骤，直到所有元素归位。

代码模板

void selectionSort(int arr[], int n) {
    // 外层循环：确定每轮归位的位置i（0到n-2，最后1个元素无需处理）
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i; // 初始化最小值索引为当前未排序区间的第一个位置
        // 内层循环：在[i, n-1]找最小值的索引
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j; // 更新最小值索引
            }
        }
        // 交换：把最小值放到索引i的位置（归位）
        swap(arr[i], arr[minIdx]);
    }
}

• 时间复杂度：O(n²)
• 不稳定排序

举例

数组初始状态：6, 3, 8, 5, 9, 1, 7, 2, 4, 0 第一轮 [0, 3, 8, 5, 9, 1, 7, 2, 4, 6] 第二轮 [0, 1, 8, 5, 9, 3, 7, 2, 4, 6] 第三轮 [0, 1, 2, 5, 9, 3, 7, 8, 4, 6] 第四轮 [0, 1, 2, 3, 9, 5, 7, 8, 4, 6] 第五轮 [0, 1, 2, 3, 4, 5, 7, 8, 9, 6] 第六轮 不变 第七轮 [0, 1, 2, 3, 4, 5, 6, 8, 9, 7] 第八轮 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8] 第九轮 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

树形选择排序(打擂台)

模拟

     15
    25 15
  25 28 19 15
49 25 37 28 19 65 15 34

每个枝结点的关键字都等于其左、右孩子结点中较小的关键字，根结点是最小的。 输出最小关键字后，只需将叶子结点中的最小关键字改为最大值，然后重复上述步骤即可

堆排序

前置知识

• 堆是基于完全二叉树的一种数据结构，核心满足「堆序性」，分为两种类型（升序排序常用大顶堆）：

• 数组模拟堆（索引从 0 开始）： 父节点 i 的左子节点：2i+1，右子节点：2i+2； 子节点 j 的父节点：(j-1)/2（整数除法）。
• 堆的特点：序列中第一个元素为序列中最大（最小）值

代码模板

    //大顶堆->升序 
    // unsortLen为未排序区间（0,,,unsortLen）左闭右闭
    void heapAdjust(vector<int>& nums,int root,int unsortLen){
        int lChild=2*root+1,rChild=2*root+2;
        int maxIdx=root;
        if(lChild<=unsortLen&&nums[lChild]>nums[maxIdx]) maxIdx=lChild;
        if(rChild<=unsortLen&&nums[rChild]>nums[maxIdx]) maxIdx=rChild;
        if(root!=maxIdx){
            swap(nums[root],nums[maxIdx]);
            heapAdjust(nums,maxIdx,unsortLen);
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size()-1;
        for(int root=(n-1)/2;root>=0;root--) heapAdjust(nums,root,n);// 子节点 j 的父节点：(j-1)/2（整数除法）。
        for(int unsortLen=n;unsortLen>0;unsortLen--){
            swap(nums[0],nums[unsortLen]);
            heapAdjust(nums,0,unsortLen-1);
        }
        return nums;
    }

    //小顶堆->降序
    void heapAdjust(vector<int>& nums,int root,int unsortLen){
        int lChild=2*root+1,rChild=2*root+2;
        int minIdx=root;
        if(lChild<=unsortLen&&nums[lChild]<nums[minIdx]) minIdx=lChild;
        if(rChild<=unsortLen&&nums[rChild]<nums[minIdx]) minIdx=rChild;
        if(root!=minIdx){
            swap(nums[root],nums[minIdx]);
            heapAdjust(nums,minIdx,unsortLen);
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size()-1;
        for(int root=(n-1)/2;root>=0;root--) heapAdjust(nums,root,n);// 子节点 j 的父节点：(j-1)/2（整数除法）。
        for(int unsortLen=n;unsortLen>0;unsortLen--){
            swap(nums[0],nums[unsortLen]);
            heapAdjust(nums,0,unsortLen-1);
        }
        return nums;
    }

• 时间复杂度：O(nlogn)
• 排序不稳定

归并排序

思路

分（拆分）：将待排序数组从中间递归拆分为左右两个子数组，直到每个子数组仅含 1 个元素（单个元素天然有序）。 治（合并）：将两个有序的子数组，通过双指针逐个比较、按大小合并为一个有序数组，逐层向上合并后得到最终有序数组。

代码模板

int temp[10005];
void merge_sort(vector<int> &num,int l,int r){
    if(l>=r) return;
    int mid = (l+r)/2;
    merge_sort(num,l,mid),merge_sort(num,mid+1,r);
    int k=0,i=l,j=mid+1;
    // 双指针比较，把较小元素放入temp
    while(i<=mid&&j<=r)
    if(num[i]<=num[j]) temp[k++] = num[i++];// 如果是num[i]<num[j]排序会变得不稳定。
    else temp[k++] = num[j++];
    // 处理左子数组剩余元素
    while(i<=mid) temp[k++]=num[i++];
    // 处理右子数组剩余元素
    while(j<=r) temp[k++]=num[j++];
    // 把temp中有序数据复制回原数组num的[l, r]区间
    for(i=l,j=0;i<=r;i++,j++) num[i]=temp[j]; 
}

• 时间复杂度：O(nlogn)
• 排序稳定

图论

图的遍历

深度搜索DFS

三部曲

• 确认递归函数参数
• 确认终止条件
• 处理目前搜索节点出发的路径

思路

代码框架

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

模板题

代码模板

//邻接矩阵写法
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径

void dfs (const vector<vector<int>>& graph, int x, int n) {
    // 当前遍历的节点x 到达节点n 
    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
        if (graph[x][i] == 1) { // 找到 x链接的节点
            path.push_back(i); // 遍历到的节点加入到路径中来
            dfs(graph, i, n); // 进入下一层递归
            path.pop_back(); // 回溯，撤销本节点
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));

    while (m--) {
        cin >> s >> t;
        // 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的
        graph[s][t] = 1;
    }

    path.push_back(1); // 无论什么路径已经是从0节点出发
    dfs(graph, 1, n); // 开始遍历

    // 输出结果
    if (result.size() == 0) cout << -1 << endl;
    for (const vector<int> &pa : result) {
        for (int i = 0; i < pa.size() - 1; i++) {
            cout << pa[i] << " ";
        }
        cout << pa[pa.size() - 1]  << endl;
    }
}

//邻接表写法
#include <iostream>
#include <vector>
#include <list>
using namespace std;

vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径

void dfs (const vector<list<int>>& graph, int x, int n) {

    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i : graph[x]) { // 找到 x指向的节点
        path.push_back(i); // 遍历到的节点加入到路径中来
        dfs(graph, i, n); // 进入下一层递归
        path.pop_back(); // 回溯，撤销本节点
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<list<int>> graph(n + 1); // 邻接表
    while (m--) {
        cin >> s >> t;
        // 使用邻接表 ，表示 s -> t 是相连的
        graph[s].push_back(t);

    }

    path.push_back(1); // 无论什么路径已经是从0节点出发
    dfs(graph, 1, n); // 开始遍历

    // 输出结果
    if (result.size() == 0) cout << -1 << endl;
    for (const vector<int> &pa : result) {
        for (int i = 0; i < pa.size() - 1; i++) {
            cout << pa[i] << " ";
        }
        cout << pa[pa.size() - 1]  << endl;
    }
}

广度搜索BFS

使用场景

适合于解决两个点之间的最短路径问题。

求单源最短路径，何时用BFS？何时用dijkstra？

是否需要求解最短路径？ → 是 → 图的边权是否相等（或无权）？ → 是 → 用 BFS（高效简洁） → 否 → 边权是否非负？ → 是 → 用 Dijkstra 算法（贪心+优先队列） → 否 → 用 Bellman-Ford/SPFA 算法（处理负权）

思路

代码模板

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

}

大家应该好奇，这一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历。 很多网上的资料都是直接说用队列来实现。 其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。 用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。 因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。 如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。 因为栈是先进后出，加入元素和弹出元素的顺序改变了。 那么广搜需要注意 转圈搜索的顺序吗？ 不需要！ 所以用队列，还是用栈都是可以的，但大家都习惯用队列了，所以下面的讲解用我也用队列来讲，只不过要给大家说清楚，并不是非要用队列，用栈也可以。

并查集

适用场景

• 需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。（常用来解决连通性问题）

思路

代码模板

class Union{
private:
    vector<int> father;
public:
// 初始化
    Union(int num){
        father.resize(num);
        for(int i=0;i<num;++i) father[i]=i;
    }
// 并查集里寻根的过程
    int find(int u){
        if(u==father[u]) return u;
        father[u]=find(father[u]);//路径压缩
        return father[u];
    }// 核心
// 将u-v 这条边加入并查集
    void join(int u,int v){
        u=find(u);
        v=find(v);
        if(u==v) return;
        father[u]=v;
    }
// 判断 u 和 v是否找到同一个根
    bool isSame(int u,int v){
        return find(u)==find(v);
    }
};

模板题

最小生成树

概念

生成树：是一个极小连通子图，它含有图中的全部顶点，但只有n-1条边。 生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。 最小生成树：所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

prim算法

三部曲

第一步，选距离生成树最近节点 第二步，最近节点加入生成树 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

适用条件：无向图 连通图 无回路 权值无论正负

模板题

思路

代码模板

#include<iostream>
#include<vector>
#include <climits>

using namespace std;
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
    // 填一个默认最大值，题目描述val最大为10000
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
    while (e--) {
        cin >> x >> y >> k;
        // 因为是双向图，所以两个方向都要填上
        grid[x][y] = k;
        grid[y][x] = k;

    }
    // 所有节点到最小生成树的最小距离
    vector<int> minDist(v + 1, 10001);

    // 这个节点是否在树里
    vector<bool> isInTree(v + 1, false);

    // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
    for (int i = 1; i < v; i++) {

        // 1、prim三部曲，第一步：选距离生成树最近节点
        int cur = -1; // 选中哪个节点 加入最小生成树
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始
            //  选取最小生成树节点的条件：
            //  （1）不在最小生成树里
            //  （2）距离最小生成树最近的节点
            if (!isInTree[j] &&  minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }
        // 2、prim三部曲，第二步：最近节点（cur）加入生成树
        isInTree[cur] = true;

        // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
        // cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下
        // 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢
        for (int j = 1; j <= v; j++) {
            // 更新的条件：
            // （1）节点是 非生成树里的节点
            // （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小
            // 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
            }
        }
    }
    // 统计结果
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += minDist[i];
    }
    cout << result << endl;

}

kruskal算法

思路

边的权值排序，因为要优先选最小的边加入到生成树里 遍历排序后的边 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

代码模板

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge{
    int u;
    int v;
    int w;
};
class Union{
private:
    vector<int> father;
public:
    Union(int n){
        father.resize(n+1);
        for(int i=1;i<=n;i++) father[i]=i;
    }
    int find(int u){
        if(u==father[u]) return father[u];
        father[u]=find(father[u]);
        return father[u];
    }
    void join(int u,int v){
        u=find(u);
        v=find(v);
        if(u==v) return;
        father[u]=v;
    }
    bool isSame(int u,int v){
        return find(u)==find(v);
    }
};
int main(){
    int v,e;
    cin>>v>>e;
    vector<Edge> edges;
    for(int i=0;i<e;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edges.push_back({u,v,w});
    }
    sort(edges.begin(),edges.end(),[&](const Edge a,const Edge b){
        return a.w<b.w;
    });
    Union setv(v);
    int result=0;
    for(auto edge:edges){
        if(!setv.isSame(edge.u,edge.v)){
            setv.join(edge.u,edge.v);
            result+=edge.w;
        } 
    }
    cout<<result;
}

prim与kruskal对比总结

• prim维护的是节点的集合，而 Kruskal 维护的是边的集合。
• Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。
• Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。

拓扑排序

前置概念

• AOV网：用顶点表示活动的网络
• AOE网：用边表示活动的网络

适用场景

• 给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。
• 拓扑排序也是图论中判断有向无环图的常用方法。

思路

• 找到入度为0 的节点，加入结果集
• 将该节点从图中移除
• 循环以上俩步

代码模板

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    vector<int> inDegree(N,0);
    vector<list<int>> graph(N);
    queue<int> q;
    vector<int> result;
    for(int i=0;i<M;i++){
        int S,T;
        cin>>S>>T;
        graph[S].push_back(T);
        inDegree[T]++;
    }
    for(int i=0;i<N;i++) if(inDegree[i]==0) q.push(i);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        result.push_back(cur);
        for(int i:graph[cur]) if(--inDegree[i]==0) q.push(i);
    }
    if(result.size()==N){
        for(int i=0;i<N-1;i++) cout<<result[i]<<" ";
        cout<<result[N-1];
    }else cout<<-1<<endl;
}

判断是否有环

• 结果集元素个数 不等于 图中节点个数，我们就可以认定图中一定有 有向环！

时间复杂度

• O(n+e)

AOE网络核心定义

• Ve(j)：从起点到本节点的最长的路径。意味着事件最早能够发生的时刻。
• Vl(j)：不影响工程的如期完工，本节点事件必须发生的时刻。
• e(ai)：活动的最早开始时间 e(ai)=Ve(j)
• l(ai)：活动的最迟开始时间 l(ai)=Vl(k)-dut(j,k)
• 关键活动：最早开始时间=最迟开始时间的活动
• 关键路径：从原点到汇点的最长的一条路径，或者全部由关键活动构成的路径

AOE网络关键路径求解

• 核心步骤： 拓扑排序得到拓扑序列； 按拓扑序计算Ve（事件最早发生时间）； 按逆拓扑序计算Vl（事件最迟发生时间）； 计算所有活动的e和l，找出关键活动； 关键活动构成的路径即为关键路径。
• 代码模板

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;

// 边结构体：to=邻接顶点，weight=活动持续时间
struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

int main() {
    int N, M; // N=事件数（顶点），M=活动数（边）
    cin >> N >> M;
    vector<list<Edge>> graph(N);       // 正邻接表
    vector<list<Edge>> reverseGraph(N);// 逆邻接表（用于逆拓扑序计算Vl）
    vector<int> inDegree(N, 0);
    vector<int> Ve(N, 0);              // 事件最早发生时间
    vector<int> Vl(N, INT_MAX);        // 事件最迟发生时间
    vector<int> topoOrder;             // 拓扑序列
    queue<int> q;
    
    // 构建图
    for (int i = 0; i < M; i++) {
        int S, T, W;
        cin >> S >> T >> W;
        graph[S].emplace_back(T, W);
        reverseGraph[T].emplace_back(S, W);
        inDegree[T]++;
    }
    
    // 步骤1：拓扑排序
    for (int i = 0; i < N; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        topoOrder.push_back(cur);
        for (auto& edge : graph[cur]) {
            if (--inDegree[edge.to] == 0) q.push(edge.to);
        }
    }
    if (topoOrder.size() != N) {
        cout << "存在环，无法计算关键路径" << endl;
        return 0;
    }
    
    // 步骤2：计算Ve（拓扑序）
    for (int u : topoOrder) {
        for (auto& edge : graph[u]) {
            int v = edge.to;
            Ve[v] = max(Ve[v], Ve[u] + edge.weight);
        }
    }
    
    // 步骤3：计算Vl（逆拓扑序）
    Vl[topoOrder.back()] = Ve[topoOrder.back()]; // 汇点Vl=Ve
    for (int i = topoOrder.size() - 2; i >= 0; i--) {
        int u = topoOrder[i];
        for (auto& edge : graph[u]) {
            int v = edge.to;
            Vl[u] = min(Vl[u], Vl[v] - edge.weight);
        }
    }
    
    // 步骤4：输出关键活动和工程最短完成时间
    cout << "关键活动（边<u,v>）：" << endl;
    for (int u = 0; u < N; u++) {
        for (auto& edge : graph[u]) {
            int v = edge.to;
            int e = Ve[u];          // 活动最早开始时间
            int l = Vl[v] - edge.weight; // 活动最迟开始时间
            if (e == l) {
                cout << "<" << u << "," << v << "> （持续时间：" << edge.weight << "）" << endl;
            }
        }
    }
    cout << "工程最短完成时间：" << Ve[topoOrder.back()] << endl;
    
    return 0;
}

最短路径

dijkstra算法

• 模板题

朴素版dijkstra

三部曲

1、选源点到哪个节点近且该节点未被访问过 (源点距离源点最近，距离为0，且未被访问。) 2、该最近节点被标记访问过 (标记源点访问过) 3、更新非访问节点到源点的距离 (即更新minDist数组)

限制条件

==单源==最短路，即可求一点出发到任意点的最短路径。 不能出现==负数权值==

与prim算法的区别

对比prim算法的三部曲： 第一步，选距离生成树最近节点 第二步，最近节点加入生成树 第三步，更新非生成树节点到生成树的距离（即更新minDist数组） prim算法支持负数权值

代码模板

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    // 存储从源点到每个节点的最短距离
    std::vector<int> minDist(n + 1, INT_MAX);

    // 记录顶点是否被访问过
    std::vector<bool> visited(n + 1, false);

    minDist[start] = 0;  // 起始点到自身的距离为0

    for (int i = 1; i <= n; i++) { // 遍历所有节点

        int minVal = INT_MAX;
        int cur = 1;

        // 1、选距离源点最近且未访问过的节点
        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && minDist[v] < minVal) {
                minVal = minDist[v];
                cur = v;
            }
        }

        visited[cur] = true;  // 2、标记该节点已被访问

        // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
                minDist[v] = minDist[cur] + grid[cur][v];
            }
        }

    }

    if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout << minDist[end] << endl; // 到达终点最短路径

}

复杂度

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)

如何求路径？

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    std::vector<int> minDist(n + 1, INT_MAX);

    std::vector<bool> visited(n + 1, false);

    minDist[start] = 0; 

    //加上初始化
    vector<int> parent(n + 1, -1);

    for (int i = 1; i <= n; i++) {

        int minVal = INT_MAX;
        int cur = 1;

        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && minDist[v] < minVal) {
                minVal = minDist[v];
                cur = v;
            }
        }

        visited[cur] = true;

        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
                minDist[v] = minDist[cur] + grid[cur][v];
                parent[v] = cur; // 记录边
            }
        }

    }

    // 输出最短情况
    for (int i = 1; i <= n; i++) {
        cout << parent[i] << "->" << i << endl;
    }
}

打印结果：

-1->1
1->2
2->3
3->4
4->5
2->6
5->7

堆优化版dijkstra

优化方向

用最小堆自动排序，时间缩短至logn。 用邻接表优化邻接矩阵（适用于稀疏图）

前置知识

堆： 一般用stl中的优先队列(priority_queue)实现。 自定义堆的排序规则: 一般用自定义比较结构体实现

struct Node { int val; int weight; };
// 自定义比较器：按weight降序（weight大的优先级高）
struct CompareNode {
    bool operator()(const Node& a, const Node& b) {
        return a.weight < b.weight; // comp(a,b) = a.weight < b.weight
    }
};

priority_queue<Node, vector<Node>, CompareNode> pq;
pq.push({1, 5}); // a
pq.push({2, 3}); // b

如何确定优先级？

要理解「comp(a, b) = true 则 b 优，false 则 a 优」的底层原理，核心要抓住两个关键点： C++ priority_queue 的底层是二叉堆，堆的核心规则是「父节点优先级 ≥ 子节点优先级」； 比较器 comp 的设计语义是：判断 a 是否应该被放在 b 的下方（优先级更低） —— 这是 STL 对 “严格弱序” 比较器的标准化设计。

快速验证：

目标：x(weight=3) 优先级 > y(weight=5)； 比较器：comp(a,b) = a.weight > b.weight； 计算 comp(x,y) = 3>5 → false → 符合预期（x 优先级高）。

代码模板

Edge(int t, int w): to(t), val(w) {}  // 构造函数

vector<list<Edge>> grid(n + 1);

for(int i = 0; i < m; i++){
    cin >> p1 >> p2 >> val; 
    // p1 指向 p2，权值为 val
    grid[p1].push_back(Edge(p2, val));

}

int start = 1;  // 起点
int end = n;    // 终点

// 存储从源点到每个节点的最短距离
std::vector<int> minDist(n + 1, INT_MAX);

// 记录顶点是否被访问过
std::vector<bool> visited(n + 1, false); 

// 优先队列中存放 pair<节点，源点到该节点的权值>
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;


// 初始化队列，源点到源点的距离为0，所以初始为0
pq.push(pair<int, int>(start, 0)); 

minDist[start] = 0;  // 起始点到自身的距离为0

while (!pq.empty()) {
    // 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）
    // <节点， 源点到该节点的距离>
    pair<int, int> cur = pq.top(); pq.pop();

    if (visited[cur.first]) continue;

    // 2. 第二步，该最近节点被标记访问过
    visited[cur.first] = true;

    // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
    for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
        // cur指向的节点edge.to，这条边的权值为 edge.val
        if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
            minDist[edge.to] = minDist[cur.first] + edge.val;
            pq.push(pair<int, int>(edge.to, minDist[edge.to]));
        }
    }

}

if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径

###### 复杂度
- 时间复杂度：O(ElogE) E 为边的数量
- 空间复杂度：O(N + E) N 为节点的数量
#### Floy算法
##### 核心：动态规划求多源最短路径（对边的权值正负没有要求）
##### 思路：最好直接看[三维讲解](https://programmercarl.com/kamacoder/0097.%E5%B0%8F%E6%98%8E%E9%80%9B%E5%85%AC%E5%9B%AD.html#%E6%80%9D%E8%B7%AF)
##### 动态规划五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
##### 变量定义
- grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。
- 递推公式定义（俩种情况）：
节点i 到 节点j 的最短路径经过节点k
节点i 到 节点j 的最短路径不经过节点k
- 遍历顺序(和积分类似，以k为基础，遍历ij面，对于每k层的每个ij点，更新其最小值)：从k=0层开始向上递推==更新==
##### 代码模板
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // 因为边的最大距离是10^4
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2][0] = val;
        grid[p2][p1][0] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end][n] == 10005) cout << -1 << endl;
        else cout << grid[start][end][n] << endl;
    }
}