树

注意看二叉树的存储表示、先序遍历、中序遍历、后序遍历，知道递归描述即可。

一般 Leetcode 对于树的结构表示都是这样的：

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

# 06 树

## 01 二叉树的存储结构

### 顺序存储表示
```c
#define MAX_TREE_SIZE 100;                     // 二叉树最大节点数
typedef TElemtype SqBiTree[MAX_TREE_SIZE];     // 0号单元存储根节点
SqBiTree bt;

链式存储表示

二叉链表

typedef struct BiTNode {                // 结点结构
    TElemType           data;
    struct BiTNode      *lchild, *rchild;    // 左右孩子指针
} BiTNode, *BiTree;

三叉链表

typedef struct TriTNode {                // 结点结构
    TElemType           data;
    struct TriTNode     *lchild, *rchild;    // 左右孩子指针
    struct TriTNode     *parent;             // 双亲指针
 } TriTNode, *TriTree;

双亲链表

typedef struct BPTNode {
    TElemType           data;
    int                 parent;        // 指向双亲的指针 意思是int *parent
    char                LRTag;         // 左、右孩子标志域
} BPTNode;

typedef struct BPTree {
    // 使用数组存储，可以找到下标
    BPTNode             nodes[MAX_TREE_SIZE];
    int                 num_node;
    int                 root;
} BPTree;

线索链表

typedef enum {
    Link,       // 指针
    Thread      // 线索
} PointerThr;

typedef struct BiThrNod {
    TElemType            data;
    struct BiThrNod     *lChild, *rChild;
    PointerThr           LTag, RTag;
} BiThrNode;

02 二叉树的遍历

三种遍历方式

先序遍历：根-左-右
中序遍历：左-根-右
后序遍历：左-右-根

普通树算法的递归描述

以下为先序遍历算法的递归描述（伪代码）

void PreOrder (BiTree T, void(*visit)(TElemType& e)){
    if (T){                             // 树非空
        visit (T->data);                // 访问节点
        PreOrder (T->LChild, visit);    // 遍历左子树
        PreOrder (T->RChild, visit);    // 遍历右子树
    }
}

普通树中序遍历算法的非递归描述（略）

03 遍历算法的应用

统计叶子节点的个数：先序遍历

void CountLeaf (BiTree T, int& count){
    if(T){
        // 叶子节点计数
        if ((!T->LChild) && (!T->RChild)) count ++;
        CountLeaf (T->LChild, count);
        CountLeaf (T->RChild, count);
    }
}

求二叉树的深度：后序遍历

int Depth (BiTree T){
    if (T) return max (Depth (T->LChild), Depth (T->RChild)) + 1;
    else return 0;
}

复制二叉树：后序遍历

// 生成一个二叉树的结点
BiTNode *GetTreeNode (TElemType item, BiTNode *lPtr, BiTNode *rPtr) {
    BiTNode *node = (BiTNode*) malloc (sizeof(BiTNode));
    node->data = item;
    node->lChild = lPtr;
    node->rChild = rPtr;
    return node;
}

BiTNode *CopyTree (BiTNode *T) {
    if (T) return GetTreeNode (T->data, CopyTree (T->lChild), CopyTree (T->rChild));
    else return NULL;
}

建立二叉树存储结构

以字符串形式“根左子树右子树”定义一棵二叉树：先序遍历

如输入字符串“A B # C # # D # #”

Status CreateBiTree (BiTree &T) {
    char ch; cin >> ch;
    if(ch == '#')  T = NULL;
    else {
        T = (BiTNode*) malloc (sizeof(BiTNode));      // 省略开空间失败的情况
        T->data = ch;
        CreateBiTree(T->lChild);
        CreateBiTree(T->rChild);
    }
    return OK;
}

由先缀表示式建树

例如：已知表达式的先缀表示式 - × + a b c / d e
特点：操作数为叶子结点运算符为分支结点
基本操作：

cin >> ch;
if (In (ch, 字母集)) 建立叶子节点;
else {
    建立根节点;
    递归建立左子树;
    递归建立右子树;
}

由原表示式建树

例如：已知表达式 (a+b)×c–d/e

cin >> ch;
if (In (ch, 字母集)) {
    建立叶子节点;
    暂存;
}
else if (In (ch, 运算符集)) {
    if (priority[ch] > priority[前一个运算符]) 暂存;
    else 建立子树;
}

由二叉树的先序和中序序列建树

下文 pre[]为先序序列， ino[]为中序序列；省略开空间的错误判断

int ps = 0, is = 0；              // 双指针
int n = strlen(pre);              // 序列长度

void CreateBiTree (BiTree& T, char pre[], char ino[], int ps, int is, int n) {
    int k = Search (ino, pre[ps]);     // 搜索指针,中序序列中查询
    if (n == 0 || k == -1) {
        T = NULL; return;
    }
    T = (BiTNode *) malloc (sizeof(BiTNode));
    T->data = pre[ps];
    CreateBiTree (T->LChild, pre, ino, ps + 1,              is,         k - is          );
    CreateBiTree (T->RChild, pre, ino, ps + 1 + (k - is),   k + 1,      n - (k - is) - 1);
}

CreateBiTree (T, pre, ino, 0, 0, strlen(pre));

二叉树的层次遍历

Status LevelOrderTraverse (BiTree T){
    Queue Q; InitQueue(Q);
    if (T) Enqueue (Q, T);
    while (!QueueEmpty(Q)) {
        Dequeue (Q, &E); visit(E);              // 出队一个结点并访问
        if (E->lChild) Enqueue (Q, E->lChild);
        if (E->rChild) EnQueue (Q, E->rChild);
    }
}

04 线索二叉树

线索链表数据结构

typedef enum {
    Link   = 0,       // 指针
    Thread = 1        // 线索
} PointerThr;

typedef struct BiThrNod {
    TElemType            data;
    struct BiThrNod     *lChild, *rChild;
    PointerThr           LTag, RTag;
} BiThrNode;

对以T为根的非空二叉树进行线索化

以下为中序遍历；ROOT结点是“头节点”
在二叉树存在的基础上，只建立“线索”

BiThrTree preT = ROOT;               // 指向刚才访问过的结点，一开始指向“ROOT”结点
void InThreading (BiThrTree T) {
    if (T) {
        InThreading (T->lChild);
        // 建立该结点的前驱线索
        if (!T->lChild) {
            T->LTag         = Thread;
            T->lChild       = preT;
        }
        // 建立上一个节点的后继线索
        if (!preT->rChild) {
            preT->RTag      = Thread;
            preT->rChild    = T;
        }
        // 将上一个结点更新为当前节点
        preT = T;
        InThreading (T->rChild);
    }
    else return;
}

构建中序线索链表

Thrt就是我们所说的ROOT结点的指针

Status InOrderThreading (BiThrTree &Thrt, BiThrTree T) {
    Thrt = (BiThrTree) malloc (sizeof(BiThrNode));
    Thrt->LTag = Link;
    Thrt->RTag = Thread;
    Thrt->rChild = Thrt;    // 右指针回指

    if (!T) {
        Thrt->lChild = Thrt;
        return OK;
    }

    Thrt->lChild = T;
    preT = Thrt;

    InThreading(T);

    preT->rChild = Thrt;
    preT->RTag = Thread;
    Thrt->rChild = preT;
}

对中序线索化链表的遍历算法

中序遍历的第一个结点？

左子树上处于“最左下”（没有左子树）的结点。

在中序线索化链表中结点的后继？

若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。

void InOrderTraverse_Thr (BiThrTree T, void (*visit) (TElemType e)) {
    BiThrTree p = T->lChild;    // p指向根结点
    while (p != T) {            // 空树或遍历结束时，p==T
        while (p->LTag == Link) p = p->lChild;  // 第一个结点
        visit (p->data);
        while (p->RTag == Thread && p->rChild != T){
            // 指向后继
            p = p->rChild;
            visit (p->data);
        }
        // 指向右子树
        p = p->rChild;
    }
}

05 树的存储结构

双亲表示法

#define MAX_TREE_SIZE 100
typedef struct PTNode {
    Elem data;
    int parent; // 双亲位置域
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;  // 根结点的位置和结点个数
} PTree;

孩子链表表示法

typedef struct CTNode {
    int child;
    struct CTNode *next;
} *ChildPtr;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;  // 结点数和根结点的位置
 } CTree;

树的二叉链表（孩子-兄弟）存储表示法

左边是孩子，右边是兄弟

typedef struct CSNode{
    Elem data;
    struct CSNode  *firstchild, *nextsibling;
} CSNode, *CSTree;

树和森林与二叉树的相互转换（很重要）

树和森林与二叉树的相互转换

06 树和森林的遍历

07 树和森林遍历算法的应用

设树的存储结构为孩子兄弟链表

typedef struct CSNode{
    Elem data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

求树的深度

int TreeDepth (CSTree T) {
    if (!T) return 0;
    else {
        h1 = TreeDepth (T->firstChild);
        h2 = TreeDepth (T->nextSibling);
        return max(h1 + 1, h2);
    }
}

08 哈夫曼树与哈夫曼编码


# 搜索与回溯

```markdown
## 概述
DFS：深度优先搜索（Depth-First-Search）

