3.搜索与图论

3.搜索与图论

明廷盛 嘻嘻😁
  2026-03-09 09:50:45 2026-03-09 09:50:45 Created   2026-03-07 08:53 2026-03-07 08:53 Updated    13.5k Words  63 Mins  

第一章 DFS

1.1 排列数字

思路:
image.png|650
  1. 什么是DFS?(以及两个重要思想)
    DFS是一个很执着的人,他不撞南墙不回头,所以他的搜索 ①不会是最短的路径,并且,其需要②回溯 (回到上一状态,且恢复现场),因为他 虽然不太聪明,但他要是想到达目的地,当他撞墙后,他还是要回头走到你来的起点,去寻找下一条可能的路径直到他到达目的地
  2. **①不会是最短的路径:**不能用DFS求最短路,BFS可以
  3. ②回溯: 就和递归一样,不过在递归前改状态,递归后把状态改回去
  4. 为什么递归前要改状态: 为了防止后续的状态回到当前状态,从而死循环
  5. 为什么递归后要把状态改回去: 因为每个状态可能多次访问,就像走迷宫一样,到达终点的路有n条,可能他们都要经过点G,要是不该回去,能到终点的n条路—>仅仅只有一条了

    做DFS的思路

  • 什么时候用DFS:要是每个过程可以抽象为状态存储就应该可以(个人认为)
    1. 怎么把每步抽象为状态
    2. flag[]数组记录每个状态是否有使用过(以免死循环)
    3. path[]可以记录其从哪个节点来的(一般DFS都会有)[不只一个哟,n皇后问题有好多,dg[],udg[],cols[]]
代码:
#include <iostream>

using namespace std;
const int N = 10;
int n, ans[N], memo[N];

/* di为dfs(i)
         d0
      1   2   3  // 第1个位置可选的数字
     /    |    \
    d1   d1    d1     // 进入第2个位置
  2  3   1  3   1  2  // 选过不能再选
 /   |   |  |   |  \
d2  d2   d2 d2  d2 d2  // 进入第3个位置
3   1    3  1   3   1  */
// 时间复杂度:n*n-1*n-2*1=>O(n!)
// 空间复杂度:数组都是N的=>O(n)
void dfs(int index) {  // index为[0,n)索引
    if (index == n) {
        for (int i = 0; i < n; i++) printf("%d ", ans[i]);
        puts("");
    } else {
        for (int num = 1; num <= n; num++) {
            if (memo[num]) continue;
            ans[index] = num, memo[num] = 1;
            dfs(index + 1);
            memo[num] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}
2026年3月6日21:56:08: 今天的我已经乱杀dfs了,至少玩的比当年透彻多了,如下是2023年9月21日11:22:47写的笔记(知识的诅咒)
1.t为当前状态 ，t+1就是下一个状态咯
2.满足输出条件: 当 当前状态到目标状态了，就是满足条件了
3.这个else中的for循环: 其实就是枚举这个状态的 下一个状态 有哪些，
    * 例如:这题是"全排列"，那下一个状态就有n种(别急着反驳我，看完)
    * 例如:迷宫，对于当前状态来说，四个方向，只要不是墙都可以走(别急着反驳我，看完)
4.满足条件的才是真正的下一个状态:
    * 全排列(例.n=5):1 2 _ 这个位置可以填1~5(n种)，只是1，2填过了，所以真正的下一个状态是3，4，5
        if (!flag[i])
    * 迷宫:可能只对于当前状态来说，可能会出现可以回去的状态，但肯定不行对吧，所以真正的状态是 ***没有走过的***，并且是***合法***的
        if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0 && flag[x][y] == false)
5.为进一步搜索所需要的状态打上标记: 那个愚蠢的小人决定走当前这条路了
6.递归: 他已经开始踏上这条路了
7.恢复到打标记前的状态: 不知道这个愚蠢的小人有没有成功，或许他成功了吧，呃，也有可能碰壁了，**但不管怎么说他回到了这**，回到了开始的地方，他抹去了来过的痕迹， 成功也好，失败也罢，他反正决定重新开始新的旅程，走他的下一条路，
/*        d0          // di为dfs(i)       
      1   2   3       // 第1个位置可选的数字 
     /    |    \                          
    d1   d1    d1     // 进入第2个位置
  2  3   1  3   1  2  // 选过不能再选
 /   |   |  |   |  \
d2  d2   d2 d2  d2 d2  // 进入第3个位置
3   1    3  1   3   1  */
// 时间复杂度:n*n-1*n-2*1=>O(n!)
// 空间复杂度:数组都是N的=>O(n)
const int N = 10;
int n, ans[N], memo[N];

void dfs(int index) {  // index为[0,n)索引
    if (index == n) { for (int i = 0; i < n; i++) printf("%d ", ans[i]); puts(""); }
    else {
        for (int num = 1; num <= n; num++) {
            if (memo[num]) continue;
            ans[index] = num, memo[num] = 1;
            dfs(index + 1);
            memo[num] = 0; // 回溯
        }
    }
}// 调用处: dfs(0)
注意:
  1. 要是忘记模板—>看 模板版本
  2. 要是不知道怎么运用DFS—>看 思路–>做DFS的思路
  3. 要是不知道DFS是什么—>看 解释版本
心得:
首次编辑时间: 2023年9月21日11:22:47
每日一题:

1.2 n皇后问题

思路:
  • dfs
0  1  2  3    dg: 比如在(0,1)放置Q,那主对角#为1-0=2-1=3-2=1;
0    Q        udg:副对角〇为1+0=0+1=1
1 〇     #    1°因为dg是做差(可能为负)所以都加n
2          #  2°因为udg是加和(所以N最大可以是(9,9)=>9+9=18)所以N要开到20
3             3°第2行的(2,1) 1-2=-1不会误判吗? 不会因为有col[1],且此后(2,3/4/5..)不可能为负数
!!!不用怕忘,非常好推,你dg 1+0=1,2+1=3,3+2=5,都不一样,所以是作差!
①时间复杂度: 第一行:n个位置,第二行:n-1个位置(排除同列),,,第n-1行:1个位置;=>O(n!)【总体因为还有对角线剪枝,会<<】
②空间复杂度: 标记数组3*n,棋盘n^2,所以O(n^2+n)=>O(n^2)
代码:
#include <iostream>

using namespace std;
const int N = 20;
int n, col[N], dg[N], udg[N];  // dg为对角↘,udg为副对角
string ans(N* N, '.');         // 最终输出的棋盘

void dfs(int curRow) {
    if (curRow == n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) printf("%c", ans[i * n + j]);
            puts("");
        }
        puts("");
    } else {
        /*
          0  1  2  3
        0    Q
        1 〇     #
        2          #
        3
        dg: 比如在(0,1)放置Q,那主对角#为1-0=2-1=3-2=1;
        udg:副对角〇为1+0=0+1=1
        1°因为dg是做差,可能为负不方便处理索引,所以都加n(小明是第11,全班都加n分,小明还是第11)
          因为udg是加和,所以N最大可以是(9,9)=>9+9=18, 所以N要开到20
        2°第2行的(2,1) 1-2=-1不会误判吗? 不会因为col[1]是记录的,col[],dg[],udg[]共同决定
        3°很好记的,忘了,非常好推,你dg 1+0=1,2+1=3,3+2=5,都不一样,所以是作差!
        */
        for (int c = 0; c < n; c++) {
            int dgIndex = c - curRow + n, udgIndex = c + curRow;
            if (col[c] == 1 || dg[dgIndex] == 1 || udg[udgIndex] == 1) continue;
            col[c] = dg[dgIndex] = udg[udgIndex] = 1;
            ans[curRow * n + c] = 'Q';
            dfs(curRow + 1);
            ans[curRow * n + c] = '.';  // 回溯
            col[c] = dg[dgIndex] = udg[udgIndex] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}
/*0  1  2  3  dg: 比如在(0,1)放置Q,那主对角#为1-0=2-1=3-2=1;
0    Q        udg:副对角〇为1+0=0+1=1
1 〇     #    1°因为dg是做差(可能为负)所以都加n
2          #  2°因为udg是加和(所以N最大可以是(9,9)=>9+9=18)所以N要开到20
3             3°第2行的(2,1) 1-2=-1不会误判吗? 不会因为有col[1],且此后(2,3/4/5..)不可能为负数
!!!不用怕忘,非常好推,你dg 1+0=1,2+1=3,3+2=5,都不一样,所以是作差!*/
// 时间复杂度: 第一行:n个位置,第二行:n-1个位置(排除同列),,,第n-1行:1个位置;=>O(n!)【总体因为还有对角线剪枝,会<<】
// 空间复杂度: 标记数组3*n,棋盘n^2,所以O(n^2+n)=>O(n^2)

const int N = 20;
int n, col[N], dg[N], udg[N];  // dg为对角↘,udg为副对角
string ans(N* N, '.');         // 最终输出的棋盘

void dfs(int curRow) {
    if (curRow == n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) printf("%c", ans[i * n + j]);
            puts("");
        } puts("");
    } else {
        for (int c = 0; c < n; c++) {
            int dgIndex = c - curRow + n, udgIndex = c + curRow;
            if (col[c] == 1 || dg[dgIndex] == 1 || udg[udgIndex] == 1) continue;
            col[c] = dg[dgIndex] = udg[udgIndex] = 1;
            ans[curRow * n + c] = 'Q';
            dfs(curRow + 1);
            ans[curRow * n + c] = '.';  // 回溯
            col[c] = dg[dgIndex] = udg[udgIndex] = 0;
        }
    }
}// 调用处: dfs(0) // 从第0行开始[0,n)索引
注意:
  1. 因为dg是做差(可能为负)所以都加n
  2. 因为udg是加和(所以N最大可以是(9,9)=>9+9=18)所以N要开到20
