图论

稠密图用邻接矩阵存，稀疏图用邻接表存

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//建边
// 对于每个点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 ++ ;
}

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

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

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

几个要素：图中的值，各数组下标，边的编号

h[i]:i是图中的值a，h[i]是这个值在e[i]中的下标i

e[i]:i是数组下标，e[i]是图中的值b，由此实现了a->b

ne[i]:i是数组下标,ne[i]是e[i]对应的下一个数组下标

嗯……要好好理解

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

应用：

  • 拓扑排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    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;
    }

  • ACWing845. 八数码

    有状态转移思想应用（妙啊）

    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
    int bfs(string start){
        string end = "12345678x";//定义目标状态
        queue<string> q;
        unordered_map<string,int> d;//O(1)
        
        q.push(start);
        d[start] = 0;
        
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        
        while(q.size()){
            auto t = q.front();
            q.pop();
            
            int dis = d[t];
            if(t == end) return dis;
            
            int k = t.find('x');
            int x = k / 3;
            int y = k % 3;
            
            for(int i = 0;i < 4;i++){
                int a = x + dx[i],b = y + dy[i];
                if(a >= 0 && a<3 && b >= 0 && b < 3){
                    swap(t[k],t[a*3 + b]);
                    
                    if(!d.count(t)){
                        d[t] = dis + 1;
                        q.push(t);
                    }
                    swap(t[k],t[a*3 + b]);//还原状态
                }
            }
        }
        return -1;
    }

朴素dijkstra算法

  1. 初始化距离

    dis[1] = 0，dis[i] = +∞

  2. 找到当前已经确定最短距离的点，s:当前已经确定最短距离的点

    for(i:1~n)

    t:不在s中的，距离最近的点

    t->s

    更新距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dijsktra()
{
    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;
            }
        }
        
        for(int j = 1;j <= n;j++){//更新这个点和其他所有点的距离
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        }
        
        st[t] = true;
    }
    
    if(dist[n] >= 10010) return -1;
    else return dist[n];
}

堆优化

  1. 初始化距离

    dis[1] = 0，dis[i] = +∞

  2. 找到当前已经确定最短距离的点，s:当前已经确定最短距离的点

    t:不在s中的，距离最近的点

    t->s（m条边）

    更新距离（堆更新一次是O(logn)）

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
void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];//存的是h[a]之前的数的idx,这样可以访问到所有a->x的边
    h[a] = idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;//默认的是按照pair的第一个元素进行排序
    heap.push({0,1});// 可以简写成 q.emplace(x, y)
    
    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]){//找到和ver相连的边的最小的那一条
            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] >= 1000000010) return -1;
    else return dist[n];
}

Bellman-Flord

  1. 建结构体a,b,w

  2. for n次（迭代k次：从1号点经过不超过k条边到每个点的最短路的距离，若一次迭代没有点更新可直接结束）

    ​ for 所有边a,b,w

    ​ 更新距离(松弛)

一定满足dis[b] <= dis[a] + w

如果有负权回路——一圈长度和小于0，就不一定有结果；若第n次还在迭代的话就有负环（一般用SPFA找）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
        }
    }
}

串联：由于这个算法的特性决定，每次更新得到的必然是在多考虑 1 条边之后能得到的全局的最短路。

而串联指的是一次更新之后考虑了不止一条边：由于使用了松弛，某节点的当前最短路依赖于其所有入度的节点的最短路；

假如在代码中使用dist[e.b]=min(dist[e.b],dist[e.a] + e.c);，我们无法保证dist[e.a]是否也在本次循环中被更新，如果被更新了，并且dist[e.b] > dist[e.a] + e.c，那么会造成当前节点在事实上**“即考虑了一条从某个节点指向a的边，也考虑了a->b”，共两条边。**

而使用dist[e.b]=min(dist[e.b],last[e.a] + e.c);，可以保证a在dist更新后不影响对b的判定，因为后者使用last数组，保存着上一次循环中的dist的值。

SPFA

要求没有负环

第一个点入队

while queue不空

​ t <- q.front;q.pop();

​ 更新t的所有出边（t->b）

​ queue<-b;

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
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    //队列里都是由起点更新到的点，不存在bellman-ford算法中未更新的点同样被边更新的情况。
    {
        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];
}

