图论

图论

树

树是由N个节点构成的有限集合，当N=0的时候称之为空树。树也可以看做是存储数据的一种数据类型，其逻辑结构常见的有二叉树，完全二叉树等等；树的节点和数的深度是有关系的，对于一个深度为K的满二叉树来说，它的节点个数2^K-1其中减去1是减去了根节点。

一个树且当N>1的时候，其余节点可以分为M个有限互不相交的有限集合。每一个节点算是一个独立的树，称之为根的子树。在树中，与其他数据结构一样，有前驱和后继的设定。对于根节点来说，它没有直接前驱。对于底部的叶节点来说，它没有直接后继。

树适合表示有层级的结构的数据，类似于游戏中的阶段，或者随机生成的地图。都需要记录前一个状态，然后跳转到另一个状态。状态的区别就是其节点的子和父属性。

一个树有几种基础属性

• 结点：组成树的基本变量
• 度：结点孩子个数
• 深度，高度：深度从根节点开始向下计数，高度从叶节点向上计数。如果我们知道一个二叉树的节点个数，那么可以估计高度的数量级大概为h=log2(N+1)

二叉树*

二叉树是由N个节点组成的有限集合，其基本形态包括：空树、仅有根节点、只有左子树、只有右子树、左右子树均存在等。每个节点最多有两个子节点，分别为左子树和右子树，且它们是有序的，不能互换。在二叉树中，不存在度大于2的节点。

满二叉树

如图是一个满二叉树，可以看到每一个层级中，其节点个数都是符合2^n（n为层级）

满二叉树满足以下特点：

• 叶子节点只出现在最下面一层。
• 非叶子节点的度一定为 2。
• 在同等深度的二叉树中，满二叉树的节点个数最多，叶子节点个数最多。

对于深度为 k 的满二叉树，节点编号是从根节点开始，按照层次依次编号，每一层从左到右进行编号。满二叉树的总节点数可以通过公式 2^k−1计算（这里 k 是树的深度，深度从1开始）。深度为 k 的满二叉树最后一个节点的编号应该是 2^k−1。

完全二叉树

在完全二叉树中，除了最底层外，其余每一层的节点数都达到了最大值。最底层的节点全部集中在最左侧，且可能未完全填满。如果最底层为第 h 层，则该层包含的节点数范围为 1 到 2^h−1 个。完全二叉树满足以下特点：

• 叶子节点只能出现在最下面两层。
• 最下层的叶子节点一定集中在该层最左边的位置上。
• 倒数第二层如果有叶子节点，则该层的叶子节点一定集中在右边的位置上。
• 如果节点的度为 1，则该节点只偶遇左孩子节点，即不存在只有右子树的情况。
• 同等节点数的二叉树中，完全二叉树的深度最小。

二叉树构造

二叉树的存储结构分为两种：「顺序存储结构」和「链式存储结构」

顺序存储结构

使用顺序存储结构实现二叉树，也就是使用一维数组存储二叉树的节点，节点存储位置则采用完全二叉树的节点层次编号，按照层次从上至下，每一层从左至右的顺序依次存放二叉树的数据元素。在进行顺序存储时，如果对应的二叉树节点不存在，则设置为「空节点」。

数组模拟二叉树，原理是改数组索引定义，采用0-based索引，也就是数组的0号位置设置为根节点，对于任意节点的索引为 i

• 左子节点的索引为 2i + 1。
• 右子节点的索引为 2i + 2。
• 父节点的索引为 (i - 1) / 2（当 i ≠ 0 时）

也可以采用1-base索引，这样就不用多一步+运算，对于任意节点的索引 i：

• 左子节点的索引为 2i。
• 右子节点的索引为 2i + 1。
• 父节点的索引为 i / 2（当 i ≠ 1 时）。

//结构体定义节点属性
struct TreeNode{
  int val;
  TreeNode *left; //定义left指针 指向左子树
  TreeNode *right;//right指针 指向右子树
  TreeNode(int x):val(x),left(NULL),right(NULL){}//构造函数初始化  
};

// 构建二叉树
TreeNode* buildTree(vector<int>& arr, int index) {
    if (index >= arr.size() || arr[index] == -1) {
        return nullptr; // 返回空指针表示空节点
    }

    TreeNode* root = new TreeNode(arr[index]);
    root->left = buildTree(arr, 2 * index + 1); // 构建左子树
    root->right = buildTree(arr, 2 * index + 2); // 构建右子树

    return root;
}

对于完全二叉树尤其是满二叉树来说，采用顺序存储结构比较合适，它能充分利用存储空间；而对于一般二叉树，如果需要设置很多的「空节点」，则采用顺序存储结构就会浪费很多存储空间。并且，由于顺序存储结构固有的一些缺陷，会使得二叉树的插入、删除等操作不方便，效率也比较低。对于二叉树来说，当树的形态和大小经常发生动态变化时，更适合采用链式存储结构。

链式存储结构

二叉树采用链式存储结构时，每个链节点包含一个用于数据域val，存储节点信息；还包含两个指针域 left 和 right，分别指向左右两个孩子节点，当左孩子或者右孩子不存在时，相应指针域值为空。二叉链节点结构如下图所示。

链式存储结构实现二叉树很好理解，每一个节点都由指向左右子树的指针。下面是实现节点的伪代码

// 构建二叉树的函数，输入一个数组，输出顺序存储形式的二叉树
void buildBinaryTree(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == -1) {
            continue; // 跳过空节点
        }

        // 当前节点的值
        int node_value = arr[i];
        printf("Node %d: %d\n", i, node_value);

        // 计算左子节点的索引
        int left_index = 2 * i + 1;
        if (left_index < size && arr[left_index] != -1) {
            printf("  Left child of node %d: %d\n", i, arr[left_index]);
        } else {
            printf("  Left child of node %d: NULL\n", i);
        }

        // 计算右子节点的索引
        int right_index = 2 * i + 2;
        if (right_index < size && arr[right_index] != -1) {
            printf("  Right child of node %d: %d\n", i, arr[right_index]);
        } else {
            printf("  Right child of node %d: NULL\n", i);
        }
    }
}

二叉树的链表存储结构具有灵活、方便的特点。节点的最大数目只受系统最大可存储空间的限制。一般情况下，二叉树的链表存储结构比顺序存储结构更省空间（用于存储指针域的空间开销只是二叉树中节点数的线性函数），而且对于二叉树实施相关操作也很方便，因此，一般我们使用链式存储结构来存储二叉树。

二叉树遍历

遍历的目的是为了找到这个二叉树每一个节点的存储的数据，可以根据二叉树的逻辑拓扑来构造遍历的函数，通常由三种遍历方式。递归遍历，层序遍历还有优先级遍历。

当我们使用递归遍历二叉树时，可以将其视作由三个部分构成的树：左子树、右子树和根节点。这种视角下，有三种经典的遍历方式：

1. 前序遍历（Preorder traversal）：根节点 -> 左子树 -> 右子树
2. 中序遍历（Inorder traversal）：左子树 -> 根节点 -> 右子树
3. 后序遍历（Postorder traversal）：左子树 -> 右子树 -> 根节点

递归的优势在于它能够让代码保持简洁和易读。相比之下，如果不使用递归，需要借助栈或数组来模拟递归的调用过程，这会导致代码量大大增加，并且难以维护和理解。

递归本质上是将一个大问题划分为多个小问题，并通过递归调用逐步解决这些小问题，最终实现对整个大问题的解决。在遍历二叉树时，每次递归调用都是在处理一个子树，这种分而治之的策略使得遍历操作变得清晰而高效。

因此，递归在处理树结构时具有显著的优势，能够简化代码逻辑，提高代码的可读性和可维护性，同时也更符合树的自然结构和递归定义的思想。

为了实现递归遍历，首先得声明一下二叉树的节点，每一个节点都要有两个指针，标记该节点的左右子树。其实在逻辑上和双链表是一样的。

struct TreeNode{
  int val;
  TreeNode *left;//定义left指针 指向左子树
  TreeNode *right;//right指针 指向右子树
  TreeNode(int x):val(x),left(NULL),right(NULL){}//构造函数  
};

前序遍历

二叉树的前序遍历规则为：如果二叉树为空，则返回。如果二叉树不为空，则：

• 访问根节点。
• 以前序遍历的方式遍历根节点的左子树。
• 以前序遍历的方式遍历根节点的右子树

struct TreeNode{
  int val;
  TreeNode *left; //定义left指针 指向左子树
  TreeNode *right; //right指针 指向右子树
  TreeNode(int x):val(x),left(NULL),right(NULL){}//构造函数  
};

void PT(TreeNode root)
{
    //如果访问的节点没有子节点
    if(nullptr == root) return;
    
    //打印遍历的节点数据
    cout<<root->data;
    
    //递归遍历左子树
    PT(root -> left);
    
    //递归遍历右子树
    PT(root -> right);    
    
}

如下图所示，该二叉树的前序遍历顺序为：A−B−D−H−I−E−C−F−J−G−K

二叉树的前序遍历递归实现的过程，实际上就是调用系统栈的过程。我们也可以使用数组模拟栈来实现前序遍历，但是会显得特别复杂。

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;  // 指向左子树
    TreeNode *right; // 指向右子树
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

void PreorderTraversal(TreeNode* root) {
    if (root == nullptr) return; // 如果根节点为空，直接返回
    
    const int MAX_SIZE = 100; // 假设树的最大节点数为100
    TreeNode* stack[MAX_SIZE]; // 创建模拟栈的数组
    int top = -1; // 栈顶指针

    // 从根节点开始入栈
    stack[++top] = root;

    while (top != -1) { // 当栈不为空时循环
        // 出栈
        TreeNode* node = stack[top--];
        
        // 访问当前节点
        cout << node->val << " ";

        // 先右子树入栈，再左子树入栈
        // 这样左子树在栈顶，会优先被访问
        if (node->right != nullptr) {
            stack[++top] = node->right; // 右子树入栈
        }
        if (node->left != nullptr) {
            stack[++top] = node->left; // 左子树入栈
        }
    }
}

int main() {
    // 示例树：
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "前序遍历结果：";
    PreorderTraversal(root);
    cout << endl;

    // 释放内存（略，实际应用中应考虑内存管理）

    return 0;
}

前序遍历的顺序为：根节点 - 左子树 - 右子树，而根据栈的「先入后出」特点，所以入栈的顺序应该为：先放入右子树，再放入左子树。这样可以保证最终遍历顺序为前序遍历顺序。

中序遍历

二叉树的中序遍历规则为：如果二叉树为空，则返回。如果二叉树不为空

• 以中序遍历的方式遍历根节点的左子树。
• 访问根节点。
• 以中序遍历的方式遍历根节点的右子树。

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
  	//和上面相比，就改变了顺序
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

从二叉树的中序遍历规则可以看出，中序遍历是一个递归过程。在遍历任何一棵子树时，顺序是先遍历子树的左子树，然后访问根节点，最后再遍历右子树。因此，对于给定的二叉树，其中序遍历顺序为：H−D−I−B−E−A−F−J−C−K−G。

中序遍历的特征是中间节点永远夹在左右子节点之间。然而，仅仅依赖于中序遍历的顺序，我们无法唯一确定二叉树的根节点或其结构。要准确确定树的形状，需要结合前序遍历或后序遍历的信息。

后序遍历

二叉树的后序遍历规则为：如果二叉树为空，则返回。如果二叉树不为空，则：

• 以后序遍历的方式遍历根节点的左子树。
• 以后序遍历的方式遍历根节点的右子树。
• 访问根节点。

从二叉树的后序遍历规则可以看出：后序遍历过程也是一个递归过程。在遍历任何一棵子树时仍然是按照先遍历子树根节点的左子树，然后遍历子树根节点的右子树，最后再访问根节点的顺序进行遍历。如下图所示，该二叉树的后序遍历顺序为：H−I−D−E−B−J−F−K−G−C−A

// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    postorderTraversal(root->left); //左子树变为新的根节点
    postorderTraversal(root->right); //右子树变为新的根节点
    cout << root->data << " ";
}

这里模拟一下，访问到H节点，由于H节点无直接后继，那么其执行的两个函数的返回值将是空。

postorderTraversal(root->left); //左子树变为新的根节点
postorderTraversal(root->right); //右子树变为新的根节点

也就是说，这个时候打印的节点信息就是H这个点的节点信息了。第一次访问到的节点必定是H节点，因为在递归栈中，先压入的都是这个函数。

postorderTraversal(root->left); //左子树变为新的根节点

压到H这个节点的时候结束程序，也就输出H的这个程序弹出栈了。也就是第一次执行完成了上面的程序，然后再压入；重复上述流程，就可以用后续遍历输出所有节点的值了。

postorderTraversal(root->right); //右子树变为新的根节点

后续遍历：直观的描述就是每一个子树的根节点最后遍历到，也就是相对于左右子节点来说最后一个输出根节点的值（每一个子树）。

层序遍历

二叉树的层序遍历：遍历过程是一个广度优先搜索过程。在遍历的时候是按照第 1 层、第 2 层、…… 最后一层依次遍历的，而同一层节点则是按照从左至右的顺序依次访问的。如下图所示，该二叉树的层序遍历顺序为：A−B−C−D−E−F−G−H−I−J−K

二叉树的层序遍历是通过队列实现的，按照从上到下、从左到右的顺序访问树的节点。具体步骤如下：

1. 判断二叉树是否为空：如果树为空，直接返回。
2. 将根节点入队：将树的根节点添加到队列中。
3. 循环遍历
   • 当队列不为空时，获取当前队列的长度 si，即当前层节点的数量。每层的节点数量是以指数形式增长的，例如，根节点的数量为 2^0，第一层为 2^1，以此类推，直到叶子节点。
   • 依次从队列中出队 si 个节点，并对这些节点进行访问。
   • 对于每个被访问的节点，将其左右子节点（如果存在）入队。
4. 结束遍历：当队列为空时，遍历结束。

这种方法确保了每一层的节点在被访问时，其顺序是正确的，因为队列遵循先进先出的原则。

typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

// 创建新节点
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 队列节点结构
typedef struct QueueNode {
    Node* treeNode;
    struct QueueNode* next;
} QueueNode;

// 队列结构
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

// 入队
void enqueue(Queue* queue, Node* treeNode) {
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->treeNode = treeNode;
    newQueueNode->next = NULL;

    if (queue->rear == NULL) {
        // 队列为空时，前后指针都指向新节点
        queue->front = queue->rear = newQueueNode;
        return;
    }
    
    // 将新节点添加到队列的末尾
    queue->rear->next = newQueueNode;
    queue->rear = newQueueNode;
}

// 出队
Node* dequeue(Queue* queue) {
    if (queue->front == NULL) {
        return NULL; // 如果队列为空，返回NULL
    }

    QueueNode* temp = queue->front;
    Node* treeNode = temp->treeNode;
    queue->front = queue->front->next;

    // 如果队列变为空，更新后指针
    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    free(temp);
    return treeNode;
}

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

// 二叉树的层序遍历
void levelOrder(Node* root) {
    if (root == NULL) return; // 如果根节点为空，直接返回

    Queue* queue = createQueue(); // 创建队列
    enqueue(queue, root); // 将根节点入队

    while (!isEmpty(queue)) { // 当队列不为空时循环
        Node* node = dequeue(queue); // 获取并移除队列头部元素
        printf("%d ", node->key); // 访问节点

        // 将左右孩子节点加入队列
        if (node->left != NULL) {
            enqueue(queue, node->left);
        }
        if (node->right != NULL) {
            enqueue(queue, node->right);
        }
    }

    printf("\n"); // 输出换行以分隔结果
}

// 示例使用
int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("层序遍历结果：\n");
    levelOrder(root); // 输出层序遍历结果

    // 释放内存（略，实际应用中应考虑内存管理）

    return 0;
}

还原二叉树

题目是依靠二叉树的前中后序的信息，来推出对应的另一个序列。如果仅仅知道前后的二叉树遍历结果，我们无法确定唯一的根节点位置，或者说节点的值的位置。

• 前序遍历的第一元素是整个二叉树的根节点

• 中序遍历中根节点的左边的元素是左子树，根节点右边的元素是右子树

• 后序遍历的最后一个元素是整个二叉树的根节点

前序遍历和中序遍历

题目：已知，前序遍历：ABCDEF。中序遍历：CBDAEF 求解构造的数和后序遍历。

第一步：先看前序遍历A肯定是根节点

第二步：确认了根节点，再来看中序遍历，中序遍历中根节点A的左边是CBD，右边是EF，所有可以确定二叉树既有左子树又有右子树

第三步：先来分析左子树CBD，那么CBD谁来做A的左子树呢？这个时候不能直接用中序遍历的特点（左->根->右）得出左子树应该是这个样子

因为有两种情况都满足中序遍历为CBD

直接根据中序遍历来直接得出左子树的结构，这个时候就要返回到前序遍历中去确认