心得:
首次编辑时间: 2023-9-19 16:47:23
每日一题:

1.3 树的重心

思路:
image (1).png|500
  • 树/图的存储结构:①邻接矩阵 ②邻接表
  • 对比 一般DFS和树DFS
    1. 状态:
      一般DFS: 需要找状态，状态是DFS的重要一环
      树上DFS: 不需要找状态，每个结点就是一个状态
    2. flag[]:
      一般DFS: 需要，记录每个结点是否用过(以免出现死循环) + 回溯
      树上DFS: 需要，记录每个结点是否用过(以免出现死循环)
    3. 回溯:
      一般DFS: 需要，递归前flag[u]=true，递归后flag[u]=false (为什么还原？因为你只有一种办法来到这条路，不得不回溯)
      树上DFS: 不需要，只需要递归前flag[u]=true就行 (为什么？因为各个结点之间是连通的(树/连通图)，可以从多个地方来到这个结点，flag[]的作用仅是避免死循环)
  • 递归前一定需要改状态(flag[])
  • 递归后，如果状态可能被多次访问 → 需要将flag[]改回去，否则不需要。一般树、无环图不需要改回去，有环和一般的DFS需要改回去
  • 看这题”树的重心”的思路:
    • 这题要求最大的连通块的大小
    • int dfs(int u) // 返回u及其儿子的个数
代码:
#include <iostream>
#include <cstring>
#include <climits>

using namespace std;
const int N = 1e5 + 10;                      // 树是特殊的无向图(无向图开两倍)
int h[2 * N], e[2 * N], ne[2 * N], idx = 0;  // 链式前向星0为NULL,1索引
void add(int from, int to) { idx++, e[idx] = to, ne[idx] = h[from], h[from] = idx; }
/* 重心定义: 重心是指树中的一个结点,如果将这个点删除后,
         剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
      1      连通块:删除结点后,1°该结点的所有子树(多叉树🌲) 2°和剩余部分;
 2    4    7 若把4删除: (3,9)/(6)/(1,2,7,5,8) =最大个数为5
5 8  3 6     若把1删除: (2,5,8)/(4,3,6,9)/(7) =最大个数为4 (1为重心,不唯一)
    9        若把3删除: (9)/(1,2,4,7,5,8,6)   =最大个数为7
该题要求: 最大个数最小的,如图样例输出为4; */

/* 关于返回的sum       关于维护的ans: 我们关注左图的每一个箭头尾巴
d1←sum=d2 + d4 + d7   d2返回时,size=max(d5, d8, n-sum); 即size=max([5],[8],[2,1,4,7,3,6,9])
    ↑     ↑   1       d4返回时,size=max(d3, d6, n-sum); 即size=max([3,9],[6],[1,2,5,7,8])
    ↑    sum=d3+d6    d3返回时,size=max(d9,n-sum); 即size=max([9],[rest...])
    sum=d5+d8  ↑   1  向上返回时,维护变量,是树形dfs常用的手段!
        1  1 s=d9                                                                        */
// 时间复杂度:每个结点至多一次访问n,每条边至少被遍历两次2*(n-1)=>O(2*(n-1)+n)=>O(n)
// 空间复杂度: O(n)
// 【n个结点的树,至多n-1条边】【n个结点的图,至多n(n-1)/2(无向完全图)】

int n, st[N], ans = INT_MAX;  // st记录每个结点是否访问过,ans为连通块中点数的最大值最小值
// 返回根x及其子树的结点个数
int dfs(int x) {
    st[x] = 1;
    int size = 0, sum = 1;  // size为最大子树的节点数,sum为以x为根的子树结点个数
    for (int i = h[x]; i != 0; i = ne[i]) {
        int son = e[i];
        if (st[son]) continue;
        int sonCount = dfs(son);
        size = max(size, sonCount);  // 向上返回时维护
        sum += sonCount;
    }
    ans = min(ans, max(size, n - sum));
    return sum;
}


int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        add(from, to), add(to, from);
    }
    dfs(1);
    printf("%d", ans);
    return 0;
}
const int N = 1e5 + 10;                      // 树是特殊的无向图(无向图开两倍)
int h[2 * N], e[2 * N], ne[2 * N], idx = 0;  // 链式前向星0为NULL,1索引
void add(int from, int to) { idx++, e[idx] = to, ne[idx] = h[from], h[from] = idx; }
/* 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,则这个节点被称为树的重心。
      1      连通块:删除结点后,1°该结点的所有子树(多叉树🌲) 2°和剩余部分;
 2    4    7 若把4删除: (3,9)/(6)/(1,2,7,5,8) =最大个数为5
5 8  3 6     若把1删除: (2,5,8)/(4,3,6,9)/(7) =最大个数为4 (1为重心,不唯一)
    9        若把3删除: (9)/(1,2,4,7,5,8,6)   =最大个数为7    |该题要求: 最大个数最小的,如图样例输出为4; */

/*关于返回的sum:        关于维护的ans: 我们关注左图的每一个箭头尾巴
d1←sum= d2 + d4 + d7   d2返回时,size=max(d5, d8, n-sum); 即size=max([5],[8],[2,1,4,7,3,6,9])
    ↑    ↑   1         d4返回时,size=max(d3, d6, n-sum); 即size=max([3,9],[6],[1,2,5,7,8])
    ↑   sum=d3 + d6    d3返回时,size=max(d9,n-sum); 即size=max([9],[rest...])
  sum=d5+d8  ↑   1     向上返回时,维护变量,是树形dfs常用的手段!
      1  1 s=d9                                                                        */
