Data Structures Notes

Posted on 2025-01-01 In Notes

数据结构

2024.4.15

第9章查找

动态查找表：在查找的同时对表进行修改操作（增删改）
静态查找表：查找过程不涉及表的操作
平均查找长度（ASL），分为ASL成功与ASL不成功
$$
ASL = \sum_{i=1}^{n} c_i \cdot p_i
$$
$p_i$ 为查找第 i 个元素的的概率，n 为查找表中元素的个数，$c_i$ 为找到第 i 个元素所需的关键字比较次数

顺序查找（线性表）
从表的一段向另外一端逐个查找
顺序查找方法在查找成功时候的平均比较次数约为表长的一半
ASL成功 = (n+1)/2 , ASL不成功 = n ，平均时间复杂度 = O(n)

折半查找（二分查找）不适合链表结构
二分查找的时间复杂度是O(logn)
但是要求必须是有序表（表中元素按关键字是有序的）
查找逻辑如下：
(1) 查找区间[low, high], 中点mid = [(low + high)/2]向下取整，待查找值 k
(2) 若 k = mid_value, 查找成功
(3) 若 k < mid_value, 则该元素在表中 [low, mid - 1] 的区间中, 新查找区间为[low, mid - 1]
(4) 若 k > mid_value, 则该元素在表中 [mid + 1, high] 的区间中, 新查找区间为[mid + 1, high]

def BinSearch(table, table_len, key):
   low = 0
   high = table_len - 1
   mid = 0
   while low <= high:
       mid = (low + high)//2
       if key == table[mid].key:
           return mid
       if key < table[mid].key:
           high = mid - 1
       else: 
           low = mid + 1
   return -1 # 当没有查找到的时候，返回-1，代表未找到

折半查找中关键字的比较次数并不是严格的算法中的关键字比较次数，粗略来说应该是key_value与mid中点的比较次数
ASL平均查找长度 = $log_2(n+1) - 1$ , 时间复杂度$O(log_2n)$
对于ASL成功/不成功的计算，可以通过画出判定树的方式来计算图片描述

索引查找
分块查找
对原表进行分块，要求原表是分块有序的，挑选每一块中最大的值作为索引，构建一个索引表
思路：首先查找索引表，索引表是有序的，可以使用折半查找或顺序查找，确定待查元素的块位置后，对目标块使用顺序查找

树表的查找

二叉排序树（二叉搜索树，binary search tree）
满足左子树所有结点值小于等于根节点值，右子树所有结点值大于等于根节点值
满足上面性质的树，中序遍历的结果是一个递增有序序列
在二叉排序树中进行查找和折半查找比较类似，算法如下

def SearchBST(node, value):
    if(node == null or node.value == value):
        return node
    if(value < node.value):
        node = SearchBST(node.lchild, value) # 小于，在左子树继续查找
    else:
        node = SearchBST(node.rchild, value) # 大于，在右子树继续查找
    return node

在查找过程中，关键字比较的次数不会超过二叉排序树的高度。平均查找长度为$log_2 n$。对于一个二叉排序树，最大节点是根节点右子树的最右结点，最小节点为左子树的最左节点

平衡二叉树（一般指代AVL树）
- 若一个二叉树中每个节点的左右子树的高度最多相差1，则称为平衡二叉树。一颗平衡二叉树总是二叉排序树
- 当向平衡二叉树插入一个新节点后，可能会破坏树的平衡性，因此要进行调整。调整类型有LL型调整，RR型调整，LR型调整，RL型调整。前两种比较类似，后两种比较类似
- 当要在平衡二叉树中删除一个节点的时候，删除的时候同样要进行调整
- 含有 n 个结点的平衡二叉树的平均查找长度为$O(log_2n)$
B-和B+树
- 区别：二叉排序和二叉平衡树都是用作内查找的数据结构，即查找的数据集不大，可以放在内存中，而B+和B-树都是要做外查找的数据结构，其中数据存放在外存中
红黑树

哈希表的查找

对于元素的关键字k，使用一个哈希函数h(k) 把 k 映射为内存单元的下标h(k)
哈希函数选择方法：
- 直接定址法：h(k) = k + c
- 除余留数法：h(k) = k mod p, p <= 哈希表长度m
哈希查找性能与3个元素有关：
- 装填因子Alpha：即为哈希表中已存入的元素数 n 与哈希地址空间大小 m 的比值，alpha = n/m, aplha在0.6~0.9之间较为合适
- 哈希函数
- 哈希冲突
哈希冲突解决方法：
- 开放定址法：在出现哈希冲突的时候，在表中找一个新的位置存放元素。
  - 线性探测法：从发生冲突的地址（下标）开始，探测该地址的下一个位置是否可以进行存放。优点是方法简单，缺点是容易产生堆积问题，即出现哈希数值不同的两个元素争夺同一个地址的现象
  - 平方探测法：发生冲突的地址设为d，则接下来探测位置为d+1^2, d-1^2, d+2^, d-2^2，可以避免出现堆积问题
  - 伪随机序列法，双哈希函数法
- 拉链法：把所有具有相同哈职数值的元素，用单链表链接起来。优点是处理简单，没有堆积现象，空间动态增加，alpha值可大于1，缺点就是占用额外空间

第10章排序