观察前序遍历ABCDEF，左子树CBD在前序遍历中的顺序是BCD，意味着B是左子树的根节点（这么说可能不太好理解，换个说法就是B是A的左子树）,得出这个结果是因为如果一个二叉树的根节点有左子树，那么这个左子树一定在前序遍历中一定紧跟着根节点（这个是用前序遍历的特点（根->左->右）得出的）,到这里就可以确认B是左子树的根节点

第四步：再观察中序遍历CBDAEF，B元素左边是C右边是D，说明B节点既有左子树又有右子树，左右子树只有一个元素就可以直接确定了，不用再返回去观察前序遍历

第五步：到这里左子树的重建就已经完成了，现在重建右子树，因为重建右子树的过程和左子树的过程一模一样，观察中序遍历右子树为EF，再观察前序遍历ABCDEF中右子树。

总结：步骤就是通过前序序列确定根节点，然后用中序序列确定根节点的左右分布。然后再对分布出来的，子树通过前序序列确定子树节点，然后用中序序列确定这个子树的节点的左右分布。如此递归，最终就得到了完整的树。

如果是手写就按照以下步骤：

1. 根据前序序列确定根节点
2. 在中序序列中分部分，根节点左侧为左子树部分，右侧为右子树部分。然后根据左右的字母分布，在前序序列中也分为左子树部分和右子树部分。如果字母分部不对称，跳过这一步。
3. 前序序列根节点之后的第一节点必是其左子树节点（如果前面划了分布，那么其右子树部分的第一个节点必是根节点的右子树节点)
4. 然后就是对确定的节点，在中序遍历上找他们的子树，如果他们子树不是叶子结点就需要重复上面的工作再划分。也就是递归，一般不会超出三层。试试就行^ ^。

中序遍历和后序遍历

• 中序遍历：CBDAEF

• 后序遍历为：CDBFEA

其实步骤与已知前序中序求后序差不多，步骤如下

1. 从后序遍历中确定根节点。后序遍历的最后一个元素是树的根节点。
2. 划分左右子树：在中序遍历中，以根节点为界，将序列分为左子树和右子树：
   • 根节点左侧的元素为左子树部分。
   • 根节点右侧的元素为右子树部分。
3. 根据后序遍历中的元素顺序来确定左右子树的根节点：
   • 左子树的根节点是后序遍历根节点之前的第一个元素。
   • 右子树的根节点是左子树根节点后的最后一个元素（如果存在右子树）。
4. 对确定的子树进行递归：
   • 在中序遍历中，查找每个子树的子树。
   • 如果子树不是叶子节点，则重复上述步骤，继续划分和重建。

以上面的例子为基础，对这个二叉树进行还原

• 根节点：A（后序遍历的最后一个元素）。

• 左子树：CBD（中序遍历CBDAEF中A左侧部分）。

  • 左子树根：B（后序遍历CDB中，B在最后一个A之前的第一个元素）
    • 左子树：C（B左侧）。
    • 右子树：D（B右侧）。
  • 右子树：EF（中序遍历CBDAEF中A右侧部分）
    • 右子树根：E（后序遍历EF中，E在F之前）
      • 右子树：F（E右侧）。

    A
   / \
  B   E
 / \   \
C   D   F

总结：这两种还原二叉树的方法的精髓都是要先找到当前树的根节点，然后在找到这个节点的子树，然后递归这两个操作构造。

并查集

并查集用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

并查集的重要思想在于，用集合中的一个元素代表集合。我曾看过一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主。接下来我们利用这个比喻，看看并查集是如何运作的。

• 对于只有一个元素的集合，代表元素自然是唯一的那个元素

• 合并1号和3号所在的集合，1号为代表元素

• 合并3号和2号所在的集合，合并代表元素，组合成一个新集合。

重复上述结果就可以构成一个并查集。并查集是一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的根节点（图中橙色的圆）即可。根节点的父节点是它自己。可以直接把它画成一棵树：

初始并查集

初始化，集合中每个元素都为一个集合。假如有编号为1, 2, 3, ..., n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。也就意味着每一个节点都是一个集合。

int fa[MAXN];
inline void init(int n) //将函数的调用替换为函数体的代码
{
    for (int i = 1; i <= n; ++i)
        // 集合中每个元素都为一个集合
        fa[i] = i;
}

查询，访问集合代表元素，用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

int find(int x)
{
    if(fa[x] == x) //fa数组中存储的是集合中元素的父节点
        return x;
    else
        return find(fa[x]);
}

合并，先找到两个集合的代表元素(初始情况下是自己，处理完成之后就是父节点)，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。

inline void merge(int i, int j)
{
    // find是查找j的根节点
    // 通常根节点的序号和数组的index一一对应,这里的fa[find(i)]就是i的根节点的位置
    fa[find(i)] = find(j);
}

路径压缩优化

最简单的并查集效率是比较低的。例如，来看下面这个场景：

现在我们要merge(2,3)，于是从2找到1，fa[1]=3，于是变成了这样：

然后我们又找来一个元素4，并需要执行merge(2,4)：

从2找到1，再找到3，然后fa[3]=4，于是变成了这样：

这样可能会形成一条长长的链，随着链越来越长，我们想要从底部找到根节点会变得越来越难。怎么解决呢？我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样：

其实这说来也很好实现。只要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现：

合并

// 函数的作用是找到根节点 - 只要记住这一点
int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

简化

int find(int x)
{
    // 三元表达式只是简化了if else
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

总的代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 500000 + 7;

int n, m, s;
vector<int> adj[MAX_N]; // 邻接表存储树
int parent[MAX_N]; // 并查集中的父节点
int ancestor[MAX_N]; // 记录每个节点的祖先
int visited[MAX_N]; // 记录节点是否被访问过
int lca_res[MAX_N]; // 保存每次查询的结果
vector<pair<int, int>> queries[MAX_N]; // 保存LCA查询

// 并查集的路径压缩
int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// Tarjan's LCA
void tarjan(int u) {
    ancestor[u] = u;
    visited[u] = 1;
    for (int v : adj[u]) {
        if (!visited[v]) {
            tarjan(v);
            parent[v] = u; // 合并子节点到当前节点
        }
    }
    // 处理LCA查询
    for (auto &[v, index] : queries[u]) {
        if (visited[v]) {
            lca_res[index] = ancestor[find(v)];
        }
    }
}

int main() {
    cin >> n >> m >> s;
    
    // 初始化
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    
    int a, b;
    for (int i = 1; i < n; ++i) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a); // 无向图
    }

    for (int i = 1; i <= m; ++i) {
        cin >> a >> b;
        queries[a].push_back({b, i});
        queries[b].push_back({a, i});
    }

    tarjan(s);

    for (int i = 1; i <= m; ++i) {
        cout << lca_res[i] << endl;
    }

    return 0;
}

倍增法优化

通过引入倍增法（也称为跳跃表或稀疏表），可以减少查询的时间复杂度。具体来说，倍增法在预处理阶段构建一个祖先表，使得每次查询能够在 O(log⁡n) 的时间内完成。

通俗地说，倍增法就是“跳跃式查找”，不再是逐个节点遍历，而是根据层级成倍查找。最初查找间隔为 2^0，然后是2^1，一直到 2^n。这样，通过构建一棵树来维护每个集合，原本需要线性时间O(n)的查找，可以优化到对数时间 O(log⁡n)。

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 500000+7;
const int LOG_N = 20; // log2(MAX_N) 取上界

int n, m, s;
int d[MAX_N]; // 保存节点深度
int f[MAX_N][LOG_N]; // 保存节点的 2^j 级父节点

int head[MAX_N], cnt = -1;
struct Edge {
    int to, next;
} e[MAX_N * 2];

void add(int u, int v) {
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u, int fa) // u为当前节点, fa为父节点
{
    f[u][0] = fa; // 直接父节点
    d[u] = d[fa] + 1;
    for (int j = 1; j < LOG_N; j++) {
        f[u][j] = f[f[u][j-1]][j-1]; // 预处理所有2^j父节点
    }
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if (v != fa) {
            dfs(v, u);
        }
    }
}

int lca(int x, int y) {
    if (d[x] > d[y]) // 令y为更深节点
        swap(x, y);

    // 使x和y的深度相同
    for (int j = LOG_N - 1; j >= 0; j--) {
        if (d[f[y][j]] >= d[x]) {
            y = f[y][j];
        }
    }

    if (x == y) return x;

    // 同时向上移动直到找到最近公共祖先
    for (int j = LOG_N - 1; j >= 0; j--) {
        if (f[x][j] != f[y][j]) {
            x = f[x][j];
            y = f[y][j];
        }
    }

    return f[x][0]; // 返回LCA
}

int main() {
    memset(head, -1, sizeof(head));
    memset(f, 0, sizeof(f)); // 初始化 f 数组
    int a, b;
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a); // 无向图，要加两次
    }
    dfs(s, 0);

    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }

    return 0;
}

树与二叉树的转化

普通树转换为二叉树

我们借助图片来进行了解，首先下图是一颗普通的树，它有三个结点，所以明显不是二叉树

如果将其转换成相应的二叉树分为两个步骤

• 在树中所有的兄弟结点(同层)之间加一连线
• 对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线

所以我们首先执行『在兄弟结点之间添加连线』

然后在去除『非长子外』的连线

最后，我们在稍微调整一下位置，就可以得出我们想要的二叉树

总结一下，基本的步骤如下

• 加线，在所有兄弟结点之间加一条连线
• 去线，对树中每个结点，只保留它与第一孩子结点的连线，删除它与其他孩子结点之间的连线
• 层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明

森林转换为二叉树

同样的还是借助图片来进行了解，首先下图是三颗普通的树，三棵树构造在一起就成了一个森林

如果将其转换成相应的二叉树分为两个步骤

• 先将森林中的每棵树变为二叉树
• 再将各二叉树的根结点视为兄弟从左到右连在一起，就形成了一颗二叉树

所以我们首先将森林中的每棵树变为二叉树，方式和我们之前实现的方式是一致的

然后将它们的『根结点』依次连在一起

最后老规矩，在稍微调整一下位置

总结一下，基本的步骤如下

• 把每棵树转换为二叉树
• 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来

二叉树转换为树、森林

二叉树转换为普通树本质上就是之前的逆过程，步骤也就是反过来做而已，判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是『只要看这棵二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树』，如下，是一个二叉树

第一步，若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子等等等等，依次都与 y 用连连连接起来，如下

第二步，去掉所有双亲到右孩子之间到连线（也就是之前到逆向）

最后老规矩，调整一下，就变成了我们之前的森林

树与森林的遍历

简单来说，树的遍历分为两种方式，一种是先根遍历，另一种是后根遍历

• 先根遍历，先访问树的根结点，然后再依次先根遍历根的每棵子树
• 后根遍历，先依次遍历每棵子树，然后再访问根结点

比如下面这棵树

我们按照两种遍历方式如下

先根遍历结果为 A ==> B ==> E ==> F ==> C ==> G ==> D ==> H ==> I ==> J
后根遍历结果为 E ==> F ==> B ==> G ==> C ==> H ==> I ==> J ==> D ==> A

相对于森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树，这里有一个需要注意的地方，注意比较下面两个图，前面一个是一棵树，而后面那颗则是树转换为二叉树以后的模样

仔细观察我们可以发现

• 树、森林的前根（序）遍历和二叉树的前序遍历结果相同
• 树、森林的后根（序）遍历和二叉树的中序遍历结果相同

这样一来，我们就可以将对树和森林遍历这种复杂问题转换为一种相对比较简单的处理方式

哈夫曼树

在数据膨胀、信息爆炸的今天，数据压缩的意义不言而喻，谈到数据压缩，就不能不提赫夫曼（Huffman）编码，赫夫曼编码是首个实用的压缩编码方案，即使在今天的许多知名压缩算法里，依然可以见到赫夫曼编码的影子

另外，在数据通信中，用二进制给每个字符进行编码时不得不面对的一个问题是如何使电文总长最短且不产生二义性，根据字符出现频率，利用赫夫曼编码可以构造出一种不等长的二进制，使编码后的电文长度最短，且保证不产生二义性

关于赫夫曼编码的内容会在最后进行介绍，在此之前，我们先来了解一下什么是赫夫曼树，先来看下面这个计算成绩的示例

if(a < 60)
  printf("不及格")
else if(a < 70)
  printf("及格")
else if(a < 90)
  printf("良好")
else
  printf("优秀")

如果我们将其转化为二叉树的显示方式，是下面这样的

如果按照上面这个流程，比如某个同学的成绩是 85 分的话，则需要进行三次判断才能得出他的成绩，那么我们是否可以稍微的调整一下，让这个判断流程减少一些呢，那就有了下图这样的二叉树

如果我们把判断流程改为像上图这样，那么可以发现效果有比较明显的改善，即我们只需要两次判断就可以得出我们想要的结果，但是我们如何区分到底应该采用哪种判断流程呢？所以这种情况要按实际情况来进行考虑，如下图

可以发现，一个班级的成绩一般来说，达到良好的人数应该占班级总人数的绝大数，有了这个概念以后，我们就可以先把这两棵二叉树简化成『叶子结点带权』的二叉树（树结点间的连线相关的数叫做权，Weight），就是把我们对应分数的所占比例给带入到二叉树当中，结果如下图

针对于上图，我们需要介绍几个基本的概念，如下

• 结点的路径长度，表示从根结点到该结点的路径上的连接数
• 树的路径长度，表示树中每个叶子结点的路径长度之和
• 结点带权路径长度，表示结点的路径长度与结点权值的乘积
• 树的带权路径长度（WPL，Weighted Path Length），表示的是树中所有叶子结点的带权路径长度之和
• 如果 WPL 的值越小，说明构造出来的二叉树性能越优

有了这些概念以后，我们就可以来分别计算上诉两种情况

针对第一种情况，它的 WPL 是 5 * 1 + 15 * 2 + 70 * 3 + 10 * 3 = 275

针对第二种情况，它的 WPL 是 10 * 1 + 70 * 2 + 15 * 3 + 5 * 3 = 210

可以发现，针对成绩的判断流程，采取后面的一种方式是更为合理的，那么现在问题来了，因为在一棵树的所有构成形状当中，有各种各样的构成方式，那么我们如才能何构造出最优的赫夫曼树呢（也就是所谓的最优二叉树）？看下面流程

假设有一片森林，如上图所示，有四颗小树（只有一个根结点的树），它们的权也分别标注了出来，然后我们挑选出权值最小的两棵树，小的放左边，大的放右边，然后模拟出一个新的结点作为新二叉树的根，这个新的结点连接着它们两个，如下所示，而新的树的权值为它的左右孩子的权值之和

然后同理操作，继续在剩余树林当中挑选出权值最小的那一颗(贪心)，按照我们之前的逻辑继续连接，也就是下面这样

依次执行下去，最后的结果如下

这样就形成了一颗赫夫曼树，也就是所谓的最优二叉树，因为如果用其他的方式使用 ABCD 来进行构造所形成的二叉树的 WPL 是不会小于上图当中所实现的方式的。可以看出，赫夫曼算法使用贪心，将权值最大的往上层排列，权值最小的往下排列。这样就会使得WPL的值最小。

赫夫曼编码

在之前的章节当中，我们已经介绍了赫夫曼树的基本原理和构造方式，而赫夫曼编码可以很有效地压缩数据（通常可以节省 20% ~ 90% 的空间，具体压缩率依赖于数据的特性），下面我们来看几个经常会遇到的名词

• 定长编码，比如像 ASCII 编码就是定长编码，如果我们有一百个字符，并且都是 A 的话，那么则需要八百位才能存放的下
• 变长编码，单个编码的长度不一致，可以根据整体出现频率来调节，比如我们要发生的信息都是 A，那么我们可以使用 0 或者 1 来代表 A（因为这个规则我们已经事先约定好了）
• 前缀码，所谓的前缀码，就是没有任何码字是其他码字的前缀，比如我们的赫夫曼编码（其实就是非前缀码，但是业界之中都叫前缀码）

下面我们来看看如何用代码进行实现，我们首先来定义哈夫曼树节点 HuffmanTreeNode

class HuffmanTreeNode {
public:
    HuffmanTreeNode* l;  // 左子树
    HuffmanTreeNode* r;  // 右子树
    int weight;          // 字符的度量值，表示出现频次
    char ch;             // 字符

    // 构造函数
    HuffmanTreeNode(int weight = 0, char ch = '\0') 
        : l(nullptr), r(nullptr), weight(weight), ch(ch) {}
};

然后我们再来定义一个最小堆 heapMin，主要用于在创建哈夫曼树过程中获取度量值 weight（字符出现的频次）最小的节点

class heapMin {
private:
    std::vector<HuffmanTreeNode*> heap;