// 时间复杂度:每个结点至多一次访问n,每条边至少被遍历两次2*(n-1)=>O(2*(n-1)+n)=>O(n)
// 空间复杂度: O(n)
// 【n个结点的树,至多n-1条边】【n个结点的图,至多n(n-1)/2(无向完全图)】

int n, st[N], ans = INT_MAX;  // st记录每个结点是否访问过,ans为连通块中点数的最大值最小值
// 返回根x及其子树的结点个数
int dfs(int x) {
    st[x] = 1;
    int size = 0, sum = 1;  // size为最大子树的节点数,sum为以x为根的子树结点个数
    for (int i = h[x]; i != 0; i = ne[i]) {
        int son = e[i];// x->son
        if (st[son]) continue;
        int sonCount = dfs(son);
        size = max(size, sonCount);  // 向上返回时维护
        sum += sonCount;
    }
    ans = min(ans, max(size, n - sum));
    return sum;
}// 调用处dfs(1), printf("%d", ans);
注意:
  1. 树是一种特殊的无向图: 所以 add(a, b); add(b, a);
心得:
2023年9月22日12:32:49
*   这题脑子不清晰,很难做出来
*   刚开始研究,为什么递归后要改的时候确实挺懵逼的,但GPT帮了我,嘻嘻\~
每日一题:

第二章 BFS

关于BFS的问题: 到底是先判断or先入队,何时判断? 在哪判断? 在哪修改已访问? 什么时候置为已访问;
适用大部分的情况: ①入队后, 立即将状态置为已访问; ②拓展状态必须判断是否访问

2.1 走迷宫

思路:
image.png|232
  • 什么是BFS
    1. 按层搜索
    2. 当每个状态间的权值都相等时,其搜索为最短结果
    3. BFS一般有个dist[]来记录搜索ans,即到达当前状态之前,经历了几个状态
      • 走迷宫: dist[i][j]表示从起点到(i,j)的距离,并且这里每个状态间都是1的权值,所以dist[aim.x][aim.y]就是最后要的 从起点–>(aim.x,aim.y)的 最短步数
      • 八数码: dist[][]从数组–>哈希,为什么??因为你每个状态不能像走迷宫一样是一个坐标,可以用二维,你的每个状态是string,得用哈希来存这样的状态,和该状态的值,那么最后目标状态的值就是ans
  • 遇到BFS怎么想
    1. 找什么是状态,
    2. 找怎么表示状态
      • 走迷宫问题: 每个格子是一个状态
      • 八数码问题: 每种矩阵是一个状态
    3. 状态怎么转移
    4. 别忘标记!!!!!,和DFS一样的
  • 和DFS的不同,这个不用回溯
代码:
/*
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*/
#include <iostream>
#include <queue>
#define pii pair<int, int>

using namespace std;
const int N = 110;
int n, m, map[N][N], dist[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int bfs(int sx, int sy) {
    int flag[N][N] = {0};
    queue<pii> q;
    q.push({sx, sy});
    flag[sx][sy] = 1;
    dist[sx][sy] = 0;

    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 1 || nextX > n || nextY < 1 || nextY > m) continue;
            if (map[nextX][nextY] == 1 || flag[nextX][nextY]) continue;
            dist[nextX][nextY] = 1 + dist[x][y];
            q.push({nextX, nextY});
            flag[nextX][nextY]=1;
        }
    }
    return dist[n][m];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) scanf("%d", &map[i][j]);
    }
    printf("%d", bfs(1, 1));
    return 0;
}
/* // 从0开始,#为墙,1~8为遍历到的次序
0 1 0 0 0 | 0 # 6 7 8   
0 1 0 1 0 | 1 # 5 # 7   
0 0 0 0 0 | 2 3 4 5 6   
0 1 1 1 0 | 3 # # # 7
0 0 0 1 0 | 4 5 6 # 8 */
// 时间复杂度: 每个格子至多入队一次,出队时检测4方向=>4×n×m==>O(n×m)
// 空间复杂度: 二维数组==>O(n×m)

const int N = 110;
int n, m, map[N][N], dist[N][N];  // dist[i][j]表示从(1,1)到(i,j)的最短距离
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int bfs(int sx, int sy) {
    int flag[N][N] = {0}; // 当然BFS熟练后,不刚需flag,dist初始化为-1表示没有走过
    queue<pii> q;
    q.push({sx, sy});
    flag[sx][sy] = 1; // 入队时,立刻置为已访问
    dist[sx][sy] = 0;

    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 1 || nextX > n || nextY < 1 || nextY > m) continue;
            if (map[nextX][nextY] == 1 || flag[nextX][nextY]) continue;    // 状态必须判断是否访问
            dist[nextX][nextY] = 1 + dist[x][y];
            q.push({nextX, nextY});
            flag[nextX][nextY]=1;                                          // 入队立即置已访问
        }
    }
    return dist[n][m]; // 返回(1,1)到(n,m)的最短距离
} // 主函数调用 printf("%d", bfs(1, 1)); // [1,n][1,m]索引
注意:
心得:
首次编写日期: 2023年9月22日
每日一题:

2.2 八数码

思路:
  • 这个每个状态都是字符串, 所以用map存储
代码:
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#define pii pair<int, int>

using namespace std;
const int COL = 3;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string ans = "12345678x";

pii i2p(int index) { return {index / COL, index % COL}; }
int p2i(int x, int y) { return x * COL + y; };

// 索引和坐标的转换关系: x=index/3; y=index%3; index=x*3+y
int bfs(string input) {
    queue<string> q;
    unordered_map<string, int> dist;
    unordered_set<string> isVisited;
    q.push(input);
    while (q.size()) {
        string str = q.front();
        q.pop();
        int xIndex = str.find('x'), x, y;
        tie(x, y) = i2p(xIndex);
        if (isVisited.count(str)) continue;
        isVisited.insert(str);
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= 3 || nextY < 0 || nextY >= 3) continue;
            int nextIndex = p2i(nextX, nextY);
            string nextStr = str;
            swap(nextStr[xIndex], nextStr[nextIndex]);
            if (isVisited.count(nextStr)) continue;
            // printf("%s | %s\n", str.c_str(), nextStr.c_str());
            dist[nextStr] = dist[str] + 1;
            q.push(nextStr);
        }
    }
    return dist.count(ans) ? dist[ans] : -1;
}

int main() {
    string input;
    for (int i = 0; i < 9; i++) {
        char ch;
        cin >> ch;
        input += ch;
    }

    printf("%d", bfs(input));

    return 0;
}
/* 1 2 3   1 2 3   1 2 3   1 2 3
   x 4 6   4 x 6   4 5 6   4 5 6
   7 5 8   7 5 8   7 x 8   7 8 x
123x46758->1234x6758->1234756x8->12347568x */
// 时间复杂度:9位全排列有9!种情况,每种情况4拓展=>O(9!×4)
// 空间复杂度:每个状态9字符=>O(9!×9)
const int COL = 3;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string ans = "12345678x";

pii i2p(int index) { return {index / COL, index % COL}; }
int p2i(int x, int y) { return x * COL + y; };