稳定与不稳定的排序算法的区别：若具有相同关键字的元素之间的相对次序发生了变化，则是不稳定的，反之是稳定的
稳定的排序算法：冒泡，直接插入，折半插入，归并，桶排序，基数排序
不稳定的排序算法：快速排序，堆排序，希尔排序，简单选择排序
原地排序的算法（不需要额外存储空间，直接在原始数据存储空间进行排序操作）：冒泡，插入，简单选择，快速，希尔排序(shell)，堆排序

冒泡排序

def bubble_sort(array): # 递增
    array_len = len(array)
    for i in range(array_len):
        for j in range(0, array_len-i-1):
            if(array[j] > array[j+1]):
                array[j], array[j+1] =array[j+1], array[j]

直接插入排序

def insertion_sort(array): # 递增
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key: # array[j] < key 递减版本
            array[j+1] = array[j] # 将元素集中后移
            j -= 1
        array[j+1] = key

折半插入排序

# 递增, 将low = mid+1与high = mid-1调换位置，变为递减版本
def binary_insertion_sort(array): 
    for i in range(1, len(array)):
        key = array[i]
        low, high = 0, i-1
        while low <= high: # 通过二分查找找到合适的插入位置
            mid = (low+high)//2
            if array[mid] < key:
                low = mid+1
            else:
                high = mid-1
        for j in range(i-1, low-1, -1): # 插入元素到合适的位置
            array[j+1] = array[j] # 将元素集中后移
        array[low] = key

快速排序

def quick_sort(array): # 递增，修改left和right的大小号就可以修改为递减
    if len(array) <= 1:
        return array
    
    pivot = array[len(array) // 2] 
    left = [x for x in array if x < pivot]
    middle = [x for x in array if x == pivot]
    right = [x for x in array if x > pivot] 
    return quick_sort(left) + middle + quick_sort(right)

int partition(vector<int>& nums, int l, int r){
    int pivot = nums[r];
    int i = l - 1;
    for(int j = l; j < r; ++j){
        if(nums[j] < pivot){
            ++i;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[r]);
    return i + 1;
}
void quicksort(vector<int>& nums, int l, int r){
    if(l < r){
        int mid = partition(nums, l, r);
        quicksort(nums, l, mid - 1);
        quicksort(nums, mid + 1, r);
    }
}
quicksort(arr, 0, arr.size() - 1);

归并排序(二路归并排序)

def merge_sort(array): # 递增
    if len(array) <= 1:
        return array
    
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]

    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]: # 当修改 <= 为 >= 的时候，就变为递减版本
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

希尔排序

def shell_sort(array): # 递增
    n = len(array)
    gap = n // 2 # 初始化增量序列为数组长度的一半

    while gap > 0:
        for i in range(gap, n):
            temp = array[i]
            j = i
            # 和直接插入排序一样，修改为 < 变为递减版本
            while j >= gap and array[j - gap] > temp: 
                array[j] = array[j - gap]
                j -= gap
            array[j] = temp

        gap //= 2
    
    return array

简单选择排序

def select_sort(array): # 递增
    n = len(array)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if array[j] < array[min_index]: # 修改为 > 即为递减版本
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]

    return array

堆排序

小根堆：父节点的值小于或等于其子节点的值。因此，堆的根节点是整个堆中的最小值。左一为小根根
大根堆：父节点的值大于或等于其子节点的值。因此，堆的根节点是整个堆中的最大值。左二为大根堆

他们都是基于完全二叉树结构的数据结构

      2                 11
    /   \             /   \
   5     7           7     8
  / \   /           / \   /
11   8 9           3   5 2

# 使用最大堆进行排序的时候，为递增；可以修改为使用最小堆，即为递减
# 修改heapify中array[left] > array[largest]和下面类似句子为 < 即为构造最小堆
def heapify(array, n, i):
    largest = i # 初始化最大值为父节点
    left = 2 * i + 1 # 左子节点索引
    right = 2 * i + 2 # 右子节点索引

    
    if left < n and array[left] > array[largest]:
        largest = left # 比较父节点与左子节点，更新最大值索引
    if right < n and array[right] > array[largest]:
        largest = right # 比较父节点与右子节点，更新最大值索引
    if largest != i: # 如果最大值索引不等于父节点索引，则交换父节点与最大值节点
        array[i], array[largest] = array[largest], array[i]
        heapify(array, n, largest) # 递归调用，继续向下调整