    // 调整堆使其满足最小堆性质
    void adjust(int index) {
        int len = heap.size();
        int l = 2 * index + 1;
        int r = 2 * index + 2;
        int min = index;

        if (l < len && heap[min]->weight > heap[l]->weight) {
            min = l;
        }

        if (r < len && heap[min]->weight > heap[r]->weight) {
            min = r;
        }

        if (min != index) {
            std::swap(heap[index], heap[min]);
            adjust(min);
        }
    }

public:
    // 插入一个节点
    void push(HuffmanTreeNode* node) {
        heap.push_back(node);
        for (int i = heap.size() / 2 - 1; i >= 0; i--) {
            adjust(i);
        }
    }

    // 移除最小元素
    HuffmanTreeNode* pop() {
        if (heap.empty()) return nullptr;

        HuffmanTreeNode* node = heap.front();
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            adjust(0);
        }

        return node;
    }

    // 获取堆的大小
    int size() const {
        return heap.size();
    }

    // 判断堆是否为空
    bool empty() const {
        return heap.empty();
    }
};

再来定义哈夫曼编码对象 HuffmanCode

class HuffmanCode {
public:
    std::vector<std::string> codeTable;  // 编码表
    HuffmanTreeNode* huffmanTree;        // 哈夫曼树

    // 构造函数
    HuffmanCode() : huffmanTree(nullptr) {}

    // 析构函数，用于释放哈夫曼树的内存
    ~HuffmanCode() {
        clearHuffmanTree(huffmanTree);
    }

    // 清空哈夫曼树的内存
    void clearHuffmanTree(HuffmanTreeNode* node) {
        if (node != nullptr) {
            clearHuffmanTree(node->l);
            clearHuffmanTree(node->r);
            delete node;
        }
    }

    // 打印当前的编码表
    void printCodeTable() {
        for (size_t i = 0; i < codeTable.size(); ++i) {
            std::cout << "Char: " << char('a' + i) << ", Code: " << codeTable[i] << std::endl;
        }
    }

    // 示例：插入编码表中的字符编码
    void insertCode(const std::string& code) {
        codeTable.push_back(code);
    }
};

生成字符频次最小堆

class HuffmanCode {
public:
    // 静态方法：根据给定字符串生成字符频次最小堆
    static HeapMin calcHeap(const std::string& str) {
        HeapMin heap;  // 定义一个最小堆
        std::unordered_map<char, int> freqMap;  // 定义一个哈希表来存储字符及其频次

        // 统计字符频次
        for (char ch : str) {
            freqMap[ch]++;  // 对每个字符，增加其在哈希表中的频次
        }

        // 将频次插入最小堆
        for (const auto& entry : freqMap) {
            // 创建哈夫曼树节点，参数是字符的频次和字符本身
            HuffmanTreeNode* node = new HuffmanTreeNode(entry.second, entry.first);
            heap.push(node);  // 将节点插入最小堆
        }

        return heap;  // 返回构建好的最小堆
    }
};

创建哈夫曼树

// 之前定义的 HuffmanTreeNode 和 HeapMin 保持不变

class HuffmanCode {
public:
    HuffmanTreeNode* huffmanTree;

    HuffmanCode() : huffmanTree(nullptr) {}

    // 根据输入字符串创建哈夫曼树
    HuffmanTreeNode* createHuffmanTree(const std::string& str) {
        // 生成字符频次的最小堆
        HeapMin heap = calcHeap(str);

        // 当堆中剩余一个元素时停止合并
        while (heap.size() > 1) {
            // 取出最小的两个节点
            HuffmanTreeNode* min1 = heap.pop();
            HuffmanTreeNode* min2 = heap.pop();

            // 创建一个新节点作为这两个节点的父节点
            HuffmanTreeNode* parent = new HuffmanTreeNode(min1->weight + min2->weight, '\0');

            // 将两个节点合并到父节点
            if (min1->weight < min2->weight) {
                parent->l = min1;
                parent->r = min2;
            } else {
                parent->l = min2;
                parent->r = min1;
            }

            // 将新的父节点插入堆中
            heap.push(parent);
        }

        // 剩下的唯一一个节点就是哈夫曼树的根节点
        huffmanTree = heap.pop();
        return huffmanTree;
    }

    // 计算字符频次并返回最小堆（之前已经实现）
    static HeapMin calcHeap(const std::string& str) {
        HeapMin heap;
        std::unordered_map<char, int> freqMap;

        // 统计字符频次
        for (char ch : str) {
            freqMap[ch]++;
        }

        // 将频次插入最小堆
        for (const auto& entry : freqMap) {
            HuffmanTreeNode* node = new HuffmanTreeNode(entry.second, entry.first);
            heap.push(node);
        }

        return heap;
    }
};

递归哈夫曼树，生成编码表

// HuffmanTreeNode 保持不变，假设之前已经定义
// 递归遍历哈夫曼树，生成编码表
class HuffmanCode {
public:
    std::unordered_map<char, std::string> codeTable;  // 编码表

    // 递归生成哈夫曼编码表
    void traverseTree(HuffmanTreeNode* node, const std::string& code) {
        if (node == nullptr) {
            return;
        }

        // 如果当前节点是叶子节点（即没有子节点）
        if (node->l == nullptr && node->r == nullptr) {
            codeTable[node->char] = code;  // 将叶子节点的字符与其编码存入编码表
        }

        // 递归遍历左子树并添加 '0' 到编码
        if (node->l != nullptr) {
            traverseTree(node->l, code + "0");
        }

        // 递归遍历右子树并添加 '1' 到编码
        if (node->r != nullptr) {
            traverseTree(node->r, code + "1");
        }
    }

    // 输出编码表
    void printCodeTable() const {
        for (const auto& entry : codeTable) {
            std::cout << entry.first << ": " << entry.second << std::endl;
        }
    }
};

哈夫曼编码

// 假设 HuffmanTreeNode 和 HuffmanCode 已经定义，并且 traverseTree 方法已经实现

class HuffmanCode {
public:
    std::unordered_map<char, std::string> codeTable;  // 编码表
    HuffmanTreeNode* huffmanTree;

    HuffmanCode() : huffmanTree(nullptr) {}

    // 创建哈夫曼树
    HuffmanTreeNode* createHuffmanTree(const std::string& str) {
        // ... (这里的实现与之前的 createHuffmanTree 方法相同)
    }

    // 递归生成哈夫曼编码表
    void traverseTree(HuffmanTreeNode* node, const std::string& code) {
        // ... (这里的实现与之前的 traverseTree 方法相同)
    }

    // 哈夫曼编码
    std::string encode(const std::string& str) {
        // 创建哈夫曼树
        createHuffmanTree(str);

        // 生成编码表
        codeTable.clear(); // 清空编码表
        traverseTree(huffmanTree, "");

        std::string res;
        // 遍历字符串，将每个字符替换为其哈夫曼编码
        for (char ch : str) {
            res += codeTable[ch]; // 将对应的编码添加到结果字符串中
        }

        return res; // 返回编码后的结果
    }

    // 打印编码表
    void printCodeTable() const {
        for (const auto& entry : codeTable) {
            std::cout << entry.first << ": " << entry.second << std::endl;
        }
    }
};

哈夫曼解码

class HuffmanCode {
public:
    std::unordered_map<char, std::string> codeTable;  // 编码表
    HuffmanTreeNode* huffmanTree;

    HuffmanCode() : huffmanTree(nullptr) {}

    // 创建哈夫曼树
    HuffmanTreeNode* createHuffmanTree(const std::string& str) {
        // ... (与之前相同的实现)
    }

    // 递归生成哈夫曼编码表
    void traverseTree(HuffmanTreeNode* node, const std::string& code) {
        // ... (与之前相同的实现)
    }

    // 哈夫曼编码
    std::string encode(const std::string& str) {
        // ... (与之前相同的实现)
    }

    // 哈夫曼解码
    std::string decode(const std::string& str) {
        if (huffmanTree == nullptr) {
            std::cerr << "Please create HuffmanTree!" << std::endl;
            return "";
        }

        HuffmanTreeNode* node = huffmanTree;
        std::string res;

        // 遍历编码字符串
        for (char ch : str) {
            // 根据编码字符选择左右子树
            if (ch == '0') {
                node = node->l;
            } else {
                node = node->r;
            }

            // 到达叶子节点，表示找到了一个字符
            if (node->l == nullptr && node->r == nullptr) {
                res += node->char;  // 添加字符到结果字符串
                node = huffmanTree;  // 重置到树的根节点
            }
        }

        return res; // 返回解码后的结果
    }

    // 打印编码表
    void printCodeTable() const {
        for (const auto& entry : codeTable) {
            std::cout << entry.first << ": " << entry.second << std::endl;
        }
    }
};

完整的代码

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <queue>

// 哈夫曼树节点
class HuffmanTreeNode {
public:
    char ch;                        // 字符
    int weight;                     // 字符的频次
    HuffmanTreeNode* l;            // 左子树
    HuffmanTreeNode* r;            // 右子树

    // 构造函数
    HuffmanTreeNode(char character, int freq) : ch(character), weight(freq), l(nullptr), r(nullptr) {}

    // 自定义比较运算符，用于优先队列
    bool operator>(const HuffmanTreeNode& other) const {
        return weight > other.weight;
    }
};

// 哈夫曼编码类
class HuffmanCode {
public:
    std::unordered_map<char, std::string> codeTable;  // 编码表
    HuffmanTreeNode* huffmanTree;

    HuffmanCode() : huffmanTree(nullptr) {}

    // 创建哈夫曼树
    void createHuffmanTree(const std::string& str) {
        // 统计字符频次
        std::unordered_map<char, int> frequency;
        for (char ch : str) {
            frequency[ch]++;
        }

        // 使用优先队列构建最小堆
        std::priority_queue<HuffmanTreeNode*, std::vector<HuffmanTreeNode*>, std::greater<HuffmanTreeNode*>> minHeap;

        // 将每个字符和频次放入堆中
        for (const auto& pair : frequency) {
            minHeap.push(new HuffmanTreeNode(pair.first, pair.second));
        }

        // 构建哈夫曼树
        while (minHeap.size() > 1) {
            HuffmanTreeNode* min1 = minHeap.top(); minHeap.pop();
            HuffmanTreeNode* min2 = minHeap.top(); minHeap.pop();

            // 创建新父节点
            HuffmanTreeNode* parent = new HuffmanTreeNode('\0', min1->weight + min2->weight);
            parent->l = min1;
            parent->r = min2;

            minHeap.push(parent);
        }

        // 取得最终的哈夫曼树根节点
        if (!minHeap.empty()) {
            huffmanTree = minHeap.top();
        }
    }

    // 递归生成哈夫曼编码表 - 编码表是由给出的字符出现的频率构造的
    void traverseTree(HuffmanTreeNode* node, const std::string& code) {
        if (node->l == nullptr && node->r == nullptr) {
            codeTable[node->ch] = code; // 到达叶子节点，存储编码
            return;
        }
        if (node->l != nullptr) traverseTree(node->l, code + "0"); // 左子树
        if (node->r != nullptr) traverseTree(node->r, code + "1"); // 右子树
    }

    // 哈夫曼编码
    std::string encode(const std::string& str) {
        createHuffmanTree(str); // 创建哈夫曼树
        traverseTree(huffmanTree, ""); // 生成编码表

        std::string res;
        for (char ch : str) {
            res += codeTable[ch]; // 替换为哈夫曼编码
        }
        return res; // 返回编码结果
    }

    // 哈夫曼解码
    std::string decode(const std::string& str) {
        if (huffmanTree == nullptr) {
            std::cerr << "Please create HuffmanTree!" << std::endl;
            return "";
        }

        HuffmanTreeNode* node = huffmanTree;
        std::string res;

        // 遍历编码字符串
        for (char ch : str) {
            node = (ch == '0') ? node->l : node->r; // 根据编码选择子树
            // 到达叶子节点
            if (node->l == nullptr && node->r == nullptr) {
                res += node->ch; // 添加字符到结果字符串
                node = huffmanTree; // 重置到树的根节点
            }
        }

        return res; // 返回解码后的结果
    }

    // 打印编码表
    void printCodeTable() const {
        for (const auto& entry : codeTable) {
            std::cout << entry.first << ": " << entry.second << std::endl;
        }
    }
};

// 示例使用
int main() {
    HuffmanCode hc;
    std::string input = "example string for huffman encoding";

    // 哈夫曼编码
    std::string encoded = hc.encode(input);
    std::cout << "Encoded string: " << encoded << std::endl;

    // 哈夫曼解码
    std::string decoded = hc.decode(encoded);
    std::cout << "Decoded string: " << decoded << std::endl;

    // 输出编码表
    hc.printCodeTable();

    return 0;
}

二叉搜索树BST

二叉搜索树中，左子树的所有节点值小于父节点，右子树的所有节点值大于父节点。

• 若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；
• 若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；
• 它的左、右⼦树也分别为⼆叉搜索树

二叉搜索树的中序遍历是正序输出，例如下面的树输出的是3 7 9 14 16 18 19

二叉搜索树的主要优势在于其查找效率。如果树是相对平衡的，即它的深度是对数级别的，那么查找、插入和删除的时间复杂度也都为 O(log n)，其中 n 是树中的节点数。

具体来说，这是因为在查找过程中，我们每次都能够根据节点关键字的大小来排除掉一半的搜索空间。这种二分的思想使得二叉搜索树在处理大规模数据时仍能保持较高的效率。

平衡二叉搜索树AVL

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如下图。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。

在此二叉搜索树中查找元素 6 需要查找6次。二叉搜索树的查找效率取决于树的高度，因此需要保持树的高度最小，即可保证树的查找效率。同样的序列A，将其改为下图的方式存储，查找元素6时只需比较3次，查找效率提升一倍。

可以看出当结点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。它具有如下几个性质：

1. 可以是空树。
2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

平衡之意，如天平，即两边的分量大约相同。例如下面的图就不是平衡二叉树

下面的也不是平衡二叉树，因为虽然任何一个结点的左子树与右子树都是平衡二叉树，但高度之差已经超过 1 。

平衡因子

平衡因子的作用是衡量二叉树中各个节点的平衡程度，也就是左子树和右子树高度的差值，对于当前节点的关系应该有

$$平衡因子 = 左子树的高度 - 右子树的高度$$

平衡二叉树中不存在平衡因子大于1的节点。在一棵平衡二叉树中，节点的平衡因子只能取0 、1或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。这里子树高度是从根节点到当前节点的距离。

节点结构

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡

    Tree parent; //该结点的父节点

    ElementType val; //结点值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {
        parent = NULL;
        depth = 0;
        lchild = rchild = NULL;
        this->val=val;
    }
};

失衡与调整

在一个平衡二叉树中从底部插入一个节点，原来的平衡二叉树就变成了一个不平衡的二叉树了，这种结果被称之为失衡。我们可以通过对节点的自旋来将不平衡二叉树转化为平衡二叉树。

例如在此平衡二叉树插入节点 99 ，树的结构就变了。由于插入一个节点会更新平衡因子，也就导致了根节点的平衡因子大于2了，就导致了这个树的平衡性被破坏了。

• 节点 66 的左子树高度为 1，右子树高度为 3，此时平衡因子为 2，树失去平衡。

• 以节点 66 为父节点的那颗树就称为 最小失衡子树。

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。旋转的目的就是减少高度，通过降低整棵树的高度来平衡，从而提高查找效率。哪边的树高，就把那边的树向上旋转，也就是左边的树高，往右边旋。右边的树高，往左边旋转。

左旋

为了保证树的平衡性，当节点 66 的平衡因子为 2 时，说明右子树高度比左子树高，需要对节点 66 进行左旋操作。

1. 节点 66 的右子节点替代 66 的位置，成为新的根节点。
2. 该右子节点的左子树变为 66 的右子树。
3. 节点 66 本身成为新的根节点的左子树。

也就可以简单记为，左旋是将根节点作为新根节点的左子树。需要左旋的树说明其右子树的深度大于左子树的深度

右旋

平衡二叉树搜索需要右旋，说明左子树的高度大于右子树，需要对这个66节点进行右旋操作

1. 结点66的左子节点代替66的位置，成为新的根节点
2. 该左子节点的右子树变为66的右子树
3. 结点66本身成为新的根节点的右子树

也就可以简单记为，右旋是将老根节点作为新根节点的右子树。需要右旋的树说明其左子树的深度大于右子树的深度

为什么需要这样旋转，这样旋转会不会破坏二叉树的平衡性，答案是不会。前面提到过，平衡二叉树每个节点都由有这两个特点。

• 平衡因子不会大于2
• 左子树大于右子树

这里还是以右旋举例，当左子树高度大于右子树，且高度差超过 1 时，会对该节点进行右旋，以减少左子树的高度并恢复平衡。右旋的作用是将根节点向下调整，新根节点成为原左子树的根节点。这时满足以下几点

1. 根节点必然比新根节点的左节点大：因为新根节点原本是根节点的左子节点，而根据二叉搜索树的定义，左子节点必然比根节点小。因此，右旋操作不会破坏节点的大小关系。
2. 旧根节点的直接右节点比新根节点的右子树要大：右旋过程中，旧根节点下移为新根节点的右子树，而新根节点的右子树（如果存在）本身已经是比新根节点小的节点。所以，旧根节点依然比新根节点的右子树中的节点大。