// 索引和坐标的转换关系: x=index/3; y=index%3; index=x*3+y
int bfs(string input) {
    queue<string> q;
    unordered_map<string, int> dist;
    unordered_set<string> isVisited;
    q.push(input);
    isVisited.insert(input); // 入队立即置已访问
    while (q.size()) {
        string str = q.front();
        q.pop();
        int xIndex = str.find('x'), x, y;
        tie(x, y) = i2p(xIndex);
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= 3 || nextY < 0 || nextY >= 3) continue;
            int nextIndex = p2i(nextX, nextY);
            string nextStr = str;
            swap(nextStr[xIndex], nextStr[nextIndex]);
            if (isVisited.count(nextStr)) continue;    // 状态必须判断是否访问
            dist[nextStr] = dist[str] + 1;
            q.push(nextStr); 
            isVisited.insert(nextStr);        		   // 入队立即置已访问
        }
    }
    return dist.count(ans) ? dist[ans] : -1;
} //调用处: printf("%d", bfs(input)); // input="23415x768"
注意:
心得:
每日一题:

2.3 岛屿数量

思路:
  • 类似走迷宫, 主函数遍历二维数组, 如果访问过就continue,否则就进入BFS
代码:
/*
1 0 0 0 0 1 0 1
1 1 0 0 0 0 0 1
1 1 1 0 0 0 0 1
0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 1
BFS
main中: 遍历r*c
bfs中: 尽可能拓展;
visited: 开为全局
*/

#include <iostream>
#include <queue>
#define pii pair<int, int>

using namespace std;
const int N = 1e3 + 10;
int r, c, map[N][N], visited[N][N] = {0};
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

// 从(x,y)开始尽可能拓展1
void bfs(int sx, int sy) {
    queue<pii> q;
    q.push({sx, sy});
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (visited[x][y]) continue;
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= r || nextY < 0 || nextY >= c) continue;
            if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;
            q.push({nextX, nextY});
        }
    }
}


int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    //
    int ans = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (map[i][j] == 1 && visited[i][j] == 0) {
                ans++;
                bfs(i, j);
            }
        }
    }
    printf("%d", ans);

    return 0;
}
/* 6 8  数字为依次遍历到的次序
   1 0 0 0 0 1 0 1 | 1 0 0 0 0 2 0 3  // STEP1:主 函数遍历二维数组,见到陆地1就访问,如果拓展过就continue,否则就进入BFS
   1 1 0 0 0 0 0 1 | 1 1 0 0 0 0 0 3  // STEP2: BFS只能拓展陆地1 (4方向拓展)
   1 1 1 0 0 0 0 1 | 1 1 1 0 0 0 0 3  // STEP3: 几次BFS就是几个陆地
   0 0 0 0 0 0 0 1 | 0 0 0 0 0 0 0 3
   1 0 0 0 1 0 0 1 | 4 0 0 0 5 0 0 3
   1 0 0 1 0 0 0 1 | 4 0 0 6 0 0 0 3 */
// 时间复杂度:每个点至多进入一次,每个点4拓展=>O(4×n×m)=O(n×m)
// 空间复杂度: 二维数组=>O(n×m)
const int N = 310;
int col, row, map[N][N], visited[N][N];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};

void bfs(int sx, int sy) {
    queue<pii> q;
    q.push({sx, sy});
    visited[sx][sy] = 1;
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i], nextY = y + dy[i];
            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) continue;
            if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;   // 状态必须判断是否访问
            q.push({nextX, nextY});
            visited[nextX][nextY] = 1;                                   	 // 入队立即置已访问
        }
    }
}/* 调用处
int lands = 0;
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (map[i][j] == 0 || visited[i][j] == 1) continue;
        lands++;
        bfs(i, j);
    }
}
printf("%d", lands);*/
注意:
心得:
每日一题:

2.4 图中点的层次

思路:
  • 和一般的BFS不能说有啥区别,只能说完全一样 -_-!
代码:
/* 和走迷宫一样,只不过改为了遍历图(链式前向星)
1——->2
↓ ↘ ↓
4<——-3 */

#include <iostream>
#include <queue>
#include <cstring>
#include <climits>

using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;  // 0为NULL,one index
void add(int from, int to) { idx++, e[idx] = to, ne[idx] = h[from], h[from] = idx; }
int n, m, dist[N], st[N] = {0};  // n个点m条边;dist[i]表示1->i的最短距离

int bfs(int s) {
    queue<int> q;
    q.push(s);
    st[s] = 1;
    while (q.size()) {
        int from = q.front();
        q.pop();
        // if (st[from]) continue;
        for (int i = h[from]; i != 0; i = ne[i]) {
            int to = e[i];         // from->to
            if (st[to]) continue;  // 比如从1已经到过3了,2再到3就continue;而且有可能存在自环/重边
            st[to] = 1;
            dist[to] = dist[from] + 1;
            q.push(to);
        }
    }
    return st[n] == 0 ? -1 : dist[n];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        add(from, to);  // 有向图
    }
    printf("%d", bfs(1));
    return 0;
}

/* 和走迷宫一样,只不过改为了遍历图(链式前向星)
1——->2
↓ ↘ ↓
4<——-3 */
// 时间复杂度: 每个节点入队一次，每条边遍历一次=>O(n+m) 
// 空间复杂度: 邻接表存储O(n+m)，队列和数组O(n=>O(n+m) 
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;  // 0为NULL,one index
void add(int from, int to) { idx++, e[idx] = to, ne[idx] = h[from], h[from] = idx; }
int n, m, dist[N], st[N] = {0};  // n个点m条边;dist[i]表示1->i的最短距离

int bfs(int s) {
    queue<int> q;
    q.push(s);
    st[s] = 1;
    while (q.size()) {
        int from = q.front();
        q.pop();
        for (int i = h[from]; i != 0; i = ne[i]) {
            int to = e[i];         // from->to
            if (st[to]) continue;  // 比如从1已经到过3了,2再到3就continue;而且有可能存在自环/重边
            dist[to] = dist[from] + 1;
            q.push(to);     
            st[to] = 1;			    // 入队立即置已访问	
        }
    }
    return st[n] == 0 ? -1 : dist[n];
} // 调用处 printf("%d", bfs(1));
注意:
  1. 当用过当期的点后,一定一定要记得,flag[j]=true,希望这个刻进你的DNA里
心得:
首次编辑时间: 2023年9月22日14:41:37
每日一题:

第三章 拓扑排序

3.1 拓扑排序

第四章 最短路

image (3).png|500

4.1 Dijkstra

思路:
  • BV1W64y1z7jh [P27]———–Dijkstra + 邻接矩阵法
  • 《趣学算法》2.5—————–Dijkstra + 优先队列法
  • 《趣学算法》附录C————-优先队列
  • 《趣学算法》附录D————-邻接表[链表实现]
  • BV13r4y1X7a4 [P6]————链式前向星[静态数组实现]
    做题
  • 洛谷—P3371 【模板】单源最短路径（弱化版）
  • 洛谷—P4779 【模板】单源最短路径（标准版）
// Dijkstra为什么无法处理负权边: Dijkstra基于贪心,认为已确定最短的节点不再更新,但负权边可能导致已确定节点有更小路径,破坏前提.【一锤子买卖】
/* 1-(5)->2-(100)->3 和 1-(2)->3
   INIT       Round1       Round2    Round3   
1   0          0*           0*         0*
2  INF   min(INF,0+5)=5     5          5*
3  INF   min(INF,0+2)=2     2*         2*
已纳入     1                1,3      1,3,2  */
/* 时间复杂度: O(mlogn) 
I为什么不是O(nlogn)? m条边,最坏情况,可能造成m次更新入堆(1 2 5;1 2 4;1 2 3;1 2 2;1 2 1)虽然只有2个顶点,但每一条边都可以更新最短距离导致   (5,2)(4,2)(3,2)(2,2)(1,2)都在堆里面躺着; 
II那为什么不是O(mlogm)呢,不是堆中至多有m个点吗?那完全二叉树的高度应该是logm啊,为什么是logn呢?因为在图论中n-1 ≤ m ≤ n^2,同时取对数,
  log m≤ log(n^2) = 2logn,故logm常用logn==>O(mlogn)
III我记得有Dijkstra适用于稀疏图啊,那是什么? 
   - 朴素版：每轮找“最小 dist 的未确定点”要扫一遍所有点 ⇒ O(n^2)  - 堆优化版：每次用堆取最小的点 ⇒ O(m log n)
   稀疏图(m≈n):堆优化O(mlogn)≈O(nlogn),朴素:O(n^2); 稠密图(m≈n^2)堆优化O(n^2logn),朴素:O(n^2) */