BFS：宽度优先搜索（Breadth-First-Search）

DFS和BFS的对比
DFS使用栈（stack）来实现，BFS使用队列（queue）来实现

DFS所需要的空间是树的高度 $h$，
而BFS需要的空间是 $2^h$ （DFS的空间复杂度较低）

DFS不具有最短路的特性，BFS具有最短路的特性

## DFS
DFS中的2个重要概念：
- 回溯：回溯的时候，一定要记得恢复现场
- 剪枝：提前判断某个分支一定不合法，直接剪掉该分支

重要思路：
- 遍历
- 顺序

### 842. 排列数字
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

##### 输入格式
共一行，包含一个整数 n。

##### 输出格式
按字典序输出所有排列方案，每个方案占一行。

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
int n;
int path[N];
bool st[N];

void dfs(int u){
    if(u == n){
        for(int i = 0;i < n;i++){
            printf("%d ",path[i]);
        }
        puts("");
        return;
    }
    
    for (int i = 1; i <= n; i ++ ){
        if(!st[i]){
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            // 恢复现场
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    
    return 0;
}

843. n-皇后问题

n− 皇后问题是指将 n 个皇后放在 $n×n$ 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n ，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n 。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围 $1≤n≤9$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;

int n;
bool col[N], dg[N], udg[N];
char g[N][N];

void dfs(int u){
    if(u == n){
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }
    
    for (int i = 0; i < n; i ++ ){
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u+i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    for (int j = 0; j < n; j ++ )g[i][j] = '.';
    dfs(0);
    return 0;
}

BFS

适应问题：求最短路

queue ← 初始
while(queue不空){
    t ← 队头
    拓展 t
}

844. 走迷宫

给定一个 $n×m$ 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1 ，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角$ (n,m)$ 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0 ，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m 。

接下来 n 行，每行包含 m 个整数$（0$ 或 $1$），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

$1≤n,m≤100$

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

const int N = 110;

typedef pair<int, int> PII;
int n, m;
int g[N][N];//地图
int d[N][N];//每一个点到起点的距离o
// 自己手动模拟队列：存入路径中经过所有的点
PII q[N * N];

int bfs(){
    // 队头hh 队尾tt (已经有第一个点)
    int hh = 0, tt = 0;
    // 从(0 ,0)点出发
    q[0] = {0,0};
    // 将距离初始化为 -1 
    memset(d, -1, sizeof d);
    // (0, 0)点距离为 0
    d[0][0] = 0;
    // 上下左右 4个向量
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while(hh <= tt){
        // 队列弹出，获取下一个要处理的点
        auto t = q[hh++];
        
        for (int i = 0; i < 4; i ++ ){
            int x = t.first + dx[i] , y = t.second + dy[i];
            // 判断试探的该方向是否可到达
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                // 存入这个点到起点的距离
                d[x][y] = d[t.first][t.second] + 1;
                // 队列存入，之后处理该点
                q[++tt] = {x, y};
            }
        }
    }
    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;
    // 读入地图
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            cin >> g[i][j];
        }
    }
    cout << bfs() << endl;
}

