算法-图论

———————————————————–还没整理好——————————————————————————–

图论有哪些部分？

1
2
3
4
5
6
7
8
9
10
1、 深度优先搜索  DFS
2、 宽度优先搜索  BFS
3、 树与图的存储
4、 树与图的深度优先遍历
5、 树与图的宽途优先遍历
6、 拓扑排序
7、 单源最短路径
8、 多源最短路径
9、 最小生成树
10、二分图

DFS 和 BFS

数据结构 空间 特点
DFS stack O(h) 不具有最短性
BFS queue O(2^h) 最短路径


DFS例题

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

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

输入格式

共一行，包含一个整数 n。

输出格式

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

数据范围

1 ≤ n ≤ 7

输入样例：

1
3

输出样例：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
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 ++ ) cout << path[i] << " ";
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i ++ )
    {
        if (st[i]) continue; // 如果数字 i 已经被使用，跳过当前循环
        path[u] = i;
        st[i] = true;
        dfs(u + 1);
        st[i] = false;
    }

}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}

n-皇后问题

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

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

输入格式

共一行，包含整数 n。

输出格式

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

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

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

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

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

数据范围

1 ≤ n ≤ 9

输入样例：

1
4

输出样例：

1
2
3
4
5
6
7
8
9
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

方法一、已知每一行就一个皇后，不需要每个格子都遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>

using namespace std;

const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[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;
}

我们检查棋盘是按行来检查的，其中u就是控制棋盘的行，i是控制列的。

(u, i)就是棋盘中的坐标，在一条对角线上 u + i 的值是不变的，所以只要有一个u + i 设置为true，那么就表示这条对角线已经有皇后了。

同理，反对角线的值都是n - u + i…

按照格子枚举

一行行的遍历 ，到头之后再设置到新的 一行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool row[N], col[N],dg[N], udg[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;
}

BFS

所有边的权重都是1的时候，才用BFS

例题

给定一个 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

输入样例：

1
2
3
4
5
6
5 5
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

输出样例：

1
8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 110;

typedef pair<int, int> PII;

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

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 >= 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;
}


树与图的深度优先遍历

无向图是一种特殊的有向图，搞两条边就可以了

有向图：邻接矩阵(二维数组)、邻接表(单链表)



树与图的广度（宽度）优先遍历



拓扑排序

有向无环图—>拓扑图
分为入度和出度，如果入度为0，说明没有任何点指向当前节点，就是把所有入度为0的点入队

1
2
3
4
5
6
7
8
while que
{
	t = 队头;
	枚举t的所有出边t->j
	删掉t->j, d[j] -- ;
	if d[j] = 0
		d[j]入队
}


最短路

1️⃣ 单源最短路

1、所有边权都是整数（朴素Dijkstra算法 O(n²) 堆优化版的Dijkstra算法 O(mlogn)）

例题

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

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

数据范围

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

输入样例：

1
2
3
4
3 3
1 2 2
2 3 1
1 3 4

输出样例：

1
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    
    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];
            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 -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    printf("%d\n", dijkstra());
    
    
    return 0;
}
2、存在负权边（Bellman-Ford O(nm) SPFA O(m), 最坏O(nm)）

例题

给定一个 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。

输入样例：

1
2
3
4
3 3 1
1 2 1
2 3 1
1 3 3

输出样例：

1
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstring>
#include <iostream>
#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 last[N];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

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

2️⃣ 多源最短路

​ Floyd算法 O(n³)

朴素Dijkstra算法（不能存在负权边）

1️⃣ dist[1] = 0, dist[i] = +♾️ s:当前 已经确定最短距离的点

2️⃣ for(i: 0 - n)

​ t<-不在s中的，距离最近的点

​ s<-t 用t更新其它点的距离

稠密图：邻接矩阵 稀疏图：邻接表

使用有向图的方法解决无向图的问题

堆优化版的Dijkstra算法

存储方式改成邻接表的形式

Bellman-Ford算法 （有负环 可以用这个）

​ for() n次

​ for（所有边） a, b w w是 a-> b 的距离

​ dist[b] = min (dist[b], dist[a] + w);

三角不等式 ：dist[b] <= dist[a] + w

​

SPFA算法（没有负环就可以用这个）

把起点放到队列里面去

while queue不空

​ 1️⃣ t<-q.front;

​ q.pop();

​ 2️⃣更新t的所有出边 t->（W） b

​ queue<-b

dist[N]最短距离

cnt[N] 边数

dist[x] = dist[t] + w[i];

cnt[x] = cnt[t] + 1;

cnt[x] >= n; 经过了n + 1个点

求最短路径

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

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

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

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

数据范围

1≤n,m≤10^5，
图中涉及边长绝对值均不超过 10000。

输入样例：

1
2
3
4
3 3
1 2 5
2 3 -3
1 3 4

输出样例：

1
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size())
    {
        int 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];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    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 printf("%d\n", t);
    
    return 0;
}

Floyd算法

邻接矩阵来存储

1
2
3
4
5
6
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最短的长度

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

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

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

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

接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

1≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：

1
2
3
4
5
6
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

1
2
impossible
1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

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

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]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    
    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;
    // 边读入  以及   邻接矩阵更新      
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    
    floyd();
    
    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        
        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }
    
    return 0;
}

最小生成树

1️⃣ Prim算法

​ 稀疏图：朴素版 O(n²)

​ 稠密图：堆优化版 O(mlogn)

1
2
3
4
5
dist[i]<- +♾️
for(int i = 0; i < n ; i ++ )
    t<- 找到集合外距离最近的点      // 一共n次操作   这步就是O(n)
    用 t 更新其它点到集合的距离
    st[t]  = true;

2️⃣克鲁斯卡尔算法（Kruskal） O(mlogm)

一般来说 ，稠密图 朴素版Prim算法 稀疏图 克鲁斯卡尔算法

	现将所有边按照权重从小到大排序O(mlogm)

​

​ 枚举每条边 a, b 权重 c O(m)

​ if(a, b)不连通

​ 将这条边加入集合

二分图

就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。（不一定是连通图）

1️⃣ 染色法 O(m + n)

判断是不是二分图 当且仅当途中不含奇数环（边的数量是奇数）

对每一个点进行染色操作，只用黑白两种颜色；

  • 💡如果图中存在奇数环（构成环的顶点数量是奇数），那一定不是二分图），下图可以看到，依次选一个点，进行染色（原则是相邻的点要染于该点不同色），奇数环的染色结果会出现矛盾。；【必要性】

在这里插入图片描述

💡如果不含奇数环，一定是二分图【充分性】
如果没有奇数环，那么剩下的点的关系就是：偶数环or单链。这两种情况都能保证同一条边上相邻顶点在不同集合中，所以也是成立的；

💡总结

用dfs和bfs两种方式去实现,对图进行遍历并染色；由于上面原理可知，二分图一定不含奇数环，不含奇数环的图一定为二分图

所以，只要在染色过程中不存在矛盾（这里用黑白进行染色，即一个点不能即为黑色，又为红色），整个图遍历完成之后，所有顶点都顺利染上色。就说明这是一个二分图！

2️⃣ 匈牙利算法 O(mn) 实际运行时间一般远小于O(mn)

什么是二分图的最大匹配？
💡匹配（本质是一个边的集合！）
给定一个二分图S，在S的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

💡极大匹配
极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。（也就是说，再加入任意一条不在匹配集合中的边，该边肯定有一个顶点已经在集合中的边中了）

💡最大匹配
所有极大匹配当中边数最大的一个匹配

💡最大匹配问题
选择这样的边数最大的子集称为图的最大匹配问题