// 空间复杂度: 邻接表存储图O(n+m),dist、st数组O(n),优先队列最多O(n)=>O(n + m)
代码:
#include <iostream>
#include <queue>
#include <functional>
#include <cstring>
#define pii pair<int, int>

using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;  // 0为NULL,one index
void add(int from, int to, int x) { idx++, e[idx] = to, w[idx] = x, ne[idx] = h[from], h[from] = idx; }

int n, m, dist[N], st[N];

priority_queue<pii, vector<pii>, greater<pii>> pq;  // <1到x的距离,x>
int dijkstra(int s) {
    memset(dist, INF, sizeof(dist));
    pq.push({0, s});
    dist[s] = 0;
    // st[s] = 1;
    while (pq.size()) {
        int from = pq.top().second, beforeDist = pq.top().first;
        pq.pop();
        if (st[from]) continue;
        st[from] = 1;
        for (int i = h[from]; i != 0; i = ne[i]) {
            int to = e[i], d = w[i];
            // if (st[to]) continue;
            if (beforeDist + d >= dist[to]) continue;

            dist[to] = beforeDist + d;
            pq.push({dist[to], to});
            // st[to] = 1;
        }
    }
    return dist[n] == INF ? -1 : dist[n];
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int from, to, x;
        scanf("%d %d %d", &from, &to, &x);
        add(from, to, x);
    }

    printf("%d", dijkstra(1));
    return 0;
}
// Dijkstra为什么无法处理负权边: Dijkstra基于贪心,认为已确定最短的节点不再更新,但负权边可能导致已确定节点有更小路径,破坏前提.【一锤子买卖】
/* 1-(5)->2-(100)->3 和 1-(2)->3
   INIT       Round1       Round2    Round3   
1   0          0*           0*         0*
2  INF   min(INF,0+5)=5     5          5*
3  INF   min(INF,0+2)=2     2*         2*
已纳入     1                1,3      1,3,2  */
/* 时间复杂度: O(mlogn) 
I为什么不是O(nlogn)? m条边,最坏情况,可能造成m次更新入堆(1 2 5;1 2 4;1 2 3;1 2 2;1 2 1)虽然只有2个顶点,但每一条边都可以更新最短距离导致   (5,2)(4,2)(3,2)(2,2)(1,2)都在堆里面躺着; 
II那为什么不是O(mlogm)呢,不是堆中至多有m个点吗?那完全二叉树的高度应该是logm啊,为什么是logn呢?因为在图论中n-1 ≤ m ≤ n^2,同时取对数,
  log m≤ log(n^2) = 2logn,故logm常用logn==>O(mlogn)
III我记得有Dijkstra适用于稀疏图啊,那是什么? 
   - 朴素版：每轮找“最小 dist 的未确定点”要扫一遍所有点 ⇒ O(n^2)  - 堆优化版：每次用堆取最小的点 ⇒ O(m log n)
   稀疏图(m≈n):堆优化O(mlogn)≈O(nlogn),朴素:O(n^2); 稠密图(m≈n^2)堆优化O(n^2logn),朴素:O(n^2) */
// 空间复杂度: 邻接表存储图O(n+m),dist、st数组O(n),优先队列最多O(n)=>O(n + m)
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;  // 0为NULL,one index
void add(int from, int to, int x) { idx++, e[idx] = to, w[idx] = x, ne[idx] = h[from], h[from] = idx; }

int n, m, dist[N], st[N];
priority_queue<pii, vector<pii>, greater<pii>> pq;  // greater:越来越大; <beforeDist, from>
int dijkstra(int s) {
    memset(dist, INF, sizeof(dist));
    pq.push({0, s});
    while (pq.size()) {
        int from = pq.top().second, beforeDist = pq.top().first;
        pq.pop();
        if (st[from]) continue; // 拓展状态前判断
        st[from] = 1;           // 判断后立刻改变状态
        for (int i = h[from]; i != 0; i = ne[i]) {
            int to = e[i], d = w[i];
            if (beforeDist + d >= dist[to]) continue;
            dist[to] = beforeDist + d;
            pq.push({dist[to], to});
        }
    }
    return dist[n] == INF ? -1 : dist[n];
} // 调用处: printf("%d", dijkstra(1));
注意:
  1. Dijkstra中变量定义的理解: 该表格为某样例的最终状态表格 (规定1为start点)
索引(边节点) 1 2 3 4 5
distance[] //从规定的起点到当前索引(边节点)的最短距离 0 2 4 //从1到3的最短距离为4 8 //从1到4的最短距离为8 5 //从1到5的最短距离为5
parent[] //要是找来源需要递归调用 -1 1 2 2 3
2. 关于链式前向星: 模板二的写法是edge从1开始索引,没有0,0就是标准写法的-1
3. 关于最大值 # define MAX 
* 16位的有符号整数最大值为 **32767  (10^4)**
* 32位的有符号整数最大值为 **2147483647  (10^10) 在cpp中可以直接`INT_MAX` , 这个就是2147483647**
* 64位的有符号整数最大值为 **9223372036854775807  (10^19) 在cpp中可以直接**`LONG_LONG_MAX`**, 这个就是2147483647**
  1. Dijkstra这个函数注意: 刚开始一定要把dist[s]=0;否则new_distance会爆
心得:
每日一题:

4.2 Bellman-Ford

思路:
image (4).png|303
  • 负环: 负环是指一个有向图中存在一个环，且该环上所有边的权重之和为负数。也就是说，从起点出发沿着环的方向走一圈回到起点，累计的权重是负数。
// Bellman-Ford作用: 找到从1开始到各个点的最短距离(以及路径) | 可以处理存在负权的边 | 可以找负环
// STEP1: 初始dist只有dist[1]=0,其他都是不可达
// STEP2: 进行n-1次松弛操作(一次松弛操作定义为:遍历所有的边,若存在更短的路径,更新dist[]数组;同时可以维护source[]记录从哪个前驱结点更新来)
// STEP3: n-1次松弛操作理应完成所有最短的更新(为什么?I), 如果第n次操作时,dist[]还能更新=>图中存在负权边
/* 1-(5)->2-(-1自环)->2 和 2-(-100)->3
   INIT         Round1                        Round2                       Round3(第n轮)
1  (0, -1)      (0, -1)                      (0, -1)                      (0, -1)
2  (INF, -1)    min(INF,0+5)=(5,1)           min(5,5-1)=(4,2)             min(4,4-1)=(3,2) 【第n轮仍更新，检测到负环】
3  (INF, -1)    min(INF,INF-100)=(INF-100,2) min(INF-100,5-100)=(-95,2)   min(-95,4-100)=(-96,2)
I的解释: 假设图中有n个顶点。从源点到任意顶点的最短路径最多包含 n-1 条边，因为如果路径包含 n 条或更多边，则必然存在环（重复访问顶点）。最短路径不应包含正权环（否则去掉环可得更短路径），而负权环会导致最短路径无定义（算法通过第 n 次迭代检测此类环）。因此，通过 n-1 次松弛操作（每次操作考虑增加一条边），足以覆盖所有可能的最短路径。每次松弛操作基于上一轮结果更新距离，经过 n-1 轮后，所有最短路径（如果存在）都会被找到。
II的解释: 这题是找经过不超过k条边的最短路,为什么BellmanFord也能做? k次松弛操作就是经过≤k条边的最短路! 如果 k ≥ n-1，则结果与标准算法一致；如果 k < n-1，则找到的是受限步数内的最短路径。 */