判断负环

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
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];//dist严格意义说不是用来存最短距离的。所以dist中元素初始值并不是那么重要。我们就拿dist中元素全部初始化为0来举例分析一下，如果图中全部是正权重，那么if就压根不会执行。cnt也不会更新。如果图中全是负权重，但没有负环，其实就跟求最短路比较类似了，但dist存的也不完全是源点1到各个点的最短距离，这里有这么两种情况(比如1->2,1->3,2->3,这时dist中元素就代表了源点1到各点的最短距离，因为如果这样，2,3开始不入队迟早也会入队，这样就退化成了，只开始入队1，其他点不入队的情况，算的是1到各点的最短距离。另外一种是可能存在1->3,2->3,1到不了2，这样此时dist[3]，就代表了1,2分别为起点到3的最短距离。如果存在连通分支的情况其实就是前面两个情况的结合。)第一种情况很显然就跟单源最短路一样，不存在负环的前提下最短路径的长度也就是n-1，一旦大于等于n就说明有负环。第二种情况可以把例如3这个点分别看成以1为源点，以2为源点求最短路。此时cnt代表的就是两个求最短路的过程中dist的更新次数。如果有n个点，1->n,但到不了2,2->n，但1可以到其他所有点，这样就变成以1为源点和以2为源点最短路，以1的角度看就是n-1个点的最短路，在这个最短路中cnt最多达到n-2，同样2->n最短路中cnt最多是1，相加也最对是n-1。类似的分析，如果1到不了很多点，可以看成多个最短路，在每个最短路中看cnt最大值，综合所有cnt更新会发现cnt最大也就是n-1(在没有负回路的前提下)有不同联通分支分析与第二种情况分析类似。
//如果既有负权重，又有正权重，对于dist全初始为0的情况来说，正权重其实就起不到作用，这里可以认为正权重的边不存在。把正权重的边删掉后，就又变成了全部是负权重的情况。回到了上面的分析。综上，如果回路中不存在负回路，那么cnt最多也就是n-1，只有存在负权重，cnt才会大于等于n
//所以结合上述分析，我们可以知道cnt[j]各个起源点到j点的最短长度的和
bool st[N];

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

bool spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        st[i] = true;
        q.push(i);
    }//这里是因为如果和正常的spfa一样的话，只能判断从源点1可以到达所有的点的路径中有没有负环。但如果源点有到不了的点，比如不在一个联通分支，这样就会有点不会入队，这样就没法判断这个点到其他点的路径中是否存在负环，即也无法判断图中是否有负环，所以开始让所有点都入队

    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];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

Floyd

for(k =1;k<=n;k++)

​ for(i =1;i<=n;i++)

​ for(j =1;j<=n;j++)

​ d[i,j] = min(d[i,j],d[i,k] + d[k,j]);

d[i,j]存的就是最短路长度

1
2
3
4
5
6
7
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]);
}

拓扑排序

找到图中入度为 0 的节点，以及仅由入度为 0 节点所指向的节点。

LC802

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
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        // 反图，邻接表存储
        vector<vector<int>> new_graph(n);
        // 节点入度
        vector<int> Indeg(n, 0);

        for(int i = 0; i < n; i++) {
            for(int x : graph[i]) {
                new_graph[x].push_back(i);
            }
            // 原数组记录的节点出度，在反图中就是入度
            Indeg[i] = graph[i].size();
        }

        // 拓扑排序
        queue<int> q;

        // 首先将入度为 0 的点存入队列
        for(int i = 0; i < n; i++) {
            if(!Indeg[i]) {
                q.push(i);
            }
        }

        while(!q.empty()) {
            // 每次弹出队头元素
            int cur = q.front();
            q.pop();

            for(int x : new_graph[cur]) {
                // 将以其为起点的有向边删除，更新终点入度
                Indeg[x]--;
                if(!Indeg[x]) q.push(x);
            }
        }

        // 最终入度（原图中出度）为 0 的所有点均为安全点
        vector<int> ret;
        for(int i = 0; i < n; i++) {
            if(!Indeg[i]) ret.push_back;
        }
        return ret;
    }
};

最短路问题