自平衡多路搜索树

红黑树

红黑树是一种特化的AVL树（平衡二叉树）红黑树也是一种自平衡二叉查找树，它与AVL树类似，都在添加和删除的时候通过旋转操作保持二叉树的平衡，以求更高效的查询性能。

与AVL树相比，红黑树牺牲了部分平衡性，以换取插入/删除操作时较少的旋转操作，整体来说性能要优于AVL树。虽然RBTree是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的：

它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目.

红黑树是实际应用中最常用的平衡二叉查找树，它不严格的具有平衡属性，但平均的使用性能非常良好。在红黑树中，节点被标记为红色和黑色两种颜色。构成红黑树的原则有以下几点：

• 特性1：节点非黑即红
• 特性2：根节点一定是黑色
• 特性3：叶子节点（NIL）一定是黑色
• 特性4：每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 特性5：从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。

红色属性 说明，红色节点的孩子，一定是黑色。 但是，RBTree 黑色节点的孩子，可以是红色，也可以是黑色，具体如下图。

叶子属性 说明， 叶子节点可以是空ull ，AVL的叶子节点不是空的，具体如下图。

基于上面的原则，我们一般在插入红黑树节点的时候，会将这个节点设置为红色，原因参照最后一条原则： 红色破坏原则的可能性最小，如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1，破坏了平衡。

RBT有点属于一种空间换时间类型的优化，在avl的节点上，增加了 颜色属性的 数据，相当于 增加了空间的消耗。 通过颜色属性的增加， 换取，后面平衡操作的次数 减少。

红黑树并不是一颗AVL平衡二叉搜索树，从图上可以看到，根节点P的左子树显然比右子树高根据 红黑树的特性5，从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点， 说明：

rbt 的 左子树和右子树的黑节点的层数是相等的。红黑树的平衡条件，不是以整体的高度来约束的，而是以黑色节点的高度，来约束的。所以称红黑树这种平衡为黑色完美平衡。

看看黑色完美平衡的效果，去掉 rbt中的红色节点，会得到 一个四叉树，从根节点到每一个叶子，高度相同，就是rbt的root到叶子的黑色路径长度。

红黑树的恢复平衡过程的三个操作

一旦红黑树5个原则有不满足的情况，我们视为平衡被打破，如何恢复平衡。靠它的三种操作：变色、左旋、右旋。

• 变色：节点的颜色由红变黑或由黑变红。

• 左旋：以某个结点作为支点(pivot)，其父节点（子树的root）旋转为自己的左子树（左旋），pivot的原左子树变成 原root节点的 右子树，pivot的原右子树保持不变。

• 右旋：以某个结点作为支点(pivot)，其父节点（子树的root）旋转为自己的右子树（右旋），pivot的原右子树变成 原root节点的 左子树，pivot的原左子树保持不变。

红黑树的左旋、右旋操作，AVL树的左旋，右旋操作 差不多。可以往上翻找AVL的构造

红黑树的节点结构

默认新插入的节点为红色：因为父节点为黑色的概率较大，插入新节点为红色，可以避免颜色冲突

// 基础节点模板
template<typename K, typename V>
struct Node {
    int hash;
    K key;
    V val;
    Node* next;

    Node(int hash, K key, V val, Node* next = nullptr)
        : hash(hash), key(key), val(val), next(next) {}
};

// 红黑树节点模板
template<typename K, typename V>
struct TreeNode : public Node<K, V> {
    TreeNode* parent;  // 红黑树的父节点
    TreeNode* left;    // 左子节点
    TreeNode* right;   // 右子节点
    TreeNode* prev;    // 在删除时需要用到，指向前一个节点
    bool red;          // 红黑树标志，true表示红色，false表示黑色

    TreeNode(int hash, K key, V val, Node<K, V>* next = nullptr, TreeNode* parent = nullptr)
        : Node<K, V>(hash, key, val, next), parent(parent), left(nullptr), right(nullptr), prev(nullptr), red(true) {}
};

自平衡构造，下面列举了破坏平衡的事件。

• 红黑树为空树

直接把插入结点作为根节点就可以了，根据红黑树性质2：根节点是黑色的。还需要把插入节点设置为黑色。

• 插入节点的Key已经存在

更新当前节点的值，为插入节点的值。

• 插入节点的父节点为黑色

由于插入的节点是红色的，当插入节点的父节点是黑色时，不会影响红黑树的平衡。直接插入无需做自平衡。

• 插入节点的父节点为红色

根据性质2：根节点是黑色。如果插入节点的父节点为红色节点，那么该父节点不可能为根节点，所以插入节点总是存在祖父节点(三代关系)。

根据性质4：每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连。此时会出现两种状态：

1. 父亲和叔叔为红色
2. 父亲为红色，叔叔为黑色

• 父亲和叔叔为红色节点

根据性质4：红色节点不能相连 ==》祖父节点肯定为黑色节点：父亲为红色，那么此时该插入子树的红黑树层数的情况是：黑红红。因为不可能同时存在两个相连的红色节点，需要进行 变色， 显然处理方式是把其改为：红黑红。

变色 处理：黑红红 ==> 红黑红

1. 将F和V节点改为黑色
2. 将P改为红色
3. 将P设置为当前节点，进行后续处理

可以看到，将P设置为红色了，如果P的父节点是黑色，那么无需做处理；但如果P的父节点是红色，则违反红黑树性质了，所以需要将P设置为当前节点，继续插入操作, 作自平衡处理，直到整体平衡为止。

• 叔叔为黑色，父亲为红色，并且插在父亲的左节点

分为两种情况。LL 红色插入，叔叔为黑色，或者不存在（NIL）也是黑节点，并且节点的父亲节点是祖父节点的左子节点。

注意：单纯从插入来看，叔叔节点非红即黑(NIL节点)，否则破坏了红黑树性质5，此时路径会比其他路径多一个黑色节点。

• LL型失衡

新插入节点，为其父节点的左子节点(LL红色情况)， 插入后 就是LL型失衡

自平衡处理

1. 变颜色：将F设置为黑色，将P设置为红色
2. 对F节点进行右旋

LR型失衡

细分场景 2： 新插入节点，为其父节点的右子节点(LR红色情况)， 插入后 就是LR 型失衡

自平衡处理：

1. 对F进行左旋
2. 将F设置为当前节点，得到LL红色情况
3. 按照LL红色情况处理(1.变色 2.右旋P节点)

• 叔叔为黑节点，父亲为红色，并且父亲节点是祖父节点的右子节点

• RR型失衡

新插入节点，为其父节点的右子节点(RR红色情况)

自平衡处理：

1. 变色：将F设置为黑色，将P设置为红色
2. 对P节点进行左旋

• RL型失衡

新插入节点，为其父节点的左子节点(RL红色情况)

自平衡处理

1. 对F进行右旋
2. 将F设置为当前节点，得到RR红色情况
3. 按照RR红色情况处理(1.变色 2.左旋 P节点)

#include <iostream>

// 定义红黑树节点的颜色
enum Color { RED, BLACK };

// 红黑树节点结构
template<typename K, typename V>
struct TreeNode {
    K key;
    V value;
    Color color;
    TreeNode *left, *right, *parent;

    TreeNode(K key, V value) 
        : key(key), value(value), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

// 红黑树类
template<typename K, typename V>
class RedBlackTree {
private:
    TreeNode<K, V>* root;

    // 左旋操作
    void rotateLeft(TreeNode<K, V>*& root, TreeNode<K, V>*& node) {
        TreeNode<K, V>* rightChild = node->right;
        node->right = rightChild->left;

        if (rightChild->left != nullptr) {
            rightChild->left->parent = node;
        }

        rightChild->parent = node->parent;

        if (node->parent == nullptr) {
            root = rightChild;
        } else if (node == node->parent->left) {
            node->parent->left = rightChild;
        } else {
            node->parent->right = rightChild;
        }

        rightChild->left = node;
        node->parent = rightChild;
    }

    // 右旋操作
    void rotateRight(TreeNode<K, V>*& root, TreeNode<K, V>*& node) {
        TreeNode<K, V>* leftChild = node->left;
        node->left = leftChild->right;

        if (leftChild->right != nullptr) {
            leftChild->right->parent = node;
        }

        leftChild->parent = node->parent;

        if (node->parent == nullptr) {
            root = leftChild;
        } else if (node == node->parent->left) {
            node->parent->left = leftChild;
        } else {
            node->parent->right = leftChild;
        }

        leftChild->right = node;
        node->parent = leftChild;
    }

    // 修复红黑树的性质 - 自平衡功能
    void fixViolation(TreeNode<K, V>*& root, TreeNode<K, V>*& node) {
        TreeNode<K, V>* parent = nullptr;
        TreeNode<K, V>* grandparent = nullptr;

        while ((node != root) && (node->color != BLACK) && (node->parent->color == RED)) {
            parent = node->parent;
            grandparent = parent->parent;

            // 父节点是祖父节点的左子节点
            if (parent == grandparent->left) {
                TreeNode<K, V>* uncle = grandparent->right;

                // 情况1: 叔叔节点是红色
                if (uncle != nullptr && uncle->color == RED) {
                    grandparent->color = RED;
                    parent->color = BLACK;
                    uncle->color = BLACK;
                    node = grandparent;
                } else {
                    // 情况2: 当前节点是父节点的右子节点
                    if (node == parent->right) {
                        rotateLeft(root, parent);
                        node = parent;
                        parent = node->parent;
                    }

                    // 情况3: 当前节点是父节点的左子节点
                    rotateRight(root, grandparent);
                    std::swap(parent->color, grandparent->color);
                    node = parent;
                }
            }
            // 父节点是祖父节点的右子节点
            else {
                TreeNode<K, V>* uncle = grandparent->left;

                // 情况1: 叔叔节点是红色
                if (uncle != nullptr && uncle->color == RED) {
                    grandparent->color = RED;
                    parent->color = BLACK;
                    uncle->color = BLACK;
                    node = grandparent;
                } else {
                    // 情况2: 当前节点是父节点的左子节点
                    if (node == parent->left) {
                        rotateRight(root, parent);
                        node = parent;
                        parent = node->parent;
                    }

                    // 情况3: 当前节点是父节点的右子节点
                    rotateLeft(root, grandparent);
                    std::swap(parent->color, grandparent->color);
                    node = parent;
                }
            }
        }

        root->color = BLACK;
    }

    // 插入一个节点到红黑树中
    TreeNode<K, V>* insertBST(TreeNode<K, V>* root, TreeNode<K, V>* node) {
        if (root == nullptr)
            return node;

        if (node->key < root->key) {
            root->left = insertBST(root->left, node);
            root->left->parent = root;
        } else if (node->key > root->key) {
            root->right = insertBST(root->right, node);
            root->right->parent = root;
        }

        return root;
    }

    // 中序遍历
    void inorderHelper(TreeNode<K, V>* root) {
        if (root == nullptr)
            return;

        inorderHelper(root->left);
        std::cout << root->key << " ";
        inorderHelper(root->right);
    }

public:
    RedBlackTree() : root(nullptr) {}

    // 插入函数
    void insert(const K& key, const V& value) {
        TreeNode<K, V>* node = new TreeNode<K, V>(key, value);

        root = insertBST(root, node);

        fixViolation(root, node);
    }

    // 中序遍历
    void inorder() {
        inorderHelper(root);
    }
};

int main() {
    RedBlackTree<int, std::string> tree;

    tree.insert(10, "A");
    tree.insert(20, "B");
    tree.insert(30, "C");
    tree.insert(15, "D");
    tree.insert(25, "E");
    tree.insert(5, "F");

    std::cout << "Inorder Traversal of Created Tree:\n";
    tree.inorder();

    return 0;
}

多叉树

二叉树的操作效率较高，但是也存在问题，如下图所示

当二叉树的节点较少时，不会出现什么问题。但是当节点过多时（海量，如 1 亿），就会出现如下的问题：

1. 构建二叉树时，需要进行多次 I/O 操作。节点较多时，一般会存储在文件或则数据库中，进行多次 I/O 获取到所有的节点，速度有影响
2. 会造成二叉树的高度很大，降低操作速度

为了解决层数过多的问题，就出现了 多叉树。在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是 多叉树（multiway tree）。

多叉树也有一定的规则的，比如后面讲解的 2-3 树、2-3-4 树，就是多叉树。多叉树通过重新组织节点，减少树的高度，对二叉树进行优化。下图则是一颗 2-3 的多叉树：

在2-3 树中，节点的子节点数量可能为 2 个或 3 个。具有 2 个子节点的节点只包含 1 个键，而具有 3 个子节点的节点则包含 2 个键。通过动态调整节点的大小和重新组织节点，B 树能够减少树的高度，从而降低 I/O 操作次数，提升访问大规模数据时的效率。

• 一个圆圈表示一个数据项
• 相连的数据项，整个表示一个节点

那么它的优点是什么

• 降低树的高度：可以看到，一个节点中有很多数据项，就能大大减少节点数量，从而降低树的高度

• 减少 I/O 读写次数

  文件系统及数据库系统的设计者利用了 磁盘预读原理，将一个节点的大小设为等于一个页（通常大小为 4K），这样每个节点只需要一次 I/O 就可以完全载入。

  这样说，你可能没有概念，举个例子：将树的度 M 设置为 1024 ，在 600 亿个元素中最多只需要 4 次 I/O 操作就可以读取到想要的元素。B 树（B+ ）广泛应用于文件存储系统以及数据库系统中。

什么是 度

• 节点的度：一个节点下的子树节点个数就是 节点的度。
• 树的度：指一颗树中，节点的度最大的那一个值。

B 树其实就是前面所说的 多叉树

B树

2-3树是最简单的 B 树结构，具有如下特点：

1. 所有 叶子节点 都在同一层只要是 B 树都满足这个条件，就是满树。
2. 有两个子节点的节点叫 二节点，二节点要么 没有子节点，要么 必须有两个子节点。
3. 有三个子节点的节点叫 三节点，三节点要么 没有子节点，要么 必须有三个子节点。

4. 2-3 树是由 二节点 和 三节点 构成的树