树和图的深度优先遍历

树是一种特殊的图，无向图是一种双向的有向图

因此我们只需要表示有向图就ok了

有向图有两种表示方法，边数为m，顶点数n

邻接矩阵空间复杂度 $O(n^2)$ 多用于稠密图
邻接表空间复杂度 $O(n+m)$ 多用于稀疏图

邻接表表示

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010 , M = N * 2;// M 存边数

int n ,m;
// 树和图的问题：邻接表
// 邻接表不带权
// h[N] 遍历每一个结点，邻接表的head指针
// e[M] 存链表值 ne[M] 存链表指针 idx存当前使用的e[idx]下标
int h[N], e[M], ne[M], idx;
// 哪些点被遍历过了
bool st[N];

// 插入一条边
void add(int a, int b)  // 添加一条边a->b
{
    // 赋值 赋指针 idx++
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u){
    st[u] = true; //标记：已经被搜过了
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]) dfs(j);
    }
}

int main()
{
    // 将邻接表的头全部初始化为 -1
    memset(h, -1, sizeof h);
    dfs(1);
}

树和图的宽度优先遍历

queue ← 初始
while(queue不空){
    t ← 队头
    拓展 t 的所有邻点
    if (x 未遍历) queue ← x
    d[x] = d[t] + 1
}

