算法基础笔记（Acwing）（三）—— 搜索与图论

搜索与图论

• 一. 树与图的存储( h[1]存放的便是 指向第一个节点的节点)
• 二. 树与图的遍历
• 1. DFS
• • 1. 排列数字
  • 2. n-皇后问题
  • • 1. 按行遍历（相当于剪枝）
    • 2. 按每个元素遍历（没有减枝）
    • • 补充，递归应该先把结束条件 写在前面
• 2. BFS（队列）
• • 例题1. 走迷宫
  • • 就是一个循环
  • 例题2. 八数码
  • • *****思想
• 3. 树与图的深度优先遍历
• • 深度搜索的顺序
  • • 例题，树的重心（在深搜模板上，改一改）
• 4. 树与图的广度优先遍历
• • 图中点的层次
  • • 1. 一个点连接的是 连接它的 点
    • • 并且先连接的 后遍历
    • 2. 处理的时候，根节点的距离直接等于0 因为其实遍历不到根节点
• 三. 拓扑排序
• 5. 拓扑排序（是否有环，用最后删除所有入度后，是否都入队）
• • 有向图的拓扑序列
  • • ***思想***
• 四. 朴素dijkstra算法
• 五. 堆优化版dijkstra
• 6. Dijkstra搜索
• • 6. Bellman-Ford算法
  • 7. spfa 算法（队列优化的Bellman-Ford算法）
  • 8. spfa判断图中是否存在负环
  • 9. floyd算法
  • 10. 朴素版prim算法
  • 11. Kruskal算法
  • 12. 染色法判别二分图
  • 13. 匈牙利算法

一. 树与图的存储( h[1]存放的便是 指向第一个节点的节点)

存储顺序（先指向的，后打印）

存储节点 h【1】存放的便是 指向第一个节点的节点

二. 树与图的遍历

1. DFS 1. 排列数字

原题链接

思想：

1. 每次遍历函数中，一个函数对应的是 一个数据位
2. 在这个遍历位置中，需要遍历的是 每个数据

#include
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)//u表示的是 第几个坑位
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯，取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
}

2. n-皇后问题

原题链接

1. 按行遍历（相当于剪枝）

思想：

1. 每次递归中，遍历一行的元素，如果可以放皇后，就递归到下一行，下一行中不行了，就返回来，回溯，

#include 
using namespace std;
const int N = 20;//对角线元素 2n-1 取20防止越界 
int n;

char g[N][N]; //存储图
bool col[N], dg[N], udg[N]; //udg 副对角线 /

//英语单词 column 列   diagonal 主角线  


void dfs (int x) { 
        if (x == n) {
            for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                    cout << g[i][j];
                }
                cout << endl;
            }
            cout << endl ;
            return;
        }
    //x:行  y:列
    for (int y = 0; y < n; y ++) {
        //按行枚举 因为每一行都需要放皇后 相当于剪枝了
        // 剪枝(提前判断当前方案已经错误，不再继续往下搜索，提高算法效率) 
        // 判断皇后能否放在这格  
        if (!col[y] && !dg[x + y] && !udg[n - x + y]) {
            g[x][y] = 'Q'; 
            col[y] = dg[x + y] = udg[n - x + y] = true;

            dfs(x + 1);//找下一层的

            //回溯的时候 记得恢复现场 
            col[y] = dg[x + y] = udg[n - x + y] = false; 
            g[x][y] = '.';
        }
    }
}

int main () {
    cin >> n;
    for (int i = 0; i < n;i ++) {
        for (int j = 0; j < n; j ++) {
            g[i][j] = '.'; //初始化全部空格子
        }
    }
    dfs(0); //从第一行开始找[0:下标]

    return 0;
}

2. 按每个元素遍历（没有减枝）

思想：

1. 什么时候成功，当然是把 皇后都放好，并且全部遍历完，也就是行要超出范围的，才算 全部遍历完
2. 所以先把判断

#include 

using namespace std;

const int N = 10;

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

void dfs(int x, int y, int s)
{
    if (y == n) y = 0, x ++ ;

    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    g[x][y] = '.';
    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;

    dfs(0, 0, 0);

    return 0;
}