   2-3 树构建图解

对数列 {16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成一个 2-3 树，那么它构建的规则要满足前面说的特点。下面进行图解后，你就明白，上面的特点是如何限制的。

有几个额外的注意事项：

1. 一个节点中，最多只允许放 2 个数据。
2. 构建的树必须是有序的，也就是按照二叉排序（BST）的要求构建有序的树

下面是图解步骤：

• 添加 16、24

添加 16时，没有数据，直接新建一个节点，放进去。添加 24时，发现有一个节点了，并且比16大，此时该节点中只有一个数据，则将 24放在 16的右边。

• 添加 12

此时会发现，12 比 16小，本来应该放在 16 的左边，此时发现这个节点 已经有两个数据了，那么就只能放在 左子节点 。

如果直接将 12放到 16,24 的左节点，就会破坏 2-3 树的条件：一个节点，要么没有子节点，要么有两个。那么此时就只能将 16,24 这个节点进行拆分。如上图：24变成 16的右节点，12 变成 16 的左节点。这时就满足了 2-3 的特性。

• 添加 32

这个就简单了，以现在的树结构，可以直接添加到 24 的 右边，变成 24,32

• 添加 14

这个也简单，直接添加到12的右边，变成 12,14

• 添加 26

此时应该添加到 24,32 的中间(26介于24 - 32)，但一个节点只能添加两个数据，那么就需要拆分。

为了满足 B 树特点，发现上层的 16 只有一个数，那么就补足它。组成 16,26。因为此时 24,32 这个节点，不满足 BST 的排序了，24 是小于 26 的。只有 32 满足。

拆完上层，再拆本层：由于 24 介于 16,26 之间，则将它安排在 3 节点中的中间节点，24,32 把24 拆分出去了，只剩下 32，此时完全满足 B 树的特点。

• 添加 34

此时就简单了，添加到 32,34 中

• 添加 10

此时应该添加到 12,14 的左侧。但是不满足条件：一个节点最多只能装 2 个数据。放到 12,14 的左节点，也不满足条件：所有叶子节点必须在同一层、也不满足2-3 节点的数量要求。

那么此时就需要拆分，先拆上层再拆下层。先看他的上层 16,26 是满的，看下图：

左侧的拆分图，上面我们分析过了，不满足 B 树要求。那么就需要拆分成右图这样：

1. 将 12,14 中的14拆分成右子节点，10 挂在 左节点。
2. 此时不满足 B 树要求的，则将 16,26 中的 26 拆分成 右子节点。因为右侧高度不够，将两个键的节点拆除。增高，达到叶节点同层。
3. 24 这个节点由于上层被拆分了，不满足在中间节点了。调整它的位置
4. 原来的 32,34 节点调整为 16 的右节点。

• 添加 8

此时很简单，组成 8,10 即可

• 添加 28

这里笔者有点小小的疑问，此时 28 不是应该加在 26,28 吗？难道说这里还有一个规则：

1. 只有一个数据的节点，下面只允许 最多有 2 个节点，要么没有
2. 有 2 个数据的节点，下面只允许 最多有 3 个节点，要么没有

• 添加 38

此时就简单，直接组成 34,38

• 添加 20

这个也简单，直接组成 20,24

2-3 树添加规则总结

1. 所有 叶子节点 都在同一层：只要是 B 树都满足这个条件，就是满树。
2. 有两个子节点的节点叫 二节点：二节点要么 没有子节点，要么 必须有两个子节点。
3. 有三个子节点的节点叫 三节点：三节点要么 没有子节点，要么 必须有三个子节点。
4. 2-3 树是由 二节点 和 三节点 构成的树
5. 构建的树，要满足二叉排序树（BST） 的顺序
6. 一个节点中，最多只允许放 2 个数据。
7. 只有一个数据的节点，下面只允许 最多有 2 个节点，要么没有
8. 有 2 个数据的节点，下面只允许 最多有 3 个节点，要么没有

---

234 树

除了 2-3 树，还有 2-3-4 树，他的特点是在 2-3 树的基础上，还多了一个 4 节点，同样，一个节点最多可以装 3 个数据，要么有 4 个节点，要么没有

B - 树

B-tree 树即 B 树，B 是 Balanced 平衡的意思。

TIP

B- 树，这个也是 B 树，只是翻译的文本容易产生误解。

上图就是一个 B 树，说明如下：

• B 树的阶：节点的最多 子节点 个数：2-3 树的阶是 3，2-3-4 树的阶是 4
• B 树的搜索：从 根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的 儿子节点。然后重复，直到所对应的儿子节点指针为空，或则已经是叶子节点。
• 关键字集合分布在整棵树中：叶子节点和非叶子节点都存放数据
• 搜索有可能在非叶子节点结束
• 其搜索性能等价于在关键字全集内做一次二分查找

B+树

在 MySQL 中，有些索引就是用 B 树或则 B+ 树实现的。B+ 树是 B 树的变体，也是一种多路搜索树。

B+树说明：

1. B+ 树的搜索与 B 树基本相同，区别是 B+ 树只有到达叶子节点才命中（B 树可以在非叶子节点命中），其性能也等价于在关键字全集做一次二分查找

2. 所有 关键字都出现在叶子节点的链表中

   即：数据只能在叶子节点，也叫 稠密索引，且链表中的关键字（数据）恰好是有序的。

3. 不可能在非叶子节点命中

4. 非叶子节点相当于是叶子节点的索引，也叫 稀疏索引，叶子节点相当于是存储（关键字）数据的数据层

5. 更适合文件索引系统

6. B 树和 B+ 树有各自的应用场景，不能说 B+ 树完全比 B 树好。

B+ 树的这种设计，应该是类似分段思想，比如：5,28,65，下面存放三个节点：

• 5-28 的段，为一个节点
• 28-65 的段，为一个节点
• 65 以上的段，为一个节点

比如查询 30 ，直接找到在第二个节点中，然后往下一个目录索引找，就很快能定位到数据。

B*树

B* 树是 B+ 树的一种变体。与 B+ 树不同，B* 树在非根和非叶子节点之间增加了指向兄弟节点的指针，并且在节点即将分裂时优先与兄弟节点共享空间，进一步推迟分裂的发生，从而提高了查找效率和减少树的分裂频率。

• B* 树定义了 非叶子节点 关键字个数至少为 (2/3)*M ，即块的最低使用率为 2/3，而 B+ 树的块的最低使用率为 B+ 树的 1/2。M 是指树的度，也就是层。
• 从第 1 个特点，可以看出 B* 树分配新节点的概率比 B+ 树要低，空间使用率更高。

线索树

遍历二叉树以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树结点的各种遍历序列，其实质是对一个非线性结构进行线性化操作，使这个访问序列中的每个结点（第一个和最后一个除外）都有一个直接前驱和直接后继。引入线索二叉树是为了加快查找结点前驱和后继的速度。在有n的结点的二叉树中，有n+1个空指针。

在线索二叉树中，原本为空的指针被重新利用，成为存储遍历过程中的前驱或后继节点的指针。这些指针相当于给节点添加了一种额外的属性，用于指示在某种遍历顺序（例如中序遍历）下，下一个要访问的节点是什么。也就是把各种遍历的指针变为这个节点的属性了，费空间省时间。

在二叉树线索化时，通常规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向后继结点。还需要增加两个标志域表明当前指针域所指对象是指向左（右）子结点还是指向直接前驱（后继）。

线索二叉树的存储结构描述如下：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode,*ThreadTree;

以这种结点构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前节点的左右指针域是否为空，若为空，将它们改为指向前驱结点或指向后继结点的线索。

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程。

以中序遍历对二叉树线索化的递归算法为例：

前驱结点：

1. 若左指针为线索，则其指向结点为前驱结点
2. 若左指针为左孩子，则其左子树的最右侧结点为前驱结点

后继结点：

1. 若右指针为线索，则其指向结点为后继结点
2. 若右指针为右孩子，则其右子树的最左侧结点为后继结点

void InThread(ThreadTree& p, ThreadTree& pre){//线索二叉树的根结点，指向前驱结点的指针
    if( p != NULL){
        InThread(p->lchild,pre);    //递归，线索化左子树
        if( p->lchild == NULL){        //左子树为空，建立前驱线索
            p->lchild == pre;
            p->ltag = 1;
        }
        if( pre != NULL && pre->rchild == NULL){
            pre->rchild = p;        //建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = p;                    //标记当前结点成为刚刚访问过得结点
        InThread( p->rchild, pre);    //递归，线索化右子树
    }    
}

建立线索二叉树：

void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if( T != NULL ){            //非空二叉树线索化
        InThread(T,pre);        //线索化二叉树
        pre->rchild = NULL;        //处理遍历的最后一个结点
        pre->rtag = 1;
    }    
}

有时为了方便，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild指针指向二叉树的二叉树的根结点，令 rchild 指针指向中序遍历时访问的最后一个结点；令中序遍历的第一个节点的lchild指针和最后一个结点的rchild指针均指向头结点。这就好比为二叉树建立了一个双向线索链表，既可以从第一个结点顺后继进行遍历，也可以从最后一个结点顺前驱进行遍历。

线索二叉树的遍历

不含头结点的线索化二叉树的遍历算法：

1. 求中序线索二叉树中中序序列的第一个结点：

   ThreadNode* FirstNode(ThreadNode* p){
       while( p->ltag == 0){
           p = p->lchild;
       }
       return p;   
   }

2. 求中序线索二叉树中结点p在中序序列下的后继结点：

   ThreadNode* NextNode(ThreadNode* p){
       if( p->rtag == 0 ){
           return FirstNode(p->rchild);
       }else{
           return p->rchild;
       }
   }

3. 中序遍历

   void InOrder(ThreadNode* T){
       for( ThreadNode* p = FirstNode(T); p != NULL; p = NextNode(p)){
           visit(p);
       }
   }

   另外添加的函数：

4. 中序线索二叉树的最后一个结点

   ThreadNode* LastNode(ThreadNode* p){
       while( p->rtag == 0 ){
           p = p->rchild;
       }
       return p;
   }

5. 求中序线索二叉树中结点p在中序序列下的前驱结点：

   ThreadNode* PreNode(ThreadNode* p){
       if( p->ltag == 0){
           return FirstNode(p->lchild);
       }else{
           return p->lchild;
       }    
   }

图

图（Graph）：由顶点的非空有限集合 V （由 n>0 个顶点组成）与边的集合 E（顶点之间的关系）构成的结构。其形式化定义为 G=(V,E)

• 顶点（Vertex）：图中的数据元素通常称为顶点，在下面的示意图中我们使用圆圈来表示顶点。
• 边（Edge）：图中两个数据元素之间的关联关系通常称为边，在下面的示意图中我们使用连接两个顶点之间的线段来表示边。边的形式化定义为：e=⟨u,v⟩，表示从 u 到 v 的一条边，其中 u 称为起始点，v 称为终止点。

• 子图（Sub Graph）：对于图 G=(V,E) 与 G′=(V′,E′)，如果存在 V′⊆V，E′⊆E，则称图 G′ 是图 G 的一个子图。在下面的示意图中我们给出了一个图 G 及其一个子图 G′。特别的，根据定义，G 也是其自身的子图。

图的分类

有向图与无向图：按照边是否有方向，我们可以将图分为两种类型：「无向图」和「有向图」。

• 无向图（Undirected Graph）：如果图中的每条边都没有指向性，则称为无向图。例如朋友关系图、路线图都是无向图。
• 有向图（Directed Graph）：如果图中的每条边都具有指向性，则称为有向图。例如流程图是有向图。

在无向图中，每条边都是由两个顶点组成的无序对。例如下图左侧中的顶点 v1 和顶点 v2 之间的边记为(v1,v2) 或 (v2,v1)

在有向图中，有向边也被称为弧，每条弧是由两个顶点组成的有序对，例如下图右侧中从顶点 v1 到顶点 v2 的弧，记为⟨v1,v2⟩，v1 被称为弧尾，v2 被称为弧头，如下图所示。

如果无向图中有 n 个顶点，则无向图中最多有 n*(n−1)/2条边。而具有n*(n−1)/2 条边的无向图称为 「完全无向图（Completed Undirected Graph）」。

如果有向图中有 n 个顶点，则有向图中最多有 n×(n−1) 条弧。而具有 n×(n−1)条弧的有向图称为 「完全有向图（Completed Directed Graph）」。如下图所示，左侧为包含 4 个顶点的完全无向图，右侧为包含 4 个顶点的完全有向图。

下面介绍一下无向图和有向图中一个重要概念 「顶点的度」。

• 顶点的度：与该顶点 vi 相关联的边的条数，记为 TD(vi)

例如上图左侧的完全无向图中，顶点 v3的度为 3。而对于有向图，我们可以将顶点的度分为 「顶点的出度」 和 「顶点的入度」。

• 顶点的出度：以该顶点 vi 为出发点的边的条数，记为OD(vi)。
• 顶点的入度：以该顶点 vi为终止点的边的条数，记为ID(vi)。
• 有向图中某顶点的度 = 该顶点的出度 + 该顶点的入度，即 TD(vi)=OD(vi)+ID(vi)。

例如上图右侧的完全有向图中，顶点 v3 的出度为 3，入度为 3，顶点 v3 的度为 3+3=6

---

环形图和无环图

如果顶点 vi0 可以通过一系列的顶点和边，到达顶点 vim，则称顶点 vi0 和顶点 vim 之间有一条路径，其中经过的顶点序列则称为两个顶点之间的路径。

• 环（Circle）：如果一条路径的起始点和终止点相同（即 vi0==vim），则称这条路径为「回路」或者「环」。
• 简单路径：顶点序列中顶点不重复出现的路径称为「简单路径」。

而根据图中是否有环，我们可以将图分为「环形图」和「无环图」。

• 环形图（Circular Graph）：如果图中存在至少一条环路，则该图称为「环形图」。
• 无环图（Acyclic Graph）：如果图中不存在环路，则该图称为「无环图」。

特别的，在有向图中，如果不存在环路，则将该图称为「有向无环图（Directed Acyclic Graph）」，缩写为 DAG。因为有向无环图拥有为独特的拓扑结构，经常被用于处理动态规划、导航中寻求最短路径、数据压缩等多种算法场景。

如下图所示，分别为：无向无环图、无向环形图、有向无环图和有向环形图。其中有向环形图中的顶点 v1、v2、v3与相连的边构成了一个环。

---

连通图和非连通图

在无向图中，如果从顶点 vi到顶点 vj 有路径，则称顶点vi和vj是连通的。

• 连通无向图：在无向图中，如果图中任意两个顶点之间都是连通的，则称该图为连通无向图。
• 非连通无向图：在无向图中，如果图中至少存在一对顶点之间不存在任何路径，则该图称为非连通无向图。

如下图所示，左侧图中 v1 与 v2、v3、v4、v5、v6 都是连通的，所以该图为连通无向图。右侧图中 v1 与 v2、v3、v4 都是连通的，但是 v1 和 v5、v6 之间不存在任何路径，则该图为非连通无向图。

下面介绍一下无向图的「连通分量」概念。有些无向图可能不是连通无向图，但是其子图可能是连通的。这些子图称为原图的连通子图。而无向图的一个极大连通子图（不存在包含它的更大的连通子图）则称为该图的「连通分量」。

• 连通子图：如果无向图的子图是连通无向图，则该子图称为原图的连通子图。
• 连通分量：无向图中的一个极大连通子图（不存在包含它的更大的连通子图）称为该图的连通分量。
• 极⼤连通⼦图：无向图中的一个连通子图，并且不存在包含它的更大的连通子图。

例如上图中右侧的非连通无向图，其本身是非连通的。但顶点 v1、v2、v3、v4 与其相连的边构成的子图是连通的，并且不存在包含它的更大的连通子图了，所以该子图是原图的一个连通分量。同理，顶点v5、v6 与其相连的边构成的子图也是原图的一个连通分量。

---

强连通有向图和强连通分量

在有向图中，如果从顶点 vi 到 vj 有路径，并且从顶点vj到 vi也有路径，则称顶点 vi与vj是强连通的。这两个特殊的概念只存在于有向图之中

• 强连通有向图：如果图中任意两个顶点vi和 vj，从 vi到 vj和从 vj到 vi都有路径，则称该图为强连通有向图。
• 非强连通有向图：如果图中至少存在一对顶点之间不存在任何路径，则该图称为非强连通有向图。

如下图所示，左侧图中任意两个顶点之间都有路径，则左侧图为强连通有向图。右侧图中顶点 v7 无法通过路径到达其他顶点，则右侧图为非强连通有向图。

与无向图类似，有向图的一个极大强连通子图称为该图的 强连通分量。

• 强连通子图：如果有向图的子图是连通有向图，则该子图称为原图的强连通子图。
• 强连通分量：有向图中的一个极⼤强连通⼦图，称为该图的强连通分量。
• 极⼤强连通⼦图：有向图中的一个强连通子图，并且不存在包含它的更大的强连通子图。

例如上图中，右侧的非强连通有向图，其本身不是强连通的（顶点 v7 无法通过路径到达其他顶点）。但顶点v1、v2、v3、v4、v5、v6与其相连的边构成的子图（即上图的左侧图）是强连通的，并且不存在包含它的更大的强连通子图了，所以该子图是原图的一个强连通分量（即上图中的左侧图是右侧图的强连通分量）。同理，顶点 v7构成的子图也是原图的一个强连通分量。

---

带权图

有时，图不仅需要表示顶点之间是否存在某种关系，还需要表示这一关系的具体细节。这时候我们需要在边上带一些数据信息，这些数据信息被称为 权。在具体应用中，权值可以具有某种具体意义，比如权值可以代表距离、时间以及价格等不同属性。

• 带权图：如果图的每条边都被赋以⼀个权值，这种图称为带权图。
• 网络：带权的连通⽆向图称为⽹络。

在下面的示意图中，我们给出了一个带权图的例子。

---

稠密图和稀疏图

根据图中边的稀疏程度，我们可以将图分为「稠密图」和「稀疏图」。这是一个模糊的概念，目前为止还没有给出一个量化的定义。

• 稠密图：有很多条边或弧（边的条数 e 接近于完全图的边数）的图称为稠密图。
• 稀疏图：有很少条边或弧（边的条数e 远小于完全图的边数，如 e < n*log2n）的图称为稀疏图。

图的存储方式

图的结构比较复杂，我们需要表示顶点和边。一个图可能有任意多个（有限个）顶点，而且任何两个顶点之间都可能存在边。我们在实现图的存储时，重点需要关注边与顶点之间的关联关系，这是图的存储的关键。

图的存储可以通过「顺序存储结构」和「链式存储结构」来实现。其中顺序存储结构包括邻接矩阵和边集数组。链式存储结构包括邻接表、链式前向星、十字链表和邻接多重表。

领接矩阵

邻接矩阵是图的常用存储表示，它的底层依赖一个二维数组。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

//领接矩阵声明，开一个二维数组； 
//1.二维数组w[u][v],存储u - v的边权（就是这个连线多长）
//2.只能在稠密图上使用（稠密图 就是边和点不是一个数量级的  点小于边）
//应该是 一个数组存储点 一个数组存储边； 用数组下标表示点和边的关系
#include<iostream>
using namespace std;

int w[N][N]; //声明边权数组 - 例如w[a][b] = c; 说明的就是a连上了b 线的长度 = c
int vis[N];//点集

void dfs(int u){
    vis[u] = true;
    for(int v = 1;v<=n;v++){
        printf("%d,%d,%d\n",u,v,w[u][v]);
        if(vis[u]) continue;
        dfs(v);
    }
}

int main()
{
    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        cin>>a>>b;
        w[a][b] = c; //赋予权值（a点 和 b点）（算是连线）
        //w[b][a] = c;
    }
    //遍历打印
    dfs(1);
    return 0;
}

边集数组：使用一个数组来存储存储顶点之间的邻接关系。数组中每个元素都包含一条边的起点 vi、终点 vj 和边的权值 val（如果是带权图）。在下面的示意图中，左侧是一个有向图，右侧则是该有向图对应的边集数组结构。

采用边集数组计算节点的度或者查找某条边时，需要遍历整个边集数组，时间复杂度为 O(m)，m 是边的数量。除非特殊必要，很少用使用边集数组来存储图(也就是领接矩阵法)。一般来说，边集数组适合那些对边依次进行处理的运算，不适合对顶点的运算和对任何一条边的运算。

我们可以声明一个结构体，用于存储每条边对应的两个节点及其权重。通过使用结构体，能够避免分别为节点和边权单独声明数组。我们只需在结构体中声明两个变量表示节点，一个变量表示边的权重。

#include<iostream>
using namespace std;

struct edge {
    int u, v, w; // 两点和权值
} e[1000]; // 假设 M=1000，边集合大小

int vis[1000]; // 假设 N=1000，点的标记数组

// BFS负责宽度搜索
void bfs(int u) {
    vis[u] = true;
    for (int i = 1; i <= 1000; i++) { // 假设最多有1000条边
        int v = e[i].v, w = e[i].w; // 用结构体中的值
        printf("%d,%d,%d\n", u, v, w);
        if (vis[v]) continue; // 如果这个点到过了
        bfs(e[i].v); // 继续BFS搜索下一个点
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
        // e[i] = {b, a, c}; // 无向图需要这行
    }
    bfs(1);
    return 0;
}

领接表

顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。

无向图：下图所示的就是一个无向图的邻接表结构。

从上图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge(顶点节点)是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。例如：v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。

有向图：若是有向图，邻接表结构是类似的，但要注意的是有向图由于有方向的。因此，有向图的邻接表分为出边表和入边表（又称逆邻接表），出边表的表节点存放的是从表头节点出发的有向边所指的尾节点；入边表的表节点存放的则是指向表头节点的某个顶点，如下图所示。

带权图：对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如下图所示。

#include<iostream>
#include<vector> // 引入 vector 库
using namespace std;

const int N = 1000; // 假设 N 的大小为 1000，可以根据需要调整

struct edga {
    int v, w; // 终点和权重
};

vector<edga> e[N]; // 存储每个节点的出边信息
bool vis[N]; // 访问标记数组

void dfs(int u, int fa) {
    vis[u] = true; // 标记节点已访问
    for (auto ed : e[u]) { // 遍历 u 的所有出边
        int v = ed.v, w = ed.w;
        if (v == fa) continue; // 跳过父节点，避免回到父节点
        printf("%d, %d, %d\n", u, v, w); // 输出 u -> v 的边和权重
        if (!vis[v]) dfs(v, u); // 深度优先遍历 v 节点
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // 无向图，双向连接
        e[a].push_back({b, c});
        e[b].push_back({a, c}); // 这里修正为正确的双向连接
    }
    dfs(1, 0); // 从节点 1 开始 DFS，父节点设为 0
    return 0;
}

链式领接表：邻接表与散列表有点类似，使用拉链法表示节点数组和各个节点的关系

邻接表通过数组存储顶点，通过链表存储各顶点的邻接点，能够在稀疏图中节省空间。然而，当链表过长时，查找特定的邻接点会变得低效，为了提高查找效率，我们可以将链表替换为更高效的数据结构，如平衡二叉树（如红黑树）、跳表或散列表，它们可以将查找复杂度降低到 O(log⁡n)或 O(1)。

我们可以声明一个数组，每个数组元素对应一个顶点，每个顶点通过数组对应到一个链表，链表存储的是与该顶点相邻的其他顶点。链表存储该顶点的所有邻接点，若链表的 next 为 null，则表示该顶点无出边。

h数组存储插入数据的编号，在这里也就是输入的e这些节点编号，这样就构成了逻辑上的链。e数组存储的是两个不同的节点连接的信息。

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

const int N = 1000; // 设置图的最大节点数

struct edge { int u, v, w; };
vector<edge> e;       // 边集合（边的属性）
vector<int> h[N];     // 点的所有出边头数组

void add(int a, int b, int c) {
    e.push_back({a, b, c});   // 对应边的属性压入，同时size也会增加
    h[a].push_back(e.size() - 1); // 将边号存入点的出边集合，也就是按照先后顺序占据链表的位置
}

void dfs(int u, int fa) {
    for (auto j : h[u]) {    // 遍历点u的所有出边
        int v = e[j].v, w = e[j].w;
        if (v == fa) continue;  // 忽略父节点
        printf("%d, %d, %d\n", u, v, w);
        dfs(v, u); // 递归搜索
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        // 邻接表存储无向图数据
        add(a, b, c); //a当链头
        add(b, a, c); //b当链头
    }
    dfs(1, 0); // 1是当前节点, 0是当前节点的父节点（根没有父节点）
    return 0;
}

链式前向星：实质上就是使用静态链表(数组和结构体模拟)实现的邻接表。链式前向星将边集数组和邻接表相结合，可以快速访问一个节点所有的邻接点，并且使用很少的额外空间。

链式前向星由两种数据结构组成：

• 特殊的边集数组：edges，其中 edges[i] 表示第 i 条边。edges[i].vj 表示第 i 条边的终止点，edges[i].val 表示第 i 条边的权值，edges[i].next 表示与第 i 条边同起始点的下一条边的存储位置。
• 头节点数组：head，其中 head[i] 存储以顶点 i 为起始点的第 1 条边在数组 edges 中的下标。

链式前向星其实并没有改变边集数组原来的存储数学，只是利用 head 数组构成静态链表，建立了顶点 vi 和顶点 vi 所连第 1 条边的关系。在下面的示意图中，左侧是一个有向图，右侧则是该有向图对应的链式前向星结构。

如果需要在该图中遍历顶点 v1 的所有边，则步骤如下：

• 找到以顶点 v1 为起始点的的 1 条边在数组 edges 中的下标，即 index = head[1] = 1。则在 edges 数组中找到与顶点 v1 相连的第 1 条边为 edges[1]，即 ⟨v1,v5⟩，权值为 6。
• 查找 index = self.edges[1].next = 0，则在 edges 数组中找到与顶点 v1 相连的第 2 条边 edges[0]，即 ⟨v1,v2⟩，权值为 5。
• 继续查找 index = self.edges[0].next = -1，则不存在其余边，查找结束。

#include <iostream>
#include <vector>
#include <cstring> // for memset
using namespace std;

const int M = 1e5; // 最大边数
const int N = 1e5; // 最大节点数

struct edge {
    int v, w, ne; // 终点、权重、下一个边的索引
};

edge e[M]; // 边集合
int idx = 0, h[N]; // idx 是边的索引，h 是每个节点的第一条出边的链头

// 连接出边
void add(int a, int b, int c) {
    e[idx] = {b, c, h[a]}; // 创建边
    h[a] = idx++; // 更新链头
}

// 深度优先搜索 - 这个图可以看做是一个斜树
void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = e[i].ne) { // 遍历所有出边，会遇到父节点
        int v = e[i].v, w = e[i].w;
        if (v == fa) continue; // 不回到父节点
        printf("%d,%d,%d\n", u, v, w); // 打印边信息
        dfs(v, u); // 递归
    }
}