def heap_sort(array):
    n = len(array)
    for i in range (n // 2 - 1, -1, -1): # 构建大根堆
        heapify(array, n, i)
    
    # 依次将堆顶元素（最大值）与堆尾元素交换，并重新调整堆
    for i in range(n-1, 0, -1):
        array[i], array[0] = array[0], array[i]
        heapify(array, i, 0)
    
    return array

void heapsort(vector<int>& nums){
    priority_queue<int> que;
    for(auto& num : nums){
        que.push(num);
    }
    int index = 0;
    while(!que.empty()){
        nums[index++] = que.top();
        que.pop();
    }
    return nums;
}

基数排序

def counting_sort(array, exp): # 递增，修改对应语句，即从右往左进行累加，就是递减版本
    n = len(array)
    output = [0] * n 
    count = [0] * 10

    for i in range(n): # 计算每个元素的频率
        index = array[i] // exp
        count[index % 10] += 1 # count[9 - (index % 10)]
    
    for i in range(1, 10): # 将 count 转换为每个数字在 output 中的实际位置
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0: # 构建排序后的数组
        index = array[i] // exp
        output[count[index % 10] - 1] = array[i] # count[9 - (index % 10)]
        count[index % 10] -= 1 # count[9 - (index % 10)]
        i -= 1

    for i in range(n): # 将排序后的数组复制到原始数组
        array[i] = output[i]

def radix_sort(array):
    max_value = max(array)

    exp = 1
    while max_value // exp > 0:
        counting_sort(array, exp)
        exp *= 10
    
    return array

桶排序

def bucket_sort(array): # 递增，动态的根据数组的上下限选择桶的数量，可以修改
    num_buckets = max(array) // 10 - min(array) // 10 + 1
    buckets = [[] for _ in range(num_buckets)]

    for num in array:
        index = (num - min(array)) // 10 # 修改为max(array) - num, 即为递减
        buckets[index].append(num)
    
    for bucket in buckets:
        bucket.sort() # 
    
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

void bucketSort(vector<int>& nums, int bucketCount) {
    if (nums.empty() || bucketCount <= 0) return;
    // 找到数组中的最小值和最大值
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    // 计算每个桶的范围
    double bucketRange = (double)(maxVal - minVal) / bucketCount;
    // 创建桶，使用优先队列（小顶堆）模拟桶
    vector<priority_queue<int, vector<int>, greater<int>>> buckets(bucketCount);
    // 将元素分配到桶中
    for (int num : nums) {
        int bucketIndex = (int)((num - minVal) / bucketRange);
        if (bucketIndex == bucketCount) bucketIndex--; // 边界情况
        buckets[bucketIndex].push(num);
    }
    // 收集排序结果
    nums.clear();
    for (auto& bucket : buckets) {
        while (!bucket.empty()) {
            nums.push_back(bucket.top());
            bucket.pop();
        }
    }
}

排序算法	平均时间复杂度	空间复杂度	稳定性
冒泡排序	O($n^2$)	O(1)	稳定
直接插入排序	O($n^2$)	O(1)	稳定
折半插入排序	O($n^2$)	O(1)	稳定
归并排序	O($nlog_2n$)	O(n)	稳定
桶排序	O($n + k$)	O(n + k)	稳定
基数排序	O($d(n+r)$)	O(r)	稳定
快速排序	O($nlog_2n$)	O($log_2n$)	不稳定
堆排序	O($nlog_2n$)	O(1)	不稳定
希尔排序	O($n^1.3$)	O(1)	不稳定
简单选择排序	O($n^2$)	O(1)	不稳定

备注：基数排序，数据位数 d , 进制为 r

第8章图

图由顶点（vertex）和边（edge）构成，记一张图为 G = (V, E)
有向图：表示边的顶点对是有序的，无向图：表示边的顶点对是无序的。通过边有没有方向来区分
无向图中，一个顶点关联的边的数目成为顶点的度。若为有向图，则分为出度和入度。一个图中所有顶点的度之和等于边数的两倍
完全图：每两个顶点存在一条边（有向图则存在两条边）。无向完全图有 n(n-1)/2 条边，有向完全图有 n(n-1) 条边
无向图中，若任意两点存在一个路径，则为连通图。有向图中，若任意两点存在路径，成为强连通图
图的邻接矩阵存储方法，图的邻接矩阵表示是唯一的
图的邻接表存储方法，对每个顶点建立一个单链表，分为头结点和边结点。邻接表的表示不唯一
图的遍历：分为深度优先遍历（DFS）和广度优先遍历（BFS）

深度优先遍历（DFS）

从一个顶点 v 出发，选择一个与v相邻的且没被访问过的顶点 w 访问，然后对顶点 w 递归进行

def DFS(graph, start, visited=None): # 邻接表存储方法
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')

    for neighbor in graph[start]:
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

对于有 n 个顶点，e 条边的有向图或者无向图，DFS算法对每个顶点最多调用一次，所以递归调用的总次数为 n

邻接表表示图时，总时间为 O(n+e)
邻接矩阵表示图时，为 O(n^2)

广度优先遍历（BFS）

从一个顶点出发，访问该顶点所有未被访问过的邻接点，再按访问的邻接点顺序访问

from collections import deque
def BFS(graph, start): # 邻接表存储方法
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

邻接表表示图时，总时间为 O(n+e)
邻接矩阵表示图时，为 O(n^2)

生成树与算法

生成树（Spanning Tree）是一个连通图的一种特殊子图，它包含图中的所有顶点，并且是一个树结构，即没有包含环路的连通子图
图的所有生成树中具有边上的权值之和最小的树成为图的最小生成树
根据生成树定义，n 个顶点的连通图生成树有 n 个顶点，(n-1) 条边
采用BFS或DFS算法遍历图的时候，就可以得到一颗生成树，分别为广度优先生成树和深度优先生成树

Prim算法

这是一个构造算法，可以基于一个带权的连通图构造最小生成树
prim算法适用于图的邻接矩阵存储方式

时间复杂度为 O(n^2), n 为顶点个数，prim算法执行时间与边个数无关，适合稠密图

def prim(graph):
    num_verticse = len(graph)
    isin_tree = [float('inf')] * num_verticse # 记录点是否在集合里面
    isin_tree[0] = 0
    parent = [None] * num_verticse # 记录每一条边的左端点，后面打印用的
    mst_set = [False] * num_verticse # 记录最小距离的数组

    parent[0] = -1

    for i in range(num_verticse):
        Min = float('inf')
        Min_index = 0
        for j in range(num_verticse):
            if isin_tree[j] < Min and mst_set[j] == False:
                Min = isin_tree[j]
                Min_index = j
        mst_set[Min_index] = True
        # print(f"边({node_set[Min_index]}, {Min_index}), 权为{Min}")
        for j in range(num_verticse):
            if graph[Min_index][j] > 0 and mst_set[j] == False and isin_tree[j] > graph[Min_index][j]:
                isin_tree[j] = graph[Min_index][j]
                parent[j] = Min_index # 多出来的一步，用来记录边的左端点用的

    for i in range(1, num_verticse):
        print(f"边({parent[i]}, {i}), 权为{graph[i][parent[i]]}")

graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
输出：
    边(0, 1), 权为2
    边(1, 2), 权为3
    边(0, 3), 权为6
    边(1, 4), 权为5

void prim(vector<vector<int>>& graph, int v){
    vector<int> min_dist(v + 1, 10001); 
    // 题目中说val最大值是10001，因此设置为10001没问题
    vector<bool> isin_tree(v + 1, false);
    // 只需要进行v-1次循环就可以得到，因为有v个点，那么只需要v-1条边，就可以
    // 把这v个点全部链接起来，每次循环链接一条边，所以只需要循环v-1次
    for(int i = 1; i < v; ++i){
        int cur = -1;
        int min_dist_value = INT_MAX; // 要用INT_MAX，需要#include<climits>
        // 下面这个循环是找到一个距离当前最小生成树距离最短的一个端点
        for(int j = 1; j <= v; ++j){
            if(!isin_tree[j] && min_dist[j] < min_dist_value){
                cur = j;
                min_dist_value = min_dist[j];
            }
        }
        
        isin_tree[cur] = true; // 将上面找到的点(cur)加入路径，在下面循环的时候就不会被找到了
        // 在下面这个循环中，更新min_dist数组
        for(int j = 1; j <= v; ++j){
            if(!isin_tree[j] && graph[cur][j] < min_dist[j] && graph[cur][j] != 0){ // 找不在isin_tree中的点，同时距离还小，同时不等于0（等于0表示没有这条路径）
                min_dist[j] = graph[cur][j];
            }
        }
    }
    // 全部信息保存在min_dist数组中
}

Kruskal算法

按权值递增次数选择合适的边来构造最小生成树的算法
prim和kruskal产生的最小生成树不一定是相同的
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合
稀疏图中，用Kruskal更优。在稠密图中，用prim算法更优
kruskal算法执行时间只与边数e有关，适合稀疏图

时间复杂度为 O(e^2), 改进后可以变为 O($elog_2e$)

edges = [("A", "B", 5), ("A", "G", 7),
         ("B", "F", 1), ("C", "F", 4),
         ("C", "D", 3), ("C", "E", 7),
         ("E", "F", 6), ("D", "E", 4),
         ("E", "G", 12),("F", "G", 12)]
vertices=list('ABCDEFG')
edges.sort(key=lambda x:x[2])
mst = [] # 最小生成树
ori_trees=dict()
for i in vertices:
    ori_trees[i] = i

def find_node(x): # 寻找根节点
    if ori_trees[x] != x:
        ori_trees[x] = find_node(ori_trees[x])
    return ori_trees[x]

n = len(vertices) - 1 # 要添加的边数为顶点数 - 1
for edge in edges:
    v1, v2, weight = edge
    if find_node(v1) != find_node(v2):
        ori_trees[find_node(v2)] = find_node(v1)
        mst.append(edge)
        print(f"添加边({v1}, {v2}), 权为{weight}")
        n-=1
        if n==0:
            break
print("最小生成树为", mst)

// c++版本kruskal算法，需要并查集模板（3个函数，find, isSame, join), 还需要#include<algorithm>
struct edge{
    int l, r, val;
};
void kruskal(vector<edge>& edges, int edge_num, int v){
    int n = v - 1; // 只需要循环v-1次，就能链接v个顶点
    vector<edge> tree; // 保存了最小生成树的每一条边
    for(int i = 0; i < edge_num; ++i){
        if(!isSame(edges[i].l, edges[i].r)){ //两点不在一个集合，可加入
            join(edges[i].l, edges[i].r); // 加入集合
            tree.push_back(edges[i]); // 加入最小生成树
            n -= 1;
            if(n == 0) break; // 循环了v-1次的时候就停止
        }
    }
}
int main(){
    vector<edge> edges;
    for(int i = 0; i < e; ++i){
        cin>>v1>>v2>>value;
        edges.push_back({v1, v2, value});
    }
    
    sort(edges.begin(), edges.end(), [](const edge& a, const edge& b){
        return a.val < b.val;
    }); // 把edge按照从小到大进行排序，lambda表达式实现
    
    kruskal(edges, e, v); // e = edges.size(), v = 顶点个数
}

拓扑排序

给出一个有向图，把这个有向图转成线性的排序，就叫拓扑排序
如果这个有向图中有环，那么就不能做线性排序了
拓扑排序也是图论中判断有向无环图的常用方法

拓扑排序是解决图论中依赖关系的方法

void topology_sort(unordered_map<int,vector<int>>& edges, vector<int>& input_rank, int n){
    vector<int> result; // 记录结果
    queue<int> que; // 队列
    for(int i = 0; i < n; ++i){
        if(input_rank[i] == 0) // 把入度为0的节点全部放入队列
            que.push(i);
    }
    while(que.size() != 0){
        int cur = que.front();
        que.pop();
        // cur这个节点入度为0，下一步要消除cur节点相关的节点的入度
        result.push_back(cur); 
        vector<int> cur_edges = edges[cur]; // 获取cur节点相关的右端点
        if(cur_edges.size()){
            for(int i = 0; i < cur_edges.size(); ++i){
                input_rank[cur_edges[i]]--; // 把cur节点相关的节点入度-1
                if(input_rank[cur_edges[i]] == 0){ // 如果-1后入度为0，那么也放入队列中 
                    que.push(cur_edges[i]);
                }
            }
        }
    }
    if(result.size() != n){
        cout << -1 << endl; // 如果result的数量和图中节点数量不同，那就说明有环了，无法找到入度为0的节点了
        return;
    }
}
int main(){
    vector<int> input_rank(n, 0); // 记录每个节点的入度
    unordered_map<int,vector<int>> edges; // 记录每个节点，以左端点为key，右端点的值放入vector数组中，如<1, [2, 3]>
    for(int i = 0; i < m; ++i){
        input_rank[v2]++;
        edges[v1].push_back(v2);
    }
    topology_sort(edges, input_rank, n);
}

最短路径

Dijkstra算法

不适合含有负权值的带权图进行求解
采用邻接矩阵进行存储的图，或者使用优先队列进行优化的时候，可以使用邻接表

时间复杂度 O(nlogn)

import heapq # 这个版本就是dijkstra的堆优化版本
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # 使用优先队列（堆）来保存待访问的节点和其距离
    pq = [(0, start)]
    while pq:
        # 从优先队列中取出距离最短的节点
        current_distance, current_node = heapq.heappop(pq)
        
        # 如果当前节点已经被访问过，则跳过
        if current_distance > distances[current_node]:
            continue
        
        # 遍历当前节点的邻居节点，并更新其最短距离
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # 如果新的距离比已有距离小，则更新距离字典和优先队列，由于优先队列的性质，push进元素的时候会自动进行调整的
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances
graph = {
    'A': {'B': 5, 'D': 9, 'E': 2},
    'B': {'A': 5, 'C': 2},
    'C': {'B': 2, 'D': 3},
    'D': {'A': 9, 'C': 3, 'F': 2},
    'E': {'A': 2, 'F': 3},
    'F': {'D': 2, 'E': 3}
}

void dijkstra(vector<vector<int>>& graph, int n){
    vector<int> min_dist(n + 1, INT_MAX); // 记录每个节点到节点0的最短距离
    vector<bool> visited(n + 1, false); // 记录已经被访问的结点
    min_dist[1] = 0; // 初始化第一个节点距离为0
    for(int i = 1; i < n + 1; ++i){
        int cur = 1;
        int min_distance = INT_MAX;
        for(int j = 1; j < n + 1; ++j){ // 找到一个没访问过的节点，同时离节点0距离最短的一个结点
            if(visited[j] != true && min_dist[j] < min_distance){
                cur = j;
                min_distance = min_dist[j];
            }
        }
        visited[cur] = true; // 标记cur结点已访问
        for(int j = 1; j < n + 1; ++j){
            if(graph[cur][j] != 0 && visited[j] == false && min_dist[cur] + graph[cur][j] < min_dist[j]){
                min_dist[j] = min_dist[cur] + graph[cur][j];
                // 更新min_dist数组
            }
        }
    }
    // 所有结点到结点0的最短距离都保存在min_dist数组中
}

vector<int> dijkstra(int n, int source, vector<vector<pair<int, int>>>& graph) {
    vector<int> dist(n, INT_MAX); // 存储从源点到各点的最短距离
    dist[source] = 0;            // 起点到自身距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 最小堆
    pq.emplace(0, source);       // {当前最短距离, 节点编号}
    while (!pq.empty()) {
        auto [cur_dist, u] = pq.top(); pq.pop();

        if (cur_dist > dist[u]) continue; // 如果当前距离已经不是最优解，跳过

        for (const auto& [v, weight] : graph[u]) { // 遍历所有邻居
            if (dist[u] + weight < dist[v]) { // 如果从 u 到 v 的距离更短，更新距离
                dist[v] = dist[u] + weight;
                pq.emplace(dist[v], v); // 把新的最短距离和节点加入优先队列
            }
        }
    }
}

Bellman-ford算法

可以针对带负权值问题

循环n-1次，每一次循环，都对每一条边做了一次松弛操作

// edges储存所有的边
void bellman_ford(vector<vector<int>>& edges, int n){
    vector<int> min_dist(n + 1, INT_MAX); // 所有的路径信息储存在min_dist数组中
    min_dist[1] = 0;
    int v1,v2,val;
    for(int i = 1; i < n; ++i){
        for(vector<int>& edge:edges){
            v1 = edge[0];
            v2 = edge[1];
            val = edge[2];
            if(min_dist[v1] != INT_MAX && min_dist[v2] > min_dist[v1] + val){
                min_dist[v2] = min_dist[v1] + val; // 松弛操作
            }
        }
    }
}

SPFA算法

对于bellman-ford算法，在每一次循环的松弛过程中，做了很多次不会进行的松弛操作，因此SPFA就是针对这一点应运而生

SPFA算法的松弛过程如下：维护一个队列，只对上一次松弛的时候更新过的节点作为出发节点所连接的边，进行松弛。

vector<list<edge>> graph; // 使用了vector,list,自定义数据结构edge
queue<int> que; // 部分核心代码，主要使用队列就可以
que.push(1);
while (!que.empty()) {
    int node = que.front(); que.pop();
    isInQueue[node] = false; // 从队列里取出的时候，要取消标记，我们只保证已经在队列里的元素不用重复加入
    for (Edge edge : grid[node]) {
        int from = node;
        int to = edge.to;
        int value = edge.val;
        if (minDist[to] > minDist[from] + value) { // 开始松弛
            minDist[to] = minDist[from] + value; 
            if (isInQueue[to] == false) { // 已经在队列里的元素不用重复添加
                que.push(to);
                isInQueue[to] = true;
            }
        }
    }
}

特殊情况：如果存在一个环，同时这个环所有的边的权值都是负的，就称为一个负权回路。负权回路会导致无解的情况，因为只要一直在这个环中循环，就可以得到无限小的路径长度
解决方法：
- 对于bellman-ford算法，只需要松弛n-1次就可以得到结果，如果没有负权回路，那么无论再松弛多少次，min_dist数组不会变。如果有负权回路，min_dist数组会一直变，可以在做完n-1循环后，再做一次松弛查看是否变化。
- 对于SPFA算法：如没有负权回路，每个节点最多加入队列n-1次，如果有节点加入队列超过n-1次，那就说明有负权回路

Floyd算法

时间复杂度 O(V^3), V为节点个数
可以处理负权值的带权有向图，是一个求多个起点多个终点之间最短路径的算法
维护两个数组，distance数组和path数组，distance数组表示点之间的距离，path数组表示点之间的路径，Path数组中，若Path[0][2] = 3，代表2节点的前一个节点是3，若Path[0][3] = 0, 则代表已经找到了起点，这条路径是 0 -> 3 -> 2, 再到distance[0][2]读取出最短路径

主要的过程，对于图中所有的点，逐个进行遍历。比如，当进行到A点的时候，将A作为中转站，比如原来BD的路径，则计算AB + BD之间路径的长度，如果更小，则更新distance数组与path数组，逐个进行，可以得到有向图中所有点之间相互的最短距离

def floyd(graph):
    # 初始化距离矩阵
    n = len(graph) # n为图中结点个数
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif j in graph[i]:
                dist[i][j] = graph[i][j]

    # Floyd 算法核心部分
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist
graph = {
    0: {1: 5, 2: 9, 4: 2},
    1: {0: 5, 2: 2, 3: 7},
    2: {0: 9, 1: 2, 3: 4, 4: 6},
    3: {1: 7, 2: 4, 4: 8},
    4: {0: 2, 2: 6, 3: 8}
}

// dist数组为两个点的距离，最后的结果也保存在dist数组中
void floyd(vector<vector<int>>& dist, int n, vector<vector<int>>& target, int m){
    for(int k = 1; k < n + 1; ++k){ // k就是中转节点
        for(int i = 1; i < n + 1; ++i){ // 左端点
            for(int j = 1; j < n + 1; ++j){ // 右端点
                if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX){
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                } // i是左，j是右，k是中转
            }     // 所以才要判断ik, kj是不是有路径，若有比最小
        }
    }
}