847. 图中点的层次

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1 ，点的编号为 1∼n 。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1 。

输入格式第一行包含两个整数 n 和 m 。

接下来 m 行，每行包含两个整数 a 和 b ，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围

$1≤n,m≤105$

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

const int N = 100010, M = N;

int h[N], e[M], ne[M], idx;
int n , m;
int d[N] , q[N];
void add(int a, int b){
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

int bfs(){
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t] ; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i ++ ){
        int a ,b;
        cin >> a >> b;
        add(a, b);
    }
    
    
    
    cout << bfs() << endl;
    
    return 0;
    
}

有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n ，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1 。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 $(x,y)$ ，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n和 m。

接下来 m行，每行包含两个整数 x和 y，表示存在一条从点 x到点 y的有向边 $(x,y)$。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1 。

数据范围 $1≤n,m≤105$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 , M = N;

int n,m;
int h[N], e[M], ne[M], idx;
int q[N],d[N];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 模板
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
    // 队列存入所有入度为0的点
        if (!d[i])
            q[++tt] = i;

    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            // 断掉来的那条路 减少入度 d[j]--
            // 入度为 0 时，存
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ){
        int a ,b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }
    if(topsort()){
        for(auto item: q){
            if(item == 0)break;
            cout << item << " ";
        }
    }
    else puts("-1");
    return 0;
}