补充，递归应该先把结束条件 写在前面 2. BFS（队列） 例题1. 走迷宫 就是一个循环

思想：

1. 用pair 表示一个点的坐标
2. 用队列进行深度优先搜索
3. 用两个数组，表示前进的路线 dx -1 0 1 0 dy 0 -1 0
4. g[][]存放地图
   b[][]用于表示距离（并且用于判断是否走过）。并且遍历的点，等于上一个点的距离+1
5. 初始化时，所有点的距离都是-1用于判断，然后第一个为0，用于计算距离
6. 操作就是根据父结点，然后子节点进队，出队

原题链接

#include 
#include 
#include 
#include 

using namespace std;

typedef pair PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue q;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        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.push({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;

    return 0;
}

例题2. 八数码

原题链接

*****思想

1. 转成字符串（利于比较）
2. 哈希表存储，我要存储每个情况，是由第一个情况 移动多少次，转换过来的
3. 用队列存储字符串，宽搜原理，（一层一层的来）（while里面由for，for里面有入队列）
4. 行数是 k / 3 列数是 k % 3（看 / 和 %取值范围就知道了）
5. 入队的时候，不管入不入队列，都要恢复到父节点的，因为还需要通过父节点遍历兄弟节点
   

3. 树与图的深度优先遍历 深度搜索的顺序

例题，树的重心（在深搜模板上，改一改）

原题链接

解析：

1. 在递归模板中，深度递归，应用于本题，每次递归需要返回当前节点对应下面有多少个子节点
   并且记录一下，最大的连通图的数目
   并且记录一下，本节点对应孩子的数目用于下次比较
2. 在递归链表外，统计本节点对应 父节点的连通数

4. 树与图的广度优先遍历

图中点的层次 1. 一个点连接的是 连接它的 点 并且先连接的 后遍历 2. 处理的时候，根节点的距离直接等于0 因为其实遍历不到根节点

原题链接

#include 
#include 

using namespace std;

const int N=1e5+10;

int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离  d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点

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; //0号节点是编号为1的节点

    memset(d,-1,sizeof d);

    d[1]=0; //存储每个节点离起点的距离

    //当我们的队列不为空时
    while(hh<=tt)
    {
        //取出队列头部节点
        int t=q[hh++];

        //遍历t节点的每一个邻边
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //如果j没有被扩展过
            if(d[j]==-1)
            {
                d[j]=d[t]+1; //d[j]存储j节点离起点的距离，并标记为访问过
                q[++tt] = j; //把j结点 压入队列
            }
        }
    }

    return d[n];
}

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

    cout< 
三. 拓扑排序 
 
5. 拓扑排序（是否有环，用最后删除所有入度后，是否都入队） 
有向图的拓扑序列 
原题链接
 1. 入度 出度的概念
 
 
 
***思想*** 
 
 
取出入度为0的点，开始遍历
 1.1 遍历子节点，每个入度-1，判断为0时入队
 （一定都会入队的，否则就是出现环了，因为正常应该是树的结构）
队列从 0开始存储，入队和出队都要进行，用于判断结束标志
 
 
#include
#include
#include
using namespace std;

const int N=100010;
int h[N],e[N],ne[N],idx;
int n,m;
int q[N],d[N];//q表示队列,d表示点的入度

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
     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]--;//删除点t指向点j的边
            if(d[j]==0)//如果点j的入度为零了,就将点j入队
            q[++tt]=j;
        }
    }
    return tt==n-1;
    //表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof(h));//如果程序时间溢出，就是没有加上这一句
    for(int i=0;i
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);//因为是a指向b,所以b点的入度要加1
        d[b]++;
    }
    if(topsort()) 
    {
        for(int i=0;i 
四. 朴素dijkstra算法 
 
五. 堆优化版dijkstra 
 
6. Dijkstra搜索 
6. Bellman-Ford算法 
 
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}
 
7. spfa 算法（队列优化的Bellman-Ford算法） 
 
8. spfa判断图中是否存在负环 
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
 
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        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;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}
 
9. floyd算法 
 
10. 朴素版prim算法 
 
11. Kruskal算法 
 
12. 染色法判别二分图 
 
13. 匈牙利算法 
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
 
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

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 res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}