Astar算法

是一种BFS的改良版本，主要用到了启发式函数，适合无权图(或权全为1的图)，是一种搜索最短路径的方法
由于是启发式算法，结果不一定是最短路径，同时结果也不唯一
主要用到3种启发式函数，优先队列（用于排序）
- x1,y1为起点，x2,y2为终点
- 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
- 欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
- 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
利用这些来计算每个节点的权值，放到优先队列里面，就能保证每次出队列的是最合适的下一个节点了

时间复杂度大概为O(nlogn), n为节点数量

struct Knight{ // 自定义数据结构，定义了优先队列的排序顺序
    int x,y;
    int g,h,f; // f是主要权值，f = g + h
    bool operator < (const Knight & k) const{  // 重载运算符， 从小到大排序
     return k.f < f;
    }
};
void astar(const Knight& k)
{
    Knight cur, next;
	que.push(k);
	while(!que.empty())
	{
		cur=que.top(); que.pop();
		if(cur.x == b1 && cur.y == b2)
		break;
		for(int i = 0; i < 8; i++)
		{
			next.x = cur.x + dir[i][0];
			next.y = cur.y + dir[i][1];
			if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
			continue;
			if(!moves[next.x][next.y]) // next这个点没有被访问过
			{
				moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
                // 开始计算F
				next.g = cur.g + 5; // 统一不开根号，这样可以提高精度
                next.h = Heuristic(next);
                next.f = next.g + next.h;
                que.push(next);
			}
		}
	}
}