int main() {
    int n, m; // 节点数和边数
    cin >> n >> m;
    memset(h, -1, sizeof h); // 初始化链头为-1

    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c; // 输入边信息
        add(a, b, c); // a为链头
        add(b, a, c); // b为链头
    }

    dfs(1, -1); // 从节点1开始DFS
    return 0;
}

图的遍历

深度优先搜索算法：英文缩写为 DFS，是一种用于搜索树或图结构的算法。深度优先搜索算法采用了回溯思想，从起始节点开始，沿着一条路径尽可能深入地访问节点，直到无法继续前进时为止，然后回溯到上一个未访问的节点，继续深入搜索，直到完成整个搜索过程。

深度优先搜索算法中所谓的深度优先，就是说优先沿着一条路径走到底，直到无法继续深入时再回头。在深度优先遍历的过程中，我们需要将当前遍历节点 u 的相邻节点暂时存储起来，以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点，这正是「递归」和「栈」所遵循的规律，所以深度优先搜索可以通过「递归」或者「栈」来实现。

接下来我们以一个无向图为例，介绍一下深度优先搜索的算法步骤。

• 选择起始节点 u，并将其标记为已访问。

  

• 检查当前节点是否为目标节点（看具体题目要求）。

  

• 如果当前节点 u 是目标节点，则直接返回结果。

  

• 如果当前节点 u 不是目标节点，则遍历当前节点 u 的所有未访问邻接节点。

  

• 对每个未访问的邻接节点 v，从节点 v 出发继续进行深度优先搜索（递归）。

  

• 如果节点 u 没有未访问的相邻节点，回溯到上一个节点，继续搜索其他路径。

  

• 重复 2∼6步骤，直到遍历完整个图或找到目标节点为止。

在实现 DFS 时，首先需要明确递归的要素：入口节点，即遍历的起始点；trap 操作，用于在遍历过程中处理节点之间的连接；up 操作，当无法继续进行 trap 操作时，用于回溯到上一个节点，这里的回溯一般是最外部的for循环更新。

简单总结一下可以发现，『深度优先遍历』其实就是一个『递归』的过程，如果再细心观察，可以发现，其实整个遍历过程就像是一棵树的『前序遍历』，我们将上面到流程简单总结一下其实就是下图这样到流程

// 定义边的结构体
struct Edge {
    int v; // 终点
    int w; // 权重
};

// 邻接表（链式前向星）
vector<Edge> adj[N]; // N 是最大节点数
// 声明一个标记数组,标记节点是否被访问
bool vis[N];

void dfs(int u,int fa)
{
    vis[u] = true; // 标记已经被访问过了
    for(const auto edge : adj[u]) //edge的位置表示链头集合
    {
        int v = edge.v, w = edge.w;
        if(v == fa || vis[v]) continue;
        printf("%d,%d,%d\n", u, v, w); // 打印边的信息
        dfs(v,u);
    }
    
}

大致模拟一下也就是这样

// 第一个for循环
edge[1] -> u -> v
dfs(u,v)
edge[u]->v->w
dfs(v,w)
.....
// 第二个for循环
edge[2] -> u-> v
....

广度优先遍历（BreadthFirstSearch），又称为广度优先搜索，简称 BFS，是最简便的图的搜索算法之一，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果，换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止，我们可以对照下图来进行理解

要实现对上图的广度遍历，我们可以利用队列来实现，比如我们以 A 为起点，流程如下

因为遍历到的节点顺序符合「先进先出」的特点，所以广度优先搜索可以通过「队列」来实现。接下来我们以一个无向图为例，介绍一下广度优先搜索的算法步骤。

• 将起始节点 u 放入队列中，并标记为已访问。

• 从队列中取出一个节点，访问它并将其所有的未访问邻接节点 v 放入队列中，也就是访问这个节点的所有子节点。

• 标记已访问的节点 v，以避免重复入队。

• 访问完一个节点的所有领接点就将这个节点出队

• 重复步骤 上述步骤

• 将队列中的节点出队

• 结点出队，队列为空算法结束

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 定义图的节点数据结构
struct Node {
    int value;  // 节点的值
    vector<Node*> neighbors;  // 相邻节点列表，存储的是邻居节点
    bool visited;  // 标记节点是否已经访问过

    Node(int val) : value(val), visited(false) {}
};

// BFS遍历函数
void bfs(Node* start) {
    queue<Node*> q;
    q.push(start);
	// 循环入队出队，直到队列彻底为空
    while (!q.empty()) {
        Node* cur = q.front();
        // 入队完成之后就出队，可以省去标记
        q.pop();

        if (!cur->visited) {
            // 访问其他节点
            cout << "Visiting node with value: " << cur->value << endl;
            cur->visited = true;

            for (Node* neighbor : cur->neighbors) {
                if (neighbor && !neighbor->visited) {
                    q.push(neighbor);
                }
            }
        }
    }
}

int main() {
    // 创建图节点

    // 释放节点内存
    delete node1;
    delete node2;
    delete node3;
    delete node4;

    return 0;
}

拓扑排序*

有向无环图（Directed Acyclic Graph, DAG）。DAG是一个专业术语，虽然对于一般人比较陌生，但它实际上隐藏在生活中的方方面面。例如，一个工程项目有多个子项目组成，子项目之间有先后关系，一个子项目的开展必须保证前面的项目完成；工厂里面生产的产品，产品由若干部件组成，每个部件再由多个零件组成，组装时必须保证一定的先后顺序。在软件领域，我们也会不知不觉地碰到DAG，例如程序模块之间的依赖关系、makefile脚本、区块链、git分支等。

按照依赖关系对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现，这种排序就是拓扑排序。

例如，下图中1 → 2 → 4 → 3 → 5是一个正确的拓扑排序，每个节点都在它说依赖的节点后面。而1 → 2 → 3 → 4 → 5则不满足拓扑排序的要求，3依赖于4却出现在前面。

对于有向图进行拓扑排序要解决两个问题：一是要判断待排序的有向图是不是无环；二是按照依赖关系生成正确的序列。

我们可以从入度着手，选择一个入度为0的节点，说明该节点不依赖于其他节点，可以放在结果序列最前面。然后，删除该节点和节点的边，找出下一个入度为0的节点，依次放到结果序列中。重复以上过程，即可完成拓扑排序。这种方法可称之为入度方法。

同样，我们也可以从出度着手，选择一个出度为0的节点，说明没有任何节点依赖该节点，可以放到结果序列最末尾。然后，删除该节点和节点的边，找出下一个出度为0的节点，依次放到结果序列尾部。重复以上过程，即可完成拓扑排序。这种方法可称之为出度方法。

不管是入度方法还是出度方法，如果最后还存在入（出）度不为0的节点，或者结果序列中的节点个数不等于有向图中的节点个数，说明有向图中存在环。

拓扑排序主要有Kahn算法和DFS（深度优先搜索）算法两种。Kahn算法采用入度方法，以循环迭代方法实现；DFS算法采用出度方法，以递归方法实现。Kahn算法和DFS算法的复杂度是一样的，算法过程也是等价的，不分优劣，因为本质上循环迭代 + 栈 = 递归。

KAHN算法*

Kahn算法采用入度方法，其算法过程如下：

1. 选择入度为0的节点，输出到结果序列中；
2. 删除该节点以及该节点的边；
3. 重复执行步骤1和2，直到所有节点输出到结果序列中，完成拓扑排序；如果最后还存在入度不为0的节点，说明有向图中存在环，无法进行拓扑排序。

下图是对Kahn算法的演绎：

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

const int N = 100005;  // 假设最大顶点数为 100000

vector<int> e[N];   // 邻接表存储图
vector<int> tp;     // 存储最终输出的拓扑序列
int din[N];         // 存储每个顶点的入度
int n, m;           // 顶点数和边数

bool toposort() {
    queue<int> q;

    // 初始化：将所有入度为 0 的顶点加入队列
    for (int i = 1; i <= n; i++) {
        if (din[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();  // 从队列中取出队头

        tp.push_back(x);  // 加入拓扑序列

        // 删除以 x 为起点的所有边
        for (int y : e[x]) {
            if (--din[y] == 0) q.push(y);  // 如果 y 的入度为 0，加入队列
        }
    }

    // 如果拓扑序列中的顶点数等于图中的顶点数，则返回 true
    return tp.size() == n;
}

int main() {
    cin >> n >> m;

    // 读取图的边信息
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        din[b]++;
    }

    if (!toposort()) {
        puts("-1");  // 如果无法形成拓扑序列，输出 -1
    } else {
        for (int x : tp) printf("%d ", x);  // 输出拓扑序列
        puts("");  // 换行
    }

    return 0;
}

DFS算法

DFS算法采用出度算法，其算法过程如下：

1. 对有向图进行深度优先搜索；
2. 在执行深度优先搜索时，若某个顶点不能继续前进，即顶点的出度为0，则将此顶点入栈。
3. 最后对栈中的序列进行逆排序，即完成拓扑排序；如果深度优先搜索时，碰到已遍历的节点，说明存在环。

下图是对DFS算法的演绎：

#include <iostream>
#include <vector>
#include <algorithm>  // 引入 reverse 函数
#include <cstring>    // 引入 memset 函数，用于初始化数组
using namespace std;

const int N = 100005;  // 假设最大顶点数为 100000

vector<int> e[N];   // 邻接表表示的图
vector<int> tp;     // 存储最终的拓扑序列
int c[N];           // 用于染色的数组（0：未访问，-1：正在访问，1：已访问）
int n, m;           // 顶点数和边数

bool dfs(int x) {
    c[x] = -1;  // 将当前节点标记为正在访问

    for (int y : e[x]) {
        if (c[y] < 0) return false;  // 如果 y 正在访问中，说明存在环
        if (c[y] == 0 && !dfs(y)) return false;  // 如果 y 未访问，则继续 DFS
    }

    c[x] = 1;           // 当前节点访问完成，标记为已访问
    tp.push_back(x);    // 将节点加入拓扑序列
    return true;
}

bool toposort() {
    memset(c, 0, sizeof(c));  // 初始化所有节点为未访问状态

    for (int x = 1; x <= n; x++) {
        if (c[x] == 0) {
            if (!dfs(x)) return false;  // 如果发现有环，返回 false
        }
    }

    reverse(tp.begin(), tp.end());  // 翻转拓扑序列，使其为正确的顺序
    return true;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
    }

    if (!toposort()) {
        cout << "-1" << endl;  // 如果存在环，输出 -1
    } else {
        for (int x : tp) cout << x << " ";  // 输出拓扑序列
        cout << endl;
    }

    return 0;
}