/* 1-(5)->2-(-100)->3  【INF-100,2表示从2更新而来,1到3的最短路为1->2->3;举例为】
   INIT         Round1                        Round2                       Round3
1   0             0                             0                            0
2  INF   min(INF,0+5)=(5,1)             min(5,0+5)=(5,1)                   (5,1)
3  INF   min(INF,INF-100)=(INF-100,2)   min(5-100,INF-100)=(-955,2)       (-955,2)   【不存在负环=Round_n没有更新】
I为什么要backup数组? 在Round1更新3时,如果没用backup,那min(INF,5-100)=-95,但其实应该用INIT的INF更新为INF-100
II为什么最终判断不是dist[n]==INF? 可达点的距离由起点经若干条边累加,不会很大(比如1->2);不可达点可能被其他不可达点用,负权边更新(如这个例子,显然Round1的3为INF-100;)，距离略小于INF但仍远大于正常值, 所以用INF/2作为阈值区分。
III这也反映了,若k-1,只能更新到Round1,那3就不可达; 但如果k=2,能更新到Round2,也就是经过2条边后可以从1到3 此时dist[3]<INF/2可达 */
// 时间复杂度: 外层循环k轮，每轮遍历所有m条边进行松弛=>O(k×m)
// 空间复杂度: 需要dist和backup数组存储n个点的距离，以及存储m条边的信息=>O(n+m)
代码:
/*
a-1->b
3↘↙1
  c
 */
#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
typedef struct edge {
    int from, to, w;
} edge;
edge edges[N];
int n, m, k;

int bellmanFord(int s) {
    int dist[N], backup[N];  // dist[i]表示从s->i的最短路径, backup[i]为上一轮的距离
    memset(dist, INF, sizeof(dist));
    dist[s] = 0;
    for (int round = 1; round <= k; round++) {
        memcpy(backup, dist, sizeof(dist));
        for (int i = 0; i < m; i++) {  // 遍历所有边
            int from = edges[i].from, to = edges[i].to, w = edges[i].w;
            dist[to] = min(dist[to], backup[from] + w);  // 这里的from可能已经改过了,所以得backup;
        }
    }
    return dist[n] > INF / 2 ? INF : dist[n];  // return dist[n] == INF / 2 ? -1 : dist[n];
}


int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].w);

    int result = bellmanFord(1);
    printf("%s", result == INF ? "impossible" : to_string(result).c_str());
    return 0;
}

// Bellman-Ford作用: 找到从1开始到各个点的最短距离(以及路径) | 可以处理存在负权的边 | 可以找负环
// STEP1: 初始dist只有dist[1]=0,其他都是不可达
// STEP2: 进行n-1次松弛操作(一次松弛操作定义为:遍历所有的边,若存在更短的路径,更新dist[]数组;同时可以维护source[]记录从哪个前驱结点更新来)
// STEP3: n-1次松弛操作理应完成所有最短的更新(为什么?I), 如果第n次操作时,dist[]还能更新=>图中存在负权边
/* 1-(5)->2-(-1自环)->2 和 2-(-100)->3
   INIT         Round1                        Round2                       Round3(第n轮)
1  (0, -1)      (0, -1)                      (0, -1)                      (0, -1)
2  (INF, -1)    min(INF,0+5)=(5,1)           min(5,5-1)=(4,2)             min(4,4-1)=(3,2) 【第n轮仍更新，检测到负环】
3  (INF, -1)    min(INF,INF-100)=(INF-100,2) min(INF-100,5-100)=(-95,2)   min(-95,4-100)=(-96,2)
I的解释: 假设图中有n个顶点。从源点到任意顶点的最短路径最多包含 n-1 条边，因为如果路径包含 n 条或更多边，则必然存在环（重复访问顶点）。最短路径不应包含正权环（否则去掉环可得更短路径），而负权环会导致最短路径无定义（算法通过第 n 次迭代检测此类环）。因此，通过 n-1 次松弛操作（每次操作考虑增加一条边），足以覆盖所有可能的最短路径。每次松弛操作基于上一轮结果更新距离，经过 n-1 轮后，所有最短路径（如果存在）都会被找到。
II的解释: 这题是找经过不超过k条边的最短路,为什么BellmanFord也能做? k次松弛操作就是经过≤k条边的最短路! 如果 k ≥ n-1，则结果与标准算法一致；如果 k < n-1，则找到的是受限步数内的最短路径。 */

/* 1-(5)->2-(-100)->3  【INF-100,2表示从2更新而来,1到3的最短路为1->2->3;举例为】
   INIT         Round1                        Round2                       Round3
1   0             0                             0                            0
2  INF   min(INF,0+5)=(5,1)             min(5,0+5)=(5,1)                   (5,1)
3  INF   min(INF,INF-100)=(INF-100,2)   min(5-100,INF-100)=(-955,2)       (-955,2)   【不存在负环=Round_n没有更新】
I为什么要backup数组? 在Round1更新3时,如果没用backup,那min(INF,5-100)=-95,但其实应该用INIT的INF更新为INF-100
II为什么最终判断不是dist[n]==INF? 可达点的距离由起点经若干条边累加,不会很大(比如1->2);不可达点可能被其他不可达点用,负权边更新(如这个例子,显然Round1的3为INF-100;)，距离略小于INF但仍远大于正常值, 所以用INF/2作为阈值区分。
III这也反映了,若k-1,只能更新到Round1,那3就不可达; 但如果k=2,能更新到Round2,也就是经过2条边后可以从1到3 此时dist[3]<INF/2可达 */
// 时间复杂度: 外层循环k轮，每轮遍历所有m条边进行松弛=>O(k×m)
// 空间复杂度: 需要dist和backup数组存储n个点的距离，以及存储m条边的信息=>O(n+m)

const int N = 1e4 + 10, INF = 0x3f3f3f3f;
typedef struct edge {int from, to, w;} edge; edge edges[N];// 存储所有边,无需链式前向星
int n, m, k; // n个点,m条边,经过k步的最小值

// 不可达返回INF, 否则返回s->n的最短距离
int bellmanFord(int s) {
    int dist[N], backup[N];  // dist[i]表示从s->i的最短路径, backup[i]为上一轮的距离
    memset(dist, INF, sizeof(dist)); 
    dist[s] = 0;
    for (int round = 1; round <= k; round++) {
        memcpy(backup, dist, sizeof(dist));
        for (int i = 0; i < m; i++) {  // 遍历所有边
            int from = edges[i].from, to = edges[i].to, w = edges[i].w;
            dist[to] = min(dist[to], backup[from] + w);  // 这里的from可能已经改过了,所以得backup;
        }
    }
    return dist[n] > INF / 2 ? INF : dist[n]; 
}// 调用处:int result = bellmanFord(1); printf("%s", result == INF ? "impossible" : to_string(result).c_str());
注意:

image (5).png

  1. Bellman_Ford也可以用于判断负环
    要是k>=n就说明该图中存在负环,但一般不会用这个判断,因为其时间复杂度为O(nm),n 表示点数,m表示边数
  2. 为什么要备份数组
    在遍历每条边前，我们会先备份上一轮的各点的距离，防止在本次遍历每条边时发生串联，例如样例中的，各点的初始距离为正无穷，我们第一次枚举的1到2，距离变成了1，如果不采用备份，我们遍历2到3时，距离就会变成1+1=2，此时用了两条边，并不符合题目要求，反之，当我们备份数组后，遍历2到3的距离就是正无穷+1和3比较，仍是3；
  3. 最后这里这样写 if (dist[n] > 0x3f3f3f3f / 2) return -1;是因为
    有可能会有小bug,就是负权但照样有减去,但减的不多,根据题目数据不会减到一半以下
心得:
这个算是最短路里面最简单的了;
收回,我知道当时为什么学的不算太好了,其实当时有很多问题都没有理解透彻,
每日一题:

4.3 Spfa最短路

思路:
  • 怎么优化bellman-Ford的: SPFA算法通过使用队列（Queue）来代替Bellman-Ford算法中的松弛操作，从而提高了算法的效率。具体优化步骤如下：
    1. 初始化距离数组dist[]，将源点s的距离设为0，其他点的距离设为INF。
    2. 将源点s加入队列。
    3. 当队列非空时，执行以下步骤：
      • 从队列中取出一个顶点u。
      • 遍历顶点u的所有邻接顶点v，计算顶点v的新距离：
        • 如果dist[u] + weight(u, v) < dist[v]，则更新dist[v]为dist[u] + weight(u, v)。
        • 如果dist[v]发生了更新，将顶点v加入队列（如果v已经在队列中，则不重复添加）。
    4. 重复步骤3，直到队列为空。
  • 这里的st[]是用于记录当前点是否在队列中的
    • 所以,x入队 st[x]=true;
    • x出队 st[x]=false;
/* Spfa 是 BellmanFord的改良版
只有当一个结点的最短距离变小了,它原本的邻居才有可能通过它缩短距离∴我们不必像BF一样每一轮遍历所有的边,而是使用队列,只要谁的距离被更新了,就把谁丢到队里中, 只对队列中的结点进行拓展(链式前向星)更新
I:BellmanFord对所有的边都更新; Spfa仅对更新了更短距离的点更新
II: Spfa有一个队列存放那些"更新了更短距离的点",且同一时刻同一个结点仅能在队列中存在一个,但可以重复入队(不同时刻)用st[]判断 */

// 时间复杂度: 平均O(m),因为只有当结点距离被更新时才会入队并遍历其出边,但在某些特殊图/数据下同一结点可能被反复入队,最坏可达O(nm)
// 空间复杂度: 链式前向星存m条边,dist/st数组和队列中最多n个结点=>O(n + m)


/* 1-(1)->2-(-1自环)->2-(4)->3 【O(∞)如果不判断负环终止的话】
     INIT       Step1(出队1)        Step2(出队2)        Step3(出队3)      Step5(出队2)       Step...
1  (0, -1)       (0, -1)            (0, -1)             (0,-1)            (0, -1)          循环
2  (INF, -1)   min(INF,0+1)=(1,1) min(1,1-1)=(0,2)      (0, 2)         min(0,0-1)=(-1,2)   因为负环
3  (INF, -1)     (INF, -1)        min(INF,1+4)=(5,2)    (5, 2)         min(5,-1+4)=(3,2)   一直更新
q  [1]            [2]               [3,2]                [2]                [3,2]          一直入队 */

/* (1 2 5;1 2 4;1 2 3;1 2 2;1 2 1; 2 3 5;2 3 4;2 3 3;2 3 2;2 3 1)   【O(m)所有边入队一次】
     INIT         Step1(出队1)        Step2(出队2)        Step3(出队3)    1-(5)->2-(5)->3
1  (0,  -1)       (0, -1)              (0,-1)             (0,-1)          (4)->  (4)->
2  (INF,-1)   min(INF,0+5)=(5,1)       (1, 1)             (1, 1)          (3)->  (3)->
              min(5,  0+4)=(4,1)                                          (2)->  (2)->
					...          										  (1)->  (1)->
     		  min(2,  0+1)=(1,1)
3  (INF,-1)        (INF,-1)         min(INF,1+5)=(6,2)    (2,2)
									min(6  ,1+4)=(5,2)
							                ....
									min(3  ,1+1)=(2,2)
q  [1]            [2]                   [3]                 []               */

/*1 3 3;1 2 5;2 1 1;3 2 1 【O(nm)菊花图】
     INIT       Step1(出队1)        Step2(出队2)      Step3(出队3)      Step4(出队2)
1  (0,  -1)       (0, -1)            (0,-1)keep       (0,-1)            (0,-1)kepp  这里只是1的0太小,否则又会被入队
2  (INF,-1)   min(INF,0+5)=(5,1)     (5,1)       min(5, 1+3)=(4,3)      (4,3)       从而打会BF的O(nm)
3  (INF,-1)   min(INF,0+3)=(3,1)     (3,1)            (3,1)             (3,1)
q  [1]            [2,3]               [3]              [2]                []
一个图如果能实现刚让一个点出队后，找下一个能更新的点时, 再让刚出队的点进去就能把spfa打回bellma-ford */
代码:
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;  // 0为NULL,One Index;
void add(int from, int to, int x) { idx++, e[idx] = to, w[idx] = x, ne[idx] = h[from], h[from] = idx; }
int n, m, dist[N], st[N];

// 这个st的作用是如果"结点i"在queue中,那st[i]=1,避免重复入队
int spfa(int s) {
    int dist[N], st[N] = {0};
    memset(dist, INF, sizeof(dist));
    queue<int> q;
    q.push(s), st[s] = 1;  //  入队标记
    dist[s] = 0;
    while (q.size()) {
        int from = q.front();
        q.pop(), st[from] = 0;  // 出队删标记
        for (int i = h[from]; i != 0; i = ne[i]) {
            int to = e[i], d = w[i];          // from--(d)-->to
            if (dist[from] + d < dist[to]) {  // TODO Spfa不是bf的改良吗? 为什么这里不需要备份
                dist[to] = dist[from] + d;
                if (st[to] == 0) q.push(to), st[to] = 1;
            }
        }
    }
    return dist[n] > INF / 2 ? INF : dist[n];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int from, to, x;
        scanf("%d %d %d", &from, &to, &x);
        add(from, to, x);
    }
    // // for debug
    // for (int i = 1; i <= n; i++) {
    //     printf("%d: ", i);
    //     for (int j = h[i]; j != 0; j = ne[j]) printf("(%d,%d)=>", e[j], w[j]);
    //     puts("");
    // }

    int result = spfa(1);
    printf("%s", result == INF ? "impossible" : to_string(result).c_str());


    return 0;
}
/* Spfa 是 BellmanFord的改良版
只有当一个结点的最短距离变小了,它原本的邻居才有可能通过它缩短距离∴我们不必像BF一样每一轮遍历所有的边,而是使用队列,只要谁的距离被更新了,就把谁丢到队里中, 只对队列中的结点进行拓展(链式前向星)更新
I:BellmanFord对所有的边都更新; Spfa仅对更新了更短距离的点更新
II: Spfa有一个队列存放那些"更新了更短距离的点",且同一时刻同一个结点仅能在队列中存在一个,但可以重复入队(不同时刻)用st[]判断  
III:是否需要备份数组?不需要!因为BF是遍历所有的边,导致i在更新后面i->j的边的时候i可能已经被z->i更新过了;而Spfa只更新i的出边,所以i是不可能被提前更新的;*/
// 时间复杂度: 平均O(m),因为只有当结点距离被更新时才会入队并遍历其出边,但在某些特殊图/数据下同一结点可能被反复入队,最坏可达O(nm)
// 空间复杂度: 链式前向星存m条边,dist/st数组和队列中最多n个结点=>O(n + m)