串

分为目标串(traget string), 模式串(pattern string), 在目标串中找到模式串

Brute-Force算法

重复进行搜索即可，时间复杂度为 O(nm), n 为模式串程度，m 为目标串程度

KMP算法

计算next数组的串是模式串，在里面找的串是目标串
分为两部分，next数组和搜索过程。首先根据模式串计算出next数组，然后进行搜索
消除了主串指针的回溯
next数组：
从模式串的第i位开始，对str[0:i]的头部和尾部求最长公共部分，比如abcabaa这个串，它的next数组是{0, 0, 0, 1, 2, 1, 1}
在搜索过程中，有两个指针，i 和 j，i 为目标串的指针，j 为模式串的指针，当发生失配（匹配失败）的时候，i 不变，将 j 赋值为 next[j] 进行更新，重复这个过程。i指针始终向前，而j指针通过Next数组控制回溯和跳转
时间复杂度为 O(n+m)

树

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数
- 一棵深度（按根节点深度为1）为k的二叉树最多可以有 2^k - 1 个节点
二叉排序树，平衡二叉排序树(AVL)，二叉搜索树相关的算法在45行
二叉排序树：插入节点后一定是叶子结点，不需要调整

平衡二叉排序树：左右两个子树之间的高度差不大于1，插入节点后需要调整