最短路问题

单源最短路径（Single Source Shortest Path）：对于一个带权图 G=(V,E)，其中每条边的权重是一个实数。另外，给定 v 中的一个顶点，称之为源点。则源点到其他所有各个顶点之间的最短路径长度，称为单源最短路径。

这里的路径长度，指的是路径上各边权之和。单源最短路径问题的核心是找到从源点到其他各个顶点的路径，使得路径上边的权重之和最小。

常见的解决单源最短路径问题的算法包括：

1. Dijkstra 算法：一种贪心算法，用于解决无负权边的情况。它逐步扩展当前已知最短路径的范围，选择当前距离起始节点最近的节点，并更新与该节点相邻的节点的距离。同时也是单源最短路算法之一。
2. Bellman-Ford 算法：适用于有负权边的情况。它通过多次迭代来逐步逼近最短路径，每次迭代都尝试通过更新边的权重来缩短路径。
3. SPFA 算法：优化的 Bellman-Ford 算法，它在每次迭代中不遍历所有的边，而是选择性地更新与当前节点相关的边，从而提高了算法的效率。

Dijkstra

使用 Dijkstra 算法，可以寻找图中节点之间的最短路径。特别是，可以在图中寻找一个节点（称为源节点）到所有其它节点的最短路径，生成一个最短路径树。

GPS 设备使用这个算法来寻找当前位置到目标位置的最短路径。Dijkstra 算法被广泛应用在工业上，尤其是需要建模网络的领域。

• Dijkstra算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径。
• Dijkstra 算法会记录当前已知的最短路径，并在寻找到更短的路径时更新。
• 一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为已访问并添加到路径中。
• 重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案

Dijkstra 只能用在权重为正的图中，因为计算过程中需要将边的权重相加来寻找最短路径。如果图中有负权重的边，这个算法就无法正常工作。一旦一个节点被标记为已访问，当前访问它的路径就被标记为访问它的最短路径。如果存在负权重，则可能在之后的计算中得到总权重更小的路径，从而影响之前的结果。

工作原理：

假设有下面这个图：

Dijkstra 算法将会寻找出图中节点 0 到所有其他节点的最短路径

我们将会得到节点 0 到节点 1、节点 0 到节点 2、节点 0 到 节点 3……（以此类推）的最短路径。

初始的距离列表如下：

• 源节点到它自身的距离为 0。示例中的源节点定为节点 0，不过你也可以选择任意其它节点作为源节点。
• 源节点到其它节点的距离还没有确定，所以先标记为无穷大。这个算法的目的就是将这个表构造完成。

还有一个列表用来记录哪些节点未被访问（即尚未被包含在路径中）

记住，当所有节点都被添加到路径中时，算法的计算过程就完成了。

我们选择了从节点 0 出发，可以直接将它标记为“已访问”，同样的，在未访问节点列表中把它划掉，并在图中给它加上红色的边框：

现在需要检查节点 0 到相邻节点的距离，两个相邻节点分别是节点 1 和节点 2（注意看红色的边）：

这并不是说立即把这两个相邻节点加入到最短路径中。在把一个节点加入到最短路径之前，需要确认是否已经寻找到了访问它的最短路径。现在只是在对可选方案做初步检查。

更新节点 0 到节点 1、节点 0 到节点 2 的距离为它们之间的边的权重，分别为 2 和 6：

更新了到相邻节点的距离之后：

• 根据已知的距离列表选择距离源节点最近的节点。
• 将它标记为“已访问”。
• 将它添加到路径中。

查看距离列表，发现节点 1 到源节点的距离是最短的（距离为 2），所以把它加入到路径中。在图中，以红色边来表示：

在距离列表中用红色方块标记这个节点，表明它是“已访问”的、已经寻找到了访问这个节点的最短路径：

在未访问节点列表中将它划掉：

现在分析新的相邻节点，寻找访问它们的最短路径。只需要分析已经在最短路径（标记为红色边）中的节点的相邻节点。

节点 2 和节点 3 都是最短路径包含的节点的相邻节点，因为它们分别与节点 0 和节点 1 直接相连，如下图所示。下一步将要分析这两个节点。

之前已经计算过源节点到节点 2 的距离，并记录在了列表中，所以不用更新。这次只需要更新源节点到新的相邻节点（节点 3）的距离：

这个距离是 7，来看看为什么。为了计算源节点到另一个节点（这里指节点 3）的距离，需要把访问该节点的最短路径的所有边权重相加：

• 对于节点 3： 将构成路径 0 -> 1 -> 3 的所有边权重相加，得到总距离为 7（0 -> 1 距离为 2，1 -> 3 距离为 5）。

现在得到了到相邻节点的距离，需要选择一个节点添加到路径中。我们必须选择一个已知到源节点距离最短的未访问节点。

从距离列表中可以看出，距离为 6 的节点 2 就是我们的选择：

在图中为它加上红色边框，并将路径上的边标记为红色：

在距离列表中用红色方块把它标记为“已访问”，在“未访问”节点列表中把它划掉：

重复前面的步骤，寻找源节点到新的相邻节点节点 3 的最短路径。

可以看到，有两种可选的路径：0 -> 1 -> 3 或 0 -> 2 -> 3。一起看看我们是如何确定最短路径的。

节点 3 在之前已经有了一个距离记录（距离为 7，参阅下表），这个距离是之前步骤中由路径 0 -> 1 -> 3 的两个边权重（分别为 5 和 2）相加得到的。

不过现在有了一个新的可选路径：0 -> 2 -> 3，它途经权重分别为 6 和 8 的两条边 0 -> 2 和 2 -> 3，总距离为 14。

显然，第一个路径的距离更短（7 vs. 14），所以选择第一个路径 0 -> 1 -> 3。只有在新的路径距离更短的情况下，才会更新距离列表。

因此，使用第一种方案 0 -> 1 -> 3，将节点添加到路径中。

把这个节点标记为“已访问”，在“未访问”节点列表中把它划掉：

重复前面的过程。检查尚未访问的相邻节点：节点 4 和节点 5，因为它们是节点 3 的相邻节点。

更新它们到源节点的距离，尝试寻找更短的路径：

• 对于节点 4： 路径是 0 -> 1 -> 3 -> 4，距离为 17。
• 对于节点 5： 路径是 0 -> 1 -> 3 -> 5，距离为 22。

注意我们只能从最短路径（红色边）上进行扩展，而不能途经未被包含在最短路径中的边（例如，不能构造经过边 2 -> 3 的路径）。

现在需要选择将哪个未访问节点标记为“已访问”，这里选择节点 4，因为在距离列表中它的距离最短。在图中做标记：

在距离列表中用红色方块将它标记为“已访问”：

在“未访问”节点列表中把它划掉：

再次重复前面的过程。检查相邻节点：节点 5 和节点 6。分析每一种从已访问节点到它们之间的可能路径方案。

对于节点 5：

• 第一种选择是路径 0 -> 1 -> 3 -> 5，到源节点的距离为 22（2 + 5 + 15），前面的步骤已经记录了这个距离。
• 第二种选择是路径 0 -> 1 -> 3 -> 4 -> 5，到源节点的距离为 23（2 + 5 + 10 + 6）。

显然，第一个路径距离更短，为节点 5 选择第一种方案。

对于节点 6：

• 可选的路径是 0 -> 1 -> 3 -> 4 -> 6，到源节点的距离为 19（2 + 5 + 10 + 2）。

把距离最短（当前已知）的节点 6 标记为“已访问”。

在“未访问”节点列表中把它划掉：

现在得到了如下路径（标记为红色）：

现在只剩下一个节点 5 还没被访问了，看看我们要如何把它添加到路径中。

从已经添加到路径中的节点出发，有三种不同的路径可以访问节点 5：

• 第一种选择： 0 -> 1 -> 3 -> 5，总距离为 22（2 + 5 + 15）。
• 第二种选择： 0 -> 1 -> 3 -> 4 -> 5，总距离为 23（2 + 5 + 10 + 6）。
• 第三种选择： 0 -> 1 -> 3 -> 4 -> 6 -> 5，总距离为 25（2 + 5 + 10 + 2 + 6）。

选择总距离为 22 的最短路径：0 -> 1 -> 3 -> 5。

把这个节点标记为“已访问”，并在“未访问”节点列表中把它划掉：

瞧！ 我们得到了从节点 0 到图中每个节点的最短路径。

图中，标记为红色的边表示最短路径：连接节点 0 和目标节点的红色边即为从源节点出发访问目标节点的最短路径。

例如，想要从节点 0 出发访问节点 6，连接它们的红色边就是最短路径，跟着走就行了。

• 图可以用来建模对象、人或实体之间的连接。它有两个关键要素：节点和边，节点表示对象，边表示对象之间的连接。
• Dijkstra 算法能够寻找出图中指定节点（“源节点”）到所有其他节点的最短路径。
• Dijkstra 算法利用边的权重来做计算，寻找源节点到所有其他节点的总距离最短（总权重最小）的路径。

---

接着用代码实现，从上面我们可以得出结论，构造迪杰斯特拉算法的重点是构造源点和目标点的距离表，同时需要维护一个节点表用于标记节点是否被访问，这里采用邻接表存储图像

• e[u] 存储图像

• d[u]记录边权

• vis[u]标记是否访问

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

using namespace std;

// 定义边的结构体，包含目标顶点v和边的权重w
struct edge {
    int v, w;
};

vector<edge> e[N]; // 邻接表表示的图，e[i]存储从顶点i出发的所有边
int d[N], vis[N];  // d[i]存储从起点到顶点i的最短路径长度，vis[i]表示顶点i是否已被访问，索引就是映射顶点号

// Dijkstra算法函数，计算从起点s到其他顶点的最短路径
void dijkstra(int s) {
    // 1.初始化所有顶点的最短路径长度为无穷大 - 这个d数组就是我们最终目的的距离表
    for(int i = 0; i < n; i++) d[i] = INT_MAX;
    d[s] = 0; // 起点的最短路径长度为0
    
    // 2.主循环，遍历所有节点
    for(int i = 1; i <= n; i++) { 
        int u = 0; // 当前未访问的顶点中距离最小的顶点
        
        // 3.找到当前未访问且与源点距离最小的顶点u(可能有很多备选方案)
        for(int j = 1; j <= n; j++) { 
            if(!vis[j] && d[j] < d[u]) u = j;
        }
        
        vis[u] = 1; // 4.标记顶点u已被访问
        
        // 5.更新与顶点u相邻的顶点的最短路径
        for(auto ed : e[u]) { // 枚举边
            int v = ed.v, w = ed.w; // 获取相邻顶点v及边的权重w
            if(d[v] > d[u] + w) { // 如果从u经过到v的路径更短，则更新d[v]
                d[v] = d[u] + w;
            }            
        }
    }    
}

int main() {
    int n, m, s;
    cin >> n >> m >> s; // 输入顶点数n，边数m，以及起点s
    
    // 输入图的边信息 - 编号，好使用数组映射关系
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c; // 输入边的起点a，终点b，和权重c
        e[a].push_back({b, c}); // 将边添加到邻接表中
    }
    
    dijkstra(s); // 调用Dijkstra算法，计算从起点s到其他顶点的最短路径
    return 0;
}

在Dijkstra算法中，遍历每个节点的后继节点以寻找最短路径可能导致效率低下。为优化这一过程，我们可以使用优先队列来快速筛选节点。与Kahn算法类似，我们可以将当前节点入队，并将其后继节点也加入队列。

由于使用的是优先队列，我们可以根据边的权重构建优先级，使得权重最小的节点优先出队。通过这种方式，我们可以采用贪心策略，以逐步更新每个节点的最短路径，最终构建出最短路径的节点关系数组。这样被称之为堆优化，堆优化的时间复杂度为O(logn)，

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

struct edge {
    int v, w;
}; 

vector<edge> e[N]; // 邻接表存储图，e[i]表示从顶点i出发的所有边
int d[N], vis[N];  // d数组存储从源点到每个点的最短距离，vis数组标记点是否被访问过
priority_queue<pair<int, int>> q; // 大根堆，存储负的距离值以实现优先队列
// s是源点
void dijkstra(int s) {
    for(int i = 0; i <= n; i++) d[i] = inf; 
    d[s] = 0; 
    //1. 将(0, s)入队，注意之后入队的距离为负值（大根堆）
    q.push({0, s}); 

    while(!q.empty()) { 
        //2. 取出队列中的元素，t为pair(-距离, 顶点)
        auto t = q.top();
        //3. 出队，每次只出队最小权值
        q.pop(); 
        int u = t.second; 

        if(vis[u]) continue;
        vis[u] = 1; // 标记顶点u为已访问
	    //4. 枚举出队节点u的所有出边指向的节点
        for(auto ed : e[u]) { 
            int v = ed.v; 
            int w = ed.w; 

            // 如果从u到v的路径比当前已知的最短路径更短，则更新d[v]
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                // 将(-d[v], v)入队，使用负值筛选出最小路径节点，每次只会出队一个
                q.push({-d[v], v}); 
            }
        }
    }
}

int main() {
    int n, m, s;
    // 输入顶点数n、边数m以及起点s
    cin >> n >> m >> s;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c}); // 将边(b, c)添加到顶点a的邻接表中
    }

    dijkstra(s); // 调用Dijkstra算法计算从源点到其他顶点的最短路径

    return 0;
}

Bellman-Ford

Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w是 边集E的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。

• 初始化：将除源点外的所有顶点的最短距离估计值都趋于无穷(一个很大的数)
• 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；运行V-1次
• 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

初始化，更新源点的距离，为之后松弛其他结点的权做准备。

迭代到源点连接的点上，将无穷松弛为经过的路径，在连接的节点处更新权值，权值为经过路径值的和。

对于迭代到的其他结点，重复上序的操作，重复次数为|V|-1；V表示当前图的节点个数

它的时间复杂度为 O(VE)，其中 V 是顶点数，E是边数。Bellman-Ford 算法的基本思想是对所有的边进行 V-1轮松弛操作，以求出所有可能的最短路径。如果在第 V轮松弛操作中仍然存在松弛的边，则说明图中存在负权环。

Bellman-Ford算法实现可以分为以下三步：

1. 初始化：为每个顶点设定一个初始距离值，表示从源点到该顶点的最短距离。将源点的距离设为0，其余所有顶点的距离设为无穷大（表示暂时不可达）。
2. 松弛操作：进行n-1次循环（n为顶点总数）。在每次循环中，遍历所有边，并通过松弛操作更新顶点的最短距离。每次迭代最多允许经过k条边找到从源点到目标顶点的最短路径，当迭代次数为k时，表示最短路径最多包含k条边。
3. 检查负权回路：最后，再遍历一次所有边，检查是否存在 d(v) > d(u) + w(u, v) 的情况。如果发现某个顶点距离仍能被更新，说明图中存在从源点可达的负权回路，返回 false，否则返回 true 表示无负权回路。

const int INF = 1e9;
const int N = 1005; // 根据你的需求设置节点数量上限

struct edge {
    int v, w;
};

vector<edge> e[N];
int d[N];

bool bellmanFord(int n, int s) {
    fill(d, d + n, INF);
    d[s] = 0;
	// 1.最多执行 n-1 轮松弛操作，整个图中每一条边会被处理最多 n-1 次
    for (int i = 0; i < n - 1; i++) { 
        bool flag = false;
        // 2.遍历所有节点
        for (int u = 1; u <= n; u++) {
            // 3.表示点与该点无通路
            if (d[u] == INF) continue;
            // 4.对节点 u 连接的所有边进行松弛操作，遍历边集数组
            for (auto ed : e[u]) {
                int v = ed.v, w = ed.w;
                if (d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    flag = true;
                }
            }
        }
        // 5.如果本轮没有发生任何松弛操作，说明所有节点的最短路径已确定，可以提前结束
        if (!flag) break; 
    }

    // 6.检测是否存在负权环
    for (int u = 1; u <= n; u++) {
        if (d[u] == INF) continue;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (d[v] > d[u] + w) {
                return true; // 存在负权环
            }
        }
    }

    return false; // 不存在负权环
}

Spfa 算法

