DFS

排列数字

#include <iostream>

using namespace std;

const int N = 10;

int path[N];
bool st[N];
int n;

void DFS(int x)
{
    if(x == 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[x] = i;
            st[i] = true;
            DFS(x + 1);
            st[i] = false;//恢复现场
        }
    }
}

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

    DFS(0);

    return 0;
}

n-皇后问题

对角线 $dg[u + i]$，反对角线 $udg[n − u + i]$ 中的下标 $u + i$ 和 $n − u + i$ 表示的是截距 $y = x + b$ 和 $y = - x + b$
要保证是正的，所以要加 $n$

#include <iostream>

using namespace std;

const int N = 20;

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

void dfs(int u)
{
    if(u == n){
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++)
                cout << g[i][j];
            cout << endl;
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < n; i ++){
        if(!col[i] && !dg[u + i] && !udg[i - u + n]){//第 r 行，第 i 列 是否放皇后
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[i - u + n] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[i - u + n] = false;
            g[u][i] = '.';
        }
    }
}

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

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

    return 0;    
}

BFS

走迷宫

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

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];//g存储地图，d标记到搜索到的点

int bfs()
{
    queue<PII> 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 < n && x >= 0 && y < m && y >= 0 && 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;
}

八数码

将 $3 * 3$矩阵转成字符串
队列可以用 queue<string>,直接存转化后的字符串
dist数组用 unordered_map<string, int>,将字符串和数字联系在一起，字符串表示状态，数字表示距离

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string start)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);
    d[start] = 0;

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

    string end = "12345678x";

    while(q.size()){
        auto t = q.front();
        q.pop();
        //记录当前状态的距离，如果是最终状态则返回距离
        int distance  = d[t];

        if(t == end) return distance;
        //查询x在字符串中的下标，然后转换为在矩阵中的坐标
        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for(int i = 0; i < 4; i ++){
            int a = dx[i] + x, b = dy[i] + y;
            if(a >= 0 && a < 3 && b < 3 && b >= 0){
                swap(t[a * 3 + b], t[k]);
                //如果当前状态是第一次遍历，记录距离，入队
                if(!d.count(t)){
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }  
    }

    return -1;
}

int main()
{
    char s[2];
    string start;

    for(int i = 0; i < 9; i ++){
        cin >> s;
        start += *s;
    }

    cout << bfs(start) << endl;

    return 0;
}

树和图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边 $ab$ ，存储两条有向边 $a->b, b->a$ 。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：$g[a][b]$ 存储边 $a->b$

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;//ne和h都存的是下标，只有e里才会存代表实际的值
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

时间复杂度 $O(n+m)$, $n$ 表示点数，$m$ 表示边数

深度优先遍历 —— 树的重心

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    /*数组是一个存储头结点的数组，我们给定一个节点1，那么在h[1]指向的这条链表上，
    都是与节点1相邻的节点（即距离为1）*/
    {
        int j = e[i];
        if (!st[j]) dfs(j);//递归后相当于沿着一个点一直往下走
    }
}

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

using namespace std;

const int N = 200010;

int ans = N;
int h[N], e[N], ne[N], idx;
bool st[N];
int n;

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

int dfs(int u)
{
    st[u] = true;//标记访问过u节点

    int res = 0;//存储删掉某个节点之后，最大的连通子图节点数
    int sum = 1;//存储以u为根的树的节点数, 包括u
    for(int i = h[u]; i != -1; i = ne[i]){//访问u的每个子节点
        int j = e[i];//i是头结点下标，然后依次遍历，e里存的是边
        /*j = e[i];i=h[u];由add函数可知，h[u]=idx;又 e[idx] = b;
        所以j=e[i]=e[h[u]]=e[idx]=b由add函数定义可知 b为a的相邻节点
        */
        //相当于往外走一步
        if(!st[j]){
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }

    }

    res = max(res, n - sum);
    ans = min(ans, res);

    return sum;
}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);

    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;

}

宽度优先遍历 —— 图中点的层次

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

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

    for (int i = h[t]; i != -1; i = ne[i])//这条链表上都是距离头结点为1的点
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

层次遍历的思想,是当每次pop出队时，将与它距离为1的节点全部加到队列中

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int h[N], d[N], e[N], ne[N], idx;
bool st[N];

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

int bfs()
{
    memset(d, -1, sizeof d);
    queue<int> q;
    d[1] = 0;
    q.push(1);

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

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;// 因为路径长度都是1，所以直接在上一步的基础上加上1即可
                q.push(j);
            }
        }
    }

    return d[n];// 返回的d[n]即是节点1到节点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;
}

拓扑排序 —— 有向图的拓扑序列

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

    // d[i] 存储点i的入度
    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];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

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

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

using namespace std;

const int N = 1e5 + 10;

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

int 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] == 0)
            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] --;
            if(d[j] == 0)
                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 < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }

    if(!topsort()) cout << "-1" << endl;
    else 
    {
        for(int i = 0; i < n; i ++)
            cout << q[i] << " " ;
        cout << endl;
    }

    return 0;
}

最短路径

朴素dijkstra算法 —— Dijkstra求最短路 I

时间复杂是 $O(n^2+m)$, $n$ 表示点数，$m$ 表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

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

堆优化版dijkstra —— Dijkstra求最短路 II

时间复杂度 $O(mlogn)$ , $n$ 表示点数，$m$ 表示边数
堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。

1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为：
   弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
   用该点更新临界点的距离，若更新成功就加入到堆中。

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
    /* 
    这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离
    其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    */
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

Bellman-Ford算法 —— 有边数限制的最短路

时间复杂度 $O(nm)$, $n$ 表示点数，$m$ 表示边数
假设 $1$ 号点到 $n$ 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 $n-1$ 次操作，若图中不存在负环，则 $1$ 号点一定会到达 $n$ 号点，若图中存在负环，则在 $n-1$ 次松弛后一定还会更新

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

using namespace std;

const int N = 510, M = 10010;

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

int n, m, k;
int dist[N];
int backup[N];
/*backup[] 数组是上一次迭代后 dist[] 数组的备份
由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，
若不进行备份会因此发生串联效应，影响到下一个点*/

void bellam_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for(int i = 0; i < k; i ++)//保证第k次时，dist[n]是走过k步及以内的最短路
    {
        memcpy(backup, dist, sizeof dist);

        for(int j = 0; j < m; j ++){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.c);//用已确定最短路的点向外延申，类似于dijkstra
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    bellam_ford();
    /*是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，
    而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，
    dist[n]大于某个与INF相同数量级的数即可*/
    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << dist[n];

    return 0;
}