可以通过一个有序数组来构建一个平衡二叉排序树

# nums是一个递增的数组, left = 0, right = len(nums) - 1
def build(self, nums, left, right):
  if left > right:
      return None
  
  mid = left + ((right - left) // 2) # 二分法也可以这么写，防止数组越界
  root = TreeNode(nums[mid]) # 选择数组中心的点来进行创建，将当前数组分割为左右两个数组
  # 注意分割后的数组区间
  root.left = self.build(nums, left, mid - 1)
  root.right = self.build(nums, mid + 1, right)
  return root

二叉搜索树 = 二叉排序树 = 二叉查找树 = BST
- BST的中序遍历结果是一个递增的序列
- BST的反中序遍历的结果是一个递减的序列
- 左子树节点小于父节点，右子树节点大于父节点(不能是大于等于或者是小于等于)

二叉树的公共祖先问题：即对于一个节点，若是左子树出现节点p，右子树出现节点q，则该节点为p和q的公共祖先

def find(root, p, q):
  if root == None or root == p or root == q:
      return root
  
  node1 = find()
  node2 = find()
  # 如果node1和node2不为空，返回root
  # 如果node1和node2之间有个为空，返回不为空的那个
  # 都为空，返回None

深度优先遍历：
- 先序遍历：先访问根节点，然后左子树，然后右子树
- 中序遍历：先访问左子树，然后根节点，然后右子树
- 后序遍历：先访问左子树，然后右子树，然后根节点(带有回溯特征，即可以根据左右子树的返回结果来进行一些操作)
- 上面这三种遍历主要使用递归的方式进行，当然也可以使用栈对递归进行模拟，修改为迭代的形式

广度优先遍历：

层次遍历：先访问根节点，然后从上到下从左到右进行访问

一般使用队列来进行实现，由于队列先进先出的特点，可以实现一层一层的遍历二叉树

import collections # 十分重要！
queue = collections.deque([root]) # 直接使用队列
result = []
while queue:
  level = []
  for _ in range(len(queue)):
      cur = queue.popleft()
      result.append(cur.val)
      if cur.left:
          queue.append(cur.left)
      if cur.right:
          queue.append(cur.right)
  result.append(level)

def order_0(node): # 递归版本
    print(node.value) # 先序遍历
    order(node.lchild)
    order(node.rchild)

def order_1(node): # 非递归版本，使用栈
# 将根节点进栈
# while(栈不空)：
# 出栈一个节点p，访问打印信息
# 若该节点p有右子节点，进栈p.rchild
# 若该节点p有左子结点，进栈p.lchild
stack.push(node)
ans = []
while(stack.empty() == false):
    curr_node = stack.pop()
    ans.append(curr_node.val)
    if(curr_node.right != null): stack.push(curr_node.right)
    if(curr_node.left != null): stack.push(curr_node.left)
# 若层次遍历，则使用队列，基本原理一样，队列先进先出

可以通过前序(preorder)+中序(inorder)或者后序(postorder)+中序来建立一棵树

class Solution(object):
  def traversal(self, in_order, post_order):
      if len(post_order) == 0:
          return None
      
      index = in_order.index(post_order[-1])
      root = TreeNode(post_order[-1])

      if len(post_order) == 1:
          return root
      
      left_inorder = in_order[:index]
      right_inorder = in_order[index + 1:]

      left_postorder = post_order[:len(left_inorder)]
      right_postorder = post_order[len(left_inorder):len(left_inorder) + len(right_inorder)]

      root.left = self.traversal(left_inorder, left_postorder)
      root.right = self.traversal(right_inorder, right_postorder)
      
      return root

  def buildTree(self, inorder, postorder):
      """
      :type inorder: List[int]
      :type postorder: List[int]
      :rtype: TreeNode
      """
      if(len(inorder) == 0 or len(postorder) == 0):
          return None
      return self.traversal(inorder, postorder)

合并两棵树：使用各种遍历方法都可以

def merge(self, root1, root2):
  if root1 is None:
      return root2
  if root2 is None:
      return root1
  
  root1.val += root2.val
  root1.left = self.merge(root1.left, root2.left)
  root1.right = self.merge(root1.right, root2.right)
  return root1

并查集操作(Union find)

需要经常使用查找，合并集合的操作，可以使用树的方法来实现并查集。
用有根树来表示集合，树中每一个节点表示集合的一个元素，每一颗树表示一个集合，所有的树构成一根森林
在合并两棵树的时候，可以让树高度较小的树成为树高度较大树的子树，这样就能实现比较平衡的树
在树中，每个节点都存在一个父亲节点，可以定义父亲节点为自己的节点为根节点，也代表了这棵树，代表了一个集合
主要定义三个操作：Find(type x)和Union(type x, type y)和isSame(type x, type y), 分为查找元素，合并元素，判断2个元素是否是同一个集合
路径压缩：当查找到根节点后，沿着路径改变所有节点的父指针，使其全部指向根节点。意思是比如2是根节点，4->3->5->2, 在2这个集合里面有3,4,5三个元素，经过路径压缩后，就会变成：4->2, 3->2, 5->2，这样子就会减少查找的深度

并查集find，join操作的时间复杂度是$O(\alpha(N))$, $\alpha(N)$是反阿克曼函数，几乎是常数，所以find和join操作时间复杂度可以看为是O(1)，而初始化时间复杂度是O(N)

// c++ 并查集模板
int n = 1005; // 长度根据题目中节点数量而定
vector<int> father; // C++里的一种数组结构
// 并查集初始化，全部初始化为自身
void init(int n): father(n) {
    for (int i = 0; i < n; ++i) {
        father[i] = i; 
    }
}
// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return father[u] = find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找。在查询的过程中会自动进行路径压缩，减小下一次查询的开销
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u; // 代表v的根是u，u -> v
}