```markdown
# 最短路
给定一张有权图，如何求某两点之间的最短路径？
## 知识结构

单源最短路 所有边权均为正数
- 朴素dijsktra算法 $O(n^2)$
- 堆优化dijsktra算法 $O(mlog(n))$

单源最短路 存在负权边
- Bellman-Ford $O(nm)$
- SPFA 一般 $O(m)$ 最坏 $O(nm)$

多源汇最短路
- Floyd 算法 $O(n^3)$

## 朴素dijkstra
$O(n^2)$ 稠密图

第一步 // s[]:当前已确定最短距离的点 // dis[]: 所有点到起点的距离 // 初始化： dis[1] = 0, dis[i] = +∞ 第二步 for(int i = 0; i < n; i++) t ← 不在s[]中距离最近的点 s[] ← t 用t更新其它点的距离

给定一个 n
 个点 m
 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1
 号点到 n
 号点的最短距离，如果无法从 1
 号点走到 n
 号点，则输出 −1
。

#### 输入格式
第一行包含整数 n
 和 m
。

接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y
 的有向边，边长为 z
。

#### 输出格式
输出一个整数，表示 1号点到 n号点的最短距离。

如果路径不存在，则输出 −1。

#### 数据范围
1≤n≤500
,
1≤m≤105
,
图中涉及边长均不超过10000。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510;

// 稠密图用邻接矩阵
int n,m;
int g[N][N];
// 当前最短距离
int dist[N];
// 已经确定过最短距离的点
bool st[N];

int dijkstra()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    // 初始化：dis[1] = 0, dis[i] = +∞
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
        // 所有距离未确定的点当中 找到dist最小的点
           if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 该t点已确定过最短距离
        st[t] = true;
        // 用t点更新其它点距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j] ,dist[t] + g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
    
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g , 0x3f, sizeof g);
    while (m -- ){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b] , c);
    }
    
    printf("%d\\n",dijkstra());
    return 0;
}

堆优化dijkstra

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1 。

输入格式第一行包含整数 n 和 m 。

接下来 m 行每行包含三个整数 x,y,z ，表示存在一条从点 x 到点 y 的有向边，边长为 z 。

输出格式输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1 。

数据范围 $1≤n,m≤1.5×10^5$ , 图中涉及边长均不小于 0 ，且不超过 10000 。数据保证：如果最短路存在，则最短路的长度不超过 109 。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510 , M = N;

typedef pair<int, int> PII;

int n,m;
// 稀疏图用带权重的邻接表
int h[N], e[M], w[M], ne[M], idx;
// 当前最短距离
int dist[N];
// 已经确定过最短距离的点
bool st[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    // 由于优先队列没有下标 堆里需要存一个pair 存距离和编号
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    // 将1号点放入
    heap.push({0, 1});

    while (heap.size())
    {
        // 找到堆中距离最小的点
        auto t = heap.top();
        heap.pop();

        // ver表示点的编号
        int ver = t.second, distance = t.first;

        // 如果t曾经出来过，说明是冗余备份，直接continue
        if (st[ver]) continue;
        st[ver] = true;
        // 遍历ver结点为头节点的链表，更新最短距离
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- ){i
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
    }
    
    printf("%d\\n",dijkstra());
    return 0;
}

Bellman-Ford算法

for n次
    备份
    for 所有边 a---(w)--->b
        dist[b] = min (dist[b], dist[a] + w) // 松弛操作

循环之后一定满足，对于所有的点，满足 $$dist[b] ≤ dist[a] + w（三角不等式）$$
若有负权回路，最短路径不一定存在。
如果有边数限制，那么一定用Bellman-Floyd
存边方式：用结构体struct即可
备份：避免在遍历所有边时串联，更新时只用上一次迭代的结果

853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k 。

接下来 m 行，每行包含三个整数 x,y,z ，表示存在一条从点 x 到点 y 的有向边，边长为 z 。

点的编号为 1∼n 。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

1≤n,k≤500 , 1≤m≤10000 , 1≤x,y≤n ，任意边长的绝对值不超过 10000 。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edge{
    int a, b, w;
}edges[M];

int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < k; i ++ ){
        // 备份
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a , b = edges[j].b ,w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    // 如在 5(+∞)----(-3)---->8(+∞) 时 +∞ 会“变小”
    if (dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
    return dist[n];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i ++ ){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a ,b, w};
    }
    
    int t = bellman_ford();
    
    if(t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\\n", t);
    
    return 0;
}

SPFA 算法

求最短路

for n次
    备份
    for 所有边 a---(w)--->b
        dist[b] = min (dist[b], dist[a] + w) // 优化该操作

使用BFS算法

queue ← 1
while(queue不空){
    t ← q.front(), q.pop();
    更新t的所有出边 t ---(w)--->b;
    queue <--- b;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10 , M = N;

int n,m;
// 稀疏图用带权重的邻接表
int h[N], e[M], w[M], ne[M], idx;
// 当前最短距离
int dist[N];
// 已经确定过最短距离的点
bool st[N];
int q[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q[tt ++ ] = 1;
    st[1] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return 0x3f3f3f3f;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    while (m -- ){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
    }
    
    int t = spfa();
    if(t == 0x3f3f3f3f) puts("impossible");
    else cout << t << endl;
    return 0;
}

判断负环

利用抽屉原理，在更新最短路径时出现两个同样的点

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10 , M = N;

int n,m;
// 稀疏图用带权重的邻接表
int h[N], e[M], w[M], ne[M], idx;
// 当前最短距离 // 已经经历的点的个数
int dist[N],cnt[N];
// 已经确定过最短距离的点
bool st[N];
int q[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    int hh = 0, tt = 0;
    // 把每个点都作为起点来一遍
    for (int i = 1; i <= n; i ++ ){
        st[i] = true;
        q[tt ++ ] = i;
    }

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    while (m -- ){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
    }
    
    bool t = spfa();
    if(t) puts("Yes");
    else puts("No");

    return 0;
}

SPFA的好处：

能解决无负权边的问题，也能解决有负权边的问题，并且效率还比较高。但是当需要求在走不超过k条边的最短路问题上，就只能用Bellman-Ford算法了。

Floyd

求解多源汇最短路问题，也能处理边权为负数的情况，但是无法处理存在负权回路的情况。

使用邻接矩阵来存储图。初始使用d[i][j]来存储这个图，存储所有的边

算法思路：三层循环

算法模板

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

循环结束后，d[i][j]存的就是点i到j的最短距离。

原理是基于动态规划（具体原理在后续的动态规划章节再做详解）。

其状态表示是：d(k, i, j)，从点i，只经过1 ~ k这些中间点，到达点j的最短距离


```markdown
# 最小生成树
## 纲要

- Prim算法 朴素版 $O(n^2)$
- Kruskal算法 $O(mlog(m))$

## Prim算法

第一步 // s[]:在当前连通块中的所有点 // dis[]: 所有点到起点的距离 // 初始化： dis[1] = 0, dis[i] = +∞ 第二步 n次迭代 for(int i = 0; i < n; i++) t ← 不在s[]中距离最近的点用t更新其它点 到集合 的距离 s[] ← t