/* 1-(1)->2-(-1自环)->2-(4)->3 【O(∞)如果不判断负环终止的话】 
     INIT       Step1(出队1)        Step2(出队2)        Step3(出队3)      Step5(出队2)       Step...
1  (0, -1)       (0, -1)            (0, -1)             (0,-1)            (0, -1)          循环
2  (INF, -1)   min(INF,0+1)=(1,1) min(1,1-1)=(0,2)      (0, 2)         min(0,0-1)=(-1,2)   因为负环
3  (INF, -1)     (INF, -1)        min(INF,1+4)=(5,2)    (5, 2)         min(5,-1+4)=(3,2)   一直更新
q  [1]            [2]               [3,2]                [2]                [3,2]          一直入队 */

/* (1 2 5;1 2 4;1 2 3;1 2 2;1 2 1; 2 3 5;2 3 4;2 3 3;2 3 2;2 3 1)   【O(m)所有边入队一次】     
     INIT         Step1(出队1)        Step2(出队2)        Step3(出队3)    1-(5)->2-(5)->3
1  (0,  -1)       (0, -1)              (0,-1)             (0,-1)          (4)->  (4)->
2  (INF,-1)   min(INF,0+5)=(5,1)       (1, 1)             (1, 1)          (3)->  (3)->
              min(5,  0+4)=(4,1)                                          (2)->  (2)->
					...          										  (1)->  (1)->
     		  min(2,  0+1)=(1,1)
3  (INF,-1)        (INF,-1)         min(INF,1+5)=(6,2)    (2,2)
									min(6  ,1+4)=(5,2)
							                ....
									min(3  ,1+1)=(2,2)
q  [1]            [2]                   [3]                 []               */

/*1 3 3;1 2 5;2 1 1;3 2 1 【O(nm)菊花图】
     INIT       Step1(出队1)        Step2(出队2)      Step3(出队3)      Step4(出队2)      
1  (0,  -1)       (0, -1)            (0,-1)keep       (0,-1)            (0,-1)kepp  这里只是1的0太小,否则又会被入队      
2  (INF,-1)   min(INF,0+5)=(5,1)     (5,1)       min(5, 1+3)=(4,3)      (4,3)       从而打会BF的O(nm)
3  (INF,-1)   min(INF,0+3)=(3,1)     (3,1)            (3,1)             (3,1)
q  [1]            [2,3]               [3]              [2]                []          
一个图如果能实现刚让一个点出队后，找下一个能更新的点时, 再让刚出队的点进去就能把spfa打回bellma-ford */           
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;  // 0为NULL,One Index;
void add(int from, int to, int x) { idx++, e[idx] = to, w[idx] = x, ne[idx] = h[from], h[from] = idx; }
int n, m, dist[N], st[N]; // 这个st的作用是如果"结点i"在queue中,那st[i]=1,避免重复入队
int spfa(int s) {
    int dist[N], st[N] = {0};
    memset(dist, INF, sizeof(dist));
    queue<int> q;
    q.push(s), st[s] = 1;  //  入队标记
    dist[s] = 0;
    while (q.size()) {
        int from = q.front();
        q.pop(), st[from] = 0;  // 出队删标记
        for (int i = h[from]; i != 0; i = ne[i]) {
            int to = e[i], d = w[i];          // from--(d)-->to
            if (dist[from] + d < dist[to]) { 
                dist[to] = dist[from] + d;
                if (st[to] == 0) q.push(to), st[to] = 1;
            }
        }
    }
    return dist[n] > INF / 2 ? INF : dist[n];
}// 调用处: int result = spfa(1); printf("%s", result == INF ? "impossible" : to_string(result).c_str());
注意:
  1. 什么样例能使得Spfa退化为BF? 【菊花图】参考
#include <bits/stdc++.h>

using namespace std;

int main() {
    int seed;
    seed = time(NULL);
    srand(seed);
    // int n=rand()%1000,m=n*2-2;
    int n = 3, m = n * 2 - 2;
    printf("%d %d\n", n, m);
    for (int i = n; i >= 2; --i) printf("1 %d %d\n%d %d 1\n", i, (n - i + 1) * 2 + 1, i, i - 1);
}
心得:
首次编辑时间: 2023年9月24日00:32:31
手写队列卡半天,服气了!
每日一题:

4.4 Floyd

第五章 最小生成树

5.1 Prim

思路:
  • STEP1:
  • STEP2:
代码:
// Prime (Point选点)
#include <iostream>
#include <queue>
#define pii pair<int, int>


using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;          // INF用于标记是否有MST;
int h[2 * N], e[2 * N], ne[2 * N], w[2 * N], idx;  // 无向图, 开两倍
void add(int from, int to, int x) { idx++, e[idx] = to, w[idx] = x, ne[idx] = h[from], h[from] = idx; }
int n, m;

int prime(int s) {
    int st[N] = {0}, cnt = 0, mst = 0;                  // MST的定义,每个结点经过一次,且仅经过一次
    priority_queue<pii, vector<pii>, greater<pii>> pq;  // <value,to>
    pq.push({0, s});
    while (pq.size()) {
        int from = pq.top().second, d = pq.top().first;
        pq.pop();
        if (st[from]) continue;
        st[from] = 1, cnt++, mst += d;
        for (int i = h[from]; i != 0; i = ne[i]) pq.push({w[i], e[i]});
    }
    return cnt == n ? mst : INF;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int from, to, x;
        scanf("%d %d %d", &from, &to, &x);
        add(from, to, x), add(to, from, x);
    }
    // for (int i = 1; i <= n; i++) {
    //     printf("%d: ", i);
    //     for (int j = h[i]; j != 0; j = ne[j]) printf("(%d,%d)=>", e[j], w[j]);
    //     puts("");
    // }
    int result = prime(1);
    printf("%s", result == INF ? "impossible" : to_string(result).c_str());

    return 0;
}
注意:

1.

心得:
每日一题:

5.2 Kruskal

第六章 二分图

6.1 判断二分图(染色法)

6.2 二分图的最大匹配(匈牙利算法)

  • Title: 3.搜索与图论
  • Author: 明廷盛
  • Created at : 2026-03-09 09:50:45
  • Updated at : 2026-03-07 08:53:00
  • Link: https://blog.20040424.xyz/2026/03/09/🏫考研/第二部分 算法基础课/3.搜索与图论/
  • License: All Rights Reserved © 明廷盛
On this page
3.搜索与图论
  1. 第一章 DFS
    1. 1.1 排列数字
    2. 1.2 n皇后问题
    3. 1.3 树的重心
  2. 第二章 BFS
    1. 2.1 走迷宫
    2. 2.2 八数码
    3. 2.3 岛屿数量
    4. 2.4 图中点的层次
  3. 第三章 拓扑排序
    1. 3.1 拓扑排序
  4. 第四章 最短路
    1. 4.1 Dijkstra
    2. 4.2 Bellman-Ford
    3. 4.3 Spfa最短路
    4. 4.4 Floyd
  5. 第五章 最小生成树
    1. 5.1 Prim
    2. 5.2 Kruskal
  6. 第六章 二分图
    1. 6.1 判断二分图(染色法)
    2. 6.2 二分图的最大匹配(匈牙利算法)