三元组操作

可以储存稀疏矩阵，以一个n * m的矩阵为例，假设存储的是int类型的数据，共存储10个
以（行，列，数据）的方式存储一个数据，一个数据消耗6个字节，同时，另外需要6个字节来存储数组的行数，列数，数据个数
所以存储10个数据一共需要60+6=66个字节

栈

设序列进栈顺序为x1, x2, x3,…, 有多少种出栈顺序？
可能的结果有1, 2, 5, 14, 42, 132, 429, 对应元素个数为1,2,3,4,5,6,7

队列

可以使用2个栈来模拟一个队列，一个instack，一个outstack。当push数据，直接push到instack中。当pop或者top数据的时候，如果outstack为空，把instack所有数据取出并压入outstack，然后再从outstack中取数据

B+树/B树

B树（B-Tree）是一种自平衡的多叉搜索树，主要用于数据库和文件系统中，以加快数据的读写速度。它的特点是：
- 多叉节点：每个节点可以包含多个键和多个子节点，而不是像二叉树那样仅包含两个子节点。
- 节点间有序性：每个节点的键按照大小排序，子节点按顺序放置在相应的键之间。
- 平衡性：B树始终保持平衡，即从根到叶子的路径长度相同，避免了长链表状的单边增长。
- 可配置的阶数：阶数（即每个节点的子节点数）可以根据需求设置，以调整树的分支数量和高度。
  B树的这种结构让它能有效地减少磁盘IO操作，因为节点较少，访问特定数据时可以跳过大部分无关数据。B树在写入和删除数据时，会通过分裂和合并节点来保持平衡