SPFA算法是Bellman-Ford算法的队列优化。它可以求出单源最短路，也可检测到负环，实现起来也比较容易。可以证明，只有上一次迭代中松弛过的点才有可能参与下一次迭代的松弛操作。朴素的Bellman-Ford算法中对于每一次迭代，都会尝试松弛所有边，这无疑造成了巨大浪费。所以我们通过队列，保存所有松弛过的边，可以极大提高效率。

此外，SPFA算法还可以判断图中是否有负权环，即一个点入队次数超过N。给定一个有向图，求A~E的最短路。

源点A首先入队，并且AB松弛

扩展与A相连的边，B，C 入队并松弛。

B，C分别开始扩展，D入队并松弛

D出队，E入队并松弛。

E出队，此时队列为空，源点到所有点的最短路已被找到，A->E的最短路即为8

SPFA算法的实现可以分为以下三步：

1. 初始化：为每个顶点设定一个初始距离值，表示从源点到该顶点的最短距离。将源点的距离设为0，其余所有顶点的距离设为无穷大（表示暂时不可达）。同时，使用一个队列来存储待处理的顶点，并将源点入队。
2. 松弛操作：当队列不为空时，重复以下操作：从队列中取出一个顶点 u，然后遍历与 u 相连的所有边 (u, v)。对每条边进行松弛操作，检查是否能通过 u 来更新顶点 v 的最短距离。如果发现有更新，更新 d[v] 的值，并将 v 入队（如果 v 还未在队列中）。
3. 检查负权回路：在进行松弛操作时，利用一个计数器记录每个顶点的入队次数。如果某个顶点的入队次数超过了顶点总数 n，则说明图中存在负权回路，返回 false。如果所有顶点的入队次数均未超过 n，则表示无负权回路，返回 true。

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 200010; // 最大节点数
struct Edge {
    int to, next, w; // 目标节点、下一个边、边的权重
} edges[MAXN];

int n, m, edgeCount; // 节点数，边数，边的计数
int head[MAXN], dist[MAXN], inQueue[MAXN]; // head表示链表的头，dist存储最短距离，inQueue记录节点进入队列的次数
bool visited[MAXN]; // 记录节点是否在队列中

// 添加一条边
void addEdge(int from, int to, int weight) {
    edges[++edgeCount] = {to, head[from], weight};
    head[from] = edgeCount; // 更新链表头
}

// SPFA算法，返回是否无负环
bool spfa(int start) {
    queue<int> q;
    memset(visited, 0, sizeof(visited)); // 初始化所有节点未访问
    memset(dist, 0x3f, sizeof(dist));    // 初始化距离为无穷大
    memset(inQueue, 0, sizeof(inQueue)); // 初始化队列入队次数

    dist[start] = 0; // 起点的距离为0
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        visited[u] = false;

        //1. 遍历与节点u相连的所有边
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to, w = edges[i].w;

            //2. 尝试进行松弛操作,松弛过的边标记不再松弛
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w; // 更新距离

                // 3.如果节点v未在队列中，则将其入队
                if (!visited[v]) {
                    q.push(v);
                    visited[v] = true;
                    inQueue[v]++; // 检测入队次数

                    // 4.如果某个节点进入队列的次数超过n次，说明存在负环
                    if (inQueue[v] > n) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    int start, target;
    scanf("%d%d%d%d", &n, &m, &start, &target);

    // 输入边的信息
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w); // 添加有向边
    }

    // 判断是否存在负环，输出结果
    if (!spfa(start)) {
        printf("FAIL!\n");
    } else {
        printf("%d\n", dist[target]);
    }

    return 0;
}

总结：SPFA 算法将每一条边进行松弛，成功松弛的点会被入队。对于每一个点来说，可以重复入队，当入队的次数大于我们整个图的结点数的时候，说明这个图有负环。

Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。简单的来说，算法的主要思想是动态规划(dp)，而求最短路径需要不断松弛。

多源点的意思是同时计算图中所有节点对之间的最短路径，即从任意起点到任意终点的最短路径。也就是用一个二维数组存储所有点与点之间的关系。而前面的单源是用一维数组存储源点到其他点的关系。Floyd算法的时间复杂度为O(n^3)

算法的具体思想为：

1. 邻接矩阵(二维数组)dist储存路径，数组中的值开始表示点点之间初始直接路径，最终是点点之间的最小路径，有两点需要注意的，第一是如果没有直接相连的两点那么默认为一个很大的值(不要因为计算溢出成负数)，第二是自己和自己的距离要为0。
2. 从第1个到第n个点依次加入松弛计算，每个点加入进行试探枚举是否有路径长度被更改(自己能否更新路径)。顺序加入(k枚举)松弛的点时候，需要遍历图中每一个点对(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化，如果发生改变(变小)，那么两点(i,j)距离就更改。
3. 重复上述直到最后插点试探完成。

其中第2步的状态转移方程为:

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

其中dp[a][b]的意思可以理解为点a到点b的最短路径,所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思为k到j的最短路径.

咱们图解一个案例，初始情况每个点只知道和自己直接相连的点的距离，而其他间接相连的点还不知道距离，比如A-B=2,A-C=3但是B-C在不经过计算的情况是不知道长度的。

加入第一个节点A进行更新计算,大家可以发现，由于A的加入，使得本来不连通的B，C点对和B，D点对变得联通，并且加入A后距离为当前最小,同时你可以发现加入A其中也使得C-D多一条联通路径（6+3），但是C-D联通的话距离为9远远大于本来的(C,D)联通路径2，所以这条不进行更新。

咱们继续加入第二个节点B，这个点执行和前面A相同操作进行。对一些点进行更新。因为和B相连的点比较多，可以产生很多新的路径，这里给大家列举一下并做一个说明,这里新路径我统一用1表示，原来长度用0表示。

AF1=AB+BF=6+2=8 < AF0(∞) 进行更新

AE1=AB+BE=2+4=6 < AE0(∞) 进行更新

CE1=CB+BE=5+5=9 < CE0(∞)进行更新

CF1=CB+BF=5+6=11<CF0(∞)进行更新

EF1=EB+BF=4+6=10<EF0(∞)进行更新

当然，也有一些新的路径大于已有路径不进行更新，例如：

AC1=AB+BC=2+5=7>AC0(3) 不更新

AD1=AB+BD=2+8=10>AD0(6) 不更新

……

更多路径这里就不一一列举了。

后序加入C、D、E、F都是进行相同的操作,最终全部加完没有路径可以更新就结束停止。实际上这个时候图中的连线就比较多了。这些连线都是代表当前的最短路径。 这也和我们的需求贴合，我们最终要的是所有节点的最短路径。每个节点最终都应该有5条指向不同节点的边！ 矩阵对应边值就是点点之间最短路径。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9; // 定义一个大的值，表示两点之间不可达

// Floyd算法求解任意两点之间的最短路径
void floydWarshall(vector<vector<int>>& graph) {
    int n = graph.size();

    // 三重循环，遍历每个中间节点k，起点i，终点j
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (graph[i][k] < INF && graph[k][j] < INF) {
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }
}

int main() {
    int n, m; // n是节点数，m是边数
    cin >> n >> m;

    // 初始化图，graph[i][j]表示从i到j的距离，初始时不可达用INF表示
    vector<vector<int>> graph(n, vector<int>(n, INF));

    // 自己到自己的距离为0
    for (int i = 0; i < n; ++i) {
        graph[i][i] = 0;
    }

    // 读取边的输入
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 从u到v有一条权值为w的边
        graph[u][v] = w;
    }

    // 调用Floyd算法
    floydWarshall(graph);

    // 输出结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (graph[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << graph[i][j] << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

最小生成树*

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树

Kruskal算法

克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

• 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
• 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

以上图G4为例，来对克鲁斯卡尔进行演示(假设，用数组R保存最小生成树结果)。

1. 将边<E,F>加入R中。 边<E,F>的权值最小，因此将它加入到最小生成树结果R中。
2. 将边<C,D>加入R中。 上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
3. 将边<D,E>加入R中。上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
4. 将边<B,F>加入R中。上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
5. 将边<E,G>加入R中。上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
6. 将边<A,B>加入R中。 上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：

• 问题一 对图的所有边按照权值大小进行排序。
• 问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一：很好解决，采用排序算法进行排序即可。

问题二：处理方式是：记录顶点在最小生成树中的终点，顶点的终点是在最小生成树中与它连通的最大顶点。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

• C的终点是F。
• D的终点是F。
• E的终点是F。
• F的终点是F。

关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是与它连通的最大顶点。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的终点都是F，即它们的终点相同。

因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。由这样的逻辑结构，我们可以使用并查集将同一终点的节点路线归为同一个集合，这样在新加入路径的时候就可以判断出两个节点的终点是否不一致了。

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

#define maxn 110    //最多点个数
int n, m;   //点个数，边数
int parent[maxn];   //父亲节点，当值为-1时表示根节点
int ans;    //存放最小生成树权值
struct eage     //边的结构体，u、v为两端点，w为边权值
{
    int u, v, w;
}EG[5010];

// 1. 排序边权大小
bool cmp(eage a, eage b)    
{
    return a.w < b.w;
}
// 2. 并查集找到同一终点
int Find(int x)  
{
    if(parent[x] == -1) return x;
    return Find(parent[x]);
}
// 3.Kruskal算法，parent能够还原一棵生成树，或者森林
void Kruskal()      
{
    memset(parent, -1, sizeof(parent));
    sort(EG+1, EG+m+1, cmp);    //按权值将边从小到大排序
    ans = 0;
    for(int i = 1; i <= m; i++)     //按权值从小到大选择边 - 贪心
    {
        int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
        if(t1 != t2)    //若不是同一个终点，合并两棵树
        {
            ans += EG[i].w;
            parent[t1] = t2;
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n,&m))
    {
        for(int i = 1; i <= m; i++)
            scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w);
        Kruskal();
        printf("%d\n", ans);
    }
    return 0;
}

prim算法

Prim 算法的每一步都会为一颗生长中的数添加一条边：最开始这颗树只有一个顶点（起点），然后向它添加 V-1 条边，每次总是将下一条连接树中顶点与不在树中的顶点且权重最小的边（也就是横切边权重最小者），加入到树中。

• 选取任意顶点作为起点，则该顶点为树中顶点
• 从非树顶点集合中，找出横切边权重最小者，根据切分定理，这条边必然属于最小生成树；则边的另一个顶点也成为树中顶点
• 循环选取横切边，直到找到 V-1 条边（所有顶点都加入到树中），这些边构成最小生成树

• marked[] 数组
  记录当前顶点是否被扫描过。
• Queue<Edge> mst 对列
  Edge 表示图中的边，mst 记录最小生成树所有的边，长度为 V-1 。
• weight
  最小生成树的总权重。
• MinPQ<Edge> pq 优先队列
  小根堆，记录图中所有的边。
• G.adj(v)
  顶点 v 所有邻接点对应的边。

切分：也就是 marked 数组，如果顶点已经被扫描，则为 true。所以 marked 数组将所有顶点分成了两个非空且不重复的集合：{扫描过，未被扫描过} 。
横切边：一条边的两个顶点 v-w，其中顶点 v 已经被扫描，顶点 w 未被扫描，即 v, w 属于两个不同集合，而这条边就是横切边。如下算法实现中，始终取出小根堆中最小权重的边，当判断这条边是横切边时，则这条边属于最小生成树。

算法核心思路：

• 每个顶点都会有一条最小权重的横切边，逐个扫描顶点找出这条横切边
• 扫描顶点 v 时，该顶点的所有边中，如果另一个顶点没有被扫描过，则将边压入小根堆；也就是小根堆存储了图中所有的边
• 循环取出小根堆中最小的边，判断边两端顶点是否被扫描过（如果有一个顶点没有被扫描，说明这条边是横切边，且权重最小），即判断是否为横切边
• 将权重最小的横切边加入最小生成树队列中；继续扫描横切边中未被扫描的顶点，并将该顶点的边加入优先队列
• 优先队列循环出队，直到队列为空，或者最小生成树队列中有 V-1 条边

public class LazyPrimMST {

    private double weight;
    private Queue<Edge> mst;
    private boolean[] marked; 
    private MinPQ<Edge> pq;

    public LazyPrimMST(EdgeWeightedGraph G) {
        mst = new Queue<Edge>();
        pq = new MinPQ<Edge>();
        marked = new boolean[G.V()];
        // 逐个顶点扫描，找出权重最小横切边
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) prim(G, v);

    }

    // run Prim's algorithm
    private void prim(EdgeWeightedGraph G, int s) {
        scan(G, s);
        // better to stop when mst has V-1 edges
        while (!pq.isEmpty()) {
            // 取出权重最小的边
            Edge e = pq.delMin();
            int v = e.either(), w = e.other(v);
            assert marked[v] || marked[w];
            // 如果边的两个顶点都被扫描过，则继续出队
            if (marked[v] && marked[w]) continue;
            // 否则这条边为横切边，且权重最小
            // 将这条最小权重横切边，加入到最小生成树中
            mst.enqueue(e);
            weight += e.weight();
            // 沿着边的两端继续扫描
            if (!marked[v]) scan(G, v);
            if (!marked[w]) scan(G, w);
        }
    }

    // add all edges e incident to v onto pq 
    // if the other endpoint has not yet been scanned
    private void scan(EdgeWeightedGraph G, int v) {
        // 扫描顶点 v
        marked[v] = true;
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)]) pq.insert(e);
    }
}

在Prim算法的基础上，优化其使用的数据结构，把队列替换为优先队列。也被称之为Prim 即时实现。即时实现主要区别在于：优先队列中始终存储的是非树顶点到树中的最小权重横切边。

• 失效边

• 优先队列

从图解中看到四条边：7-2, 7-4, 0-4, 0-2 都是横切边，而 7-2 和 7-4 已经失效，因为 0-4 和 0-2 权重更小；对于优先队列始终只存储非树顶点 2, 4 到树中 0, 7 的最小权重横切边，即只存储 0-4, 0-2 。

• 图解

• 演示

• marked[] 数组
  记录当前顶点是否被扫描过。
• weight
  最小生成树的总权重。
• edgeTo[] 数组和 distTo[] 数组
  如果顶点 v 不在树中，但至少还有一条边和树相连。则 edgeTo[v] 是将顶点 v 与树相连的最短边，distTo[v] 为这条边的权重。
• PriorityQueue<Edge> pq 优先队列
  小根堆，记录图中非树顶点到树中的最小权重横切边，堆顶的最小权重横切边满足切分定理，而这条边的非树顶点就是下一个被添加到树中的顶点；该优先队列长度不会超过顶点数。
• G.adj(v)
  顶点 v 所有邻接点对应的边。

算法核心思路：

• 将 distTo[] 数组初始化为无限大，即所有边都不属于树
• 从加权无向图中任意指定起点 s，扫描该顶点及其对应的邻接边
• 如果邻接边的顶点被扫描过，则继续遍历其他邻接边顶点；如果没有被扫描过，则判断这条边是否比记录的小
• 如果这条边为权重更小，则更新 distTo[] 权重；将失效的边从优先队列中删除，并添加这条有效横切边到优先队列中
• 循环从优先队列中取出最小键（即满足切分定理的最小权重横切边），而和它关联的顶点 w 就是下一个被添加到树中的顶点；直到优先队列中所有的横切边都被取出，最小生成树生长完成

public class PrimMST {
    private Edge[] edgeTo;
    private double[] distTo;
    private boolean[] marked;
    private PriorityQueue<Edge> pq;
    private Double weight;

    public PrimMST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new PriorityQueue<>();
        weight = 0.0;
        // 初始化所有权重为无限大
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;

        // 逐个顶点扫描，计算最小生成树
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) prim(G, v);
    }
    
    private void prim(EdgeWeightedGraph G, int s){
        distTo[s] = 0.0;
        // 扫描顶点
        scan(G, s);

        while (!pq.isEmpty()){
            // 循环取出最小键，即权重最小的横切边，
            // 这条边一定属于最小生成树
            Edge e = pq.poll();
            int v = e.either(), w = e.other(v); 
            weight += e.weight();
            // 扫描横切边的另外一个顶点
            if (marked[v]) scan(G, w);
            else scan(G, v);
        }
    }

    private void scan(EdgeWeightedGraph G, int v) {
        // 标记当前顶点为已扫描
        marked[v] = true;
        // 遍历邻接边，找出最小权重横切边
        for (Edge e : G.adj(v)) {
            int w = e.other(v);
            // 如果已经扫描过，则继续遍历其他邻接点
            if (marked[w]) continue;

            // 如果当前横切边比记录的横切边权重小
            // 则更新横切边及其权重
            if (e.weight() < distTo[w]) {
                // 更新权重
                distTo[w] = e.weight();
                // 如果优先队列中包含失效边，则删除
                if (pq.contains(edgeTo[w])){
                    pq.remove(edgeTo[w]);
                }
                // 更新横切边
                edgeTo[w] = e;
                // 这条横切边加入优先队列
                pq.offer(edgeTo[w]);
            }
        }
    }
}