```cpp

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim(){
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    dist[1] = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ ){
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];
        
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        
        st[t] = true;
    }
    
    return res;
}

Kruskal 算法

将所有边按权重从小到大排序 $O(mlog(m))$
枚举每条边a--(c)--b 权重为c

if a、b不连通：将这条边加到集合里

if 边数为m 停止

时间复杂度$O(m)$

int n, m;
int p[N]; // 并查集的p数组

struct Edge{
    int a, b, w;
    
    bool operator< (const Edge &W) const{
        return w < W.w;
    }
}edges[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal(){
    sort(edges, edges + m);
    
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b , w = edges[i].w;
        
        a = find(a), b = find(b);
        if(a != b){
            // 联通两树
            p[a] = b;
            // res存最小生成树所有树边的权重之和
            res += w;
            // cnt存当前加入多少条边
            cnt ++;
        }
    }
    if (cnt < n - 1) puts("impossible");
    else cout << res << endl;
}

二分图

二分图即我们学过的偶图。

设 $G=(V,E)$ 是一无向图，若顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$，且图中的每条边 $(i,j)$ 所关联的两个顶点 $i$ 和 $j$ 分属这两个不同的顶点集 $(i ∈ A,j ∈ B)$，则称图 $G$ 为一二分图。
一般研究匹配问题与判定问题。

有两种题型相对的解法：

染色法 $O(n+m)$
匈牙利算法 $O(nm)$ 实际运行时间一般远小于此

染色法

给定一个图，判断是否为二分图

二分图的性质：一个图为二分图当且仅当图中不含奇数环（证明过程看学校图论相关内容）

for(i = 1; i <= n; i++)
    if i未染色
        dfs(i, 1):用深度优先遍历把这个连通块全都染一遍，染成1号颜色

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c){
    color[u] = c;
    
    for(int i = h[u]; i != -1;i = ne[i]){
        int j = e[i];
        if(!color[j]){
            if(!dfs(j , 3 - c)) return false;
        }
        else if( color[j] == c) return false;
    }
    
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    while (m -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);add(b,a);
    }
    
    bool flag = true;
    for (int i = 1; i <= n; i ++ ){
        if(!color[i]) {
            if(!dfs( i, 1)){
                flag = false; break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
}

匈牙利算法

成功匹配：所有匹配的边，没有共用顶点
最大匹配：所有成功匹配当中，边数最大的

给定一个二分图，求它的最大匹配。

const int N = 500, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int x)
{
    // 枚举男方所有看上的女方
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
       // 看上过的就不用再看了
            st[j] = true;
            // 女方没匹配过 或 匹配的男生能找到下家
            if (match[j] == 0 || find(match[j]))
            {
                // 给女方匹配相应男方编号
                match[j] = x;
                return true;
            }
        }
    }
    
    return false;
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);
    memset(h, -1, sizeof h);
    
    while (m -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    
    int res  = 0;
    for(int i = 1; i <= n1; i++){
        memset(st, false ,sizeof st);
        if(find(i)) res++;
    }
     
     cout << res << endl;
    
}

树

链式存储表示

二叉链表

三叉链表

双亲链表

线索链表

02 二叉树的遍历

三种遍历方式

普通树算法的递归描述

普通树中序遍历算法的非递归描述（略）

03 遍历算法的应用

统计叶子节点的个数：先序遍历

求二叉树的深度：后序遍历

复制二叉树：后序遍历

建立二叉树存储结构

以字符串形式“根 左子树 右子树”定义一棵二叉树：先序遍历

由先缀表示式建树

由原表示式建树

由二叉树的先序和中序序列建树

二叉树的层次遍历

04 线索二叉树

线索链表数据结构

对以T为根的非空二叉树进行线索化

构建中序线索链表

对中序线索化链表的遍历算法

05 树的存储结构

双亲表示法

孩子链表表示法

树的二叉链表 （孩子-兄弟）存储表示法

树和森林与二叉树的相互转换（很重要）

06 树和森林的遍历

07 树和森林遍历算法的应用

求树的深度

08 哈夫曼树与哈夫曼编码

843. n-皇后问题

输入格式

输出格式

BFS

844. 走迷宫

输入格式

输出格式

数据范围

树和图的深度优先遍历

邻接表表示

树和图的宽度优先遍历

847. 图中点的层次

输出格式

数据范围

有向图的拓扑序列

输入格式

输出格式

堆优化dijkstra

Bellman-Ford算法

853. 有边数限制的最短路

输入格式

输出格式

数据范围

SPFA 算法

求最短路

判断负环

SPFA的好处：

Floyd

算法模板

Kruskal 算法

二分图

染色法

匈牙利算法

以字符串形式“根左子树右子树”定义一棵二叉树：先序遍历

树的二叉链表（孩子-兄弟）存储表示法