B+树（B+ Tree）是B树的一种变体，改进了数据的存储方式，进一步提高了数据的查找效率。B+树在B树的基础上增加了以下特点：
- 所有数据存储在叶子节点：B+树的非叶子节点只存储键而不存储数据，所有数据都保存在叶子节点中。这样可以让树的内部节点更轻量，增加分支因子，从而降低树的高度。
- 叶子节点间的链表结构：B+树的叶子节点通过指针相连，形成一个有序的链表。这样在范围查找时，可以从起始叶子节点顺序访问，速度更快。每个叶子节点有两个指针，指向下一个和上一个叶子节点，形成一个双向链表
- 查询速度更稳定：由于数据都存储在同一层的叶子节点上，B+树的查询效率更加稳定。
  B+树的结构非常适合范围查询等操作，数据的顺序性和叶子节点的链接，使得区间查找在B+树中只需进行一次磁盘扫描。

红黑树（Red-Black Tree）

节点颜色：每个节点都被着色为红色或黑色。
根节点：根节点始终是黑色的。
叶节点：所有叶节点（NIL节点）都是黑色的。
红色节点的限制：红色节点不能连续出现，即一个红色节点的子节点必须是黑色。
黑色平衡：从任何一个节点到其所有子孙叶节点的路径上，必须包含相同数量的黑色节点。
插入后可能需要通过重新着色和旋转来保持红黑树的性质。
查找、插入、删除操作的时间复杂度：O(logn)，其中n为树中的节点数。
与AVL树的比较：红黑树比AVL树稍微简单一些，因为它不要求每个节点的平衡因子严格为-1、0或1，而是要求红黑性质，但保持平衡的代价较小。
与普通二叉查找树的比较：普通二叉查找树的最坏时间复杂度为O(n)，而红黑树保证了最坏情况下的时间复杂度为O(log n)。