《算法导论》读书笔记 PART 6

发布于 2020-02-25  203 次阅读


由于要做网络流专题,所以提早开始学习图论系列

第六部分:图算法

第22章基本的图算法

22.1 图的表示

1.直接存值

通过w[m] ,u[m],v[m]三个值来存储所有边,这种储存方式很简单,在一定情况下也很节省空间(没用重边的情况),但是寻找一条具体的边时需要O(m)m为边数的时间。或者可以封装成结构体

struct edge{
 int start,end,length;
};

2.使用临接矩阵

通过建立一个二维数组mp[n][n],然后把mp[i][j]的值看成从i到j的边的长度。空间复杂度为O(n^2),时间复杂度为O(1),对于顶点数小于10000的稠密图非常有用。

3.使用邻接链表(邻接表)

个人通常用vector来实现邻接表(十分好写),邻接表可以实现在O(n)的时间对边的查找,是SPFA算法的实现所必须的。

22.2广度优先搜索

广度优先搜索利用队列实现,实现对图的广度优先遍历,是基本算法之一

测试题目 hdoj 1253胜利大逃亡 ----一道很经典的三维广搜题

#include <cstdio>
#include<cstring>
#include<algorithm>
#include <iostream>
using namespace std;
struct node
{
    int x;
    int y;
    int z;
   // int t;
} queue[10000000];
int tail;
int biao[6][3]={{1,0,0},{0,1,0},{0,0,1},{-1,0,0},{0,-1,0},{0,0,-1}};
int a, b, c, t;
int head;
int map[51][51][51];
int book[51][51][51];
int time[51][51][51];
int main()
{
    int n;
    scanf("%d", &n);
    for (int q = 0; q < n; q++)
    {
        // int a,b,c;
        scanf("%d%d%d%d", &a, &b, &c,&t);
        for (int i = 0; i < a; i++)
            for (int j = 0; j < b; j++)
                for (int k = 0; k < c; k++)
                {
                    scanf("%d", &map[i][j][k]);
                    time[i][j][k]=999999;
                    book[i][j][k]=0;
                }
                head=0;
                tail=0;
        queue[tail].x=0;
        queue[tail].y=0;
        queue[tail].z=0;
        tail++;
        time[0][0][0]=0;
        book[0][0][0]=1;
        while(head^tail){
            for(int i=0;i<6;i++){
                if(queue[head].x+biao[i][0]>=0&&queue[head].x+biao[i][0]<a&&queue[head].y+biao[i][1]>=0&&queue[head].y+biao[i][1]<b&&queue[head].z+biao[i][2]>=0&&queue[head].z+biao[i][2]<c&&map[queue[head].x+biao[i][0]][queue[head].y+biao[i][1]][queue[head].z+biao[i][2]]==0&&book[queue[head].x+biao[i][0]][queue[head].y+biao[i][1]][queue[head].z+biao[i][2]]==0){
                    queue[tail].x=queue[head].x+biao[i][0];
                    queue[tail].y=queue[head].y+biao[i][1];
                    queue[tail].z=queue[head].z+biao[i][2];
                    book[queue[head].x+biao[i][0]][queue[head].y+biao[i][1]][queue[head].z+biao[i][2]]=1;
                    time[queue[head].x+biao[i][0]][queue[head].y+biao[i][1]][queue[head].z+biao[i][2]]=1+time[queue[head].x][queue[head].y][queue[head].z];
                    tail++;
                }
            }
            head++;
        }
        if(time[a-1][b-1][c-1]<=t){
            cout<<time[a-1][b-1][c-1]<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}

同时我们只需要在执行队列循环的时候将加入队列的节点输出,便可以得到图的广度优先树。

22.3深度优先搜索

深度优先搜索(后简称dfs),是通过层层递归,直到递归到深度极限,再向上回溯的算法,和bfs一样,dfs作为基本算法之一,广泛运用于竞赛领域。

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt = 0;
int book[20];
int dui[1000];
int dui2[1000];
vector<vector<int> > ans;
vector<int> tmp;
void dfs(int step)
{
    if (step == n + 1)
    {
        if (ans.size() < 3)
        {
            ans.push_back(tmp);
        }
        cnt++;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!book[i] && !dui[i - step + 500] && !dui2[i + step])
        {
            dui[i - step + 500] = 1;
            dui2[i + step] = 1;
            book[i] = 1;
            tmp.push_back(i);
            dfs(step + 1);
            tmp.pop_back();
            book[i] = 0;
            dui[i - step + 500] = 0;
            dui2[i + step] = 0;
        }
    }
    return;
}
int main()
{
    cin >> n;
    memset(book, 0, sizeof(book));
    dfs(1);
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < ans[i].size(); j++)
        {
            cout << ans[i][j] << ' ';
        }
        cout << endl;
    }
    cout << cnt << endl;
    return 0;
}

测试题目:luogu 八皇后 Checker Challenge

经过剪枝后还是很快的

22.4拓扑排序

拓扑排序是对有向无环图(DAG)里面的节点进行排序的方法,其思想是将没有边与其相连的点删去,然后删去与这个节点有关的所有边,最后不断重复这个操作,直至点集为空,如果这个时候还有边存在,就证明这是个有环图,不存在拓扑序。

求解拓扑序可以用基于dfs的kahn算法,时间复杂度为O(n+m)

int mp[510][510];
int book[510];
vector<int> ans;
int n, m;
bool dfs(int x)
{
    book[x] = -1;
    for (int i = n; i >= 1; i--)
    {
        if (mp[x][i])
        {
            if (book[i] == -1)
            {
                return false;
            }
            else
            {
                if (!book[i])
                {
                    dfs(i);
                }
            }
        }
    }
    book[x] = 1;
    ans.push_back(x);
    return true;
}
bool Toposort()
{
    ans.clear();
    memset(book, 0, sizeof(book));
    for (int i = n; i >= 1; i--)
    {
        if (!book[i])
        {
            if (!dfs(i))
                return false;
        }
    }
    reverse(ans.begin(), ans.end());
    return true;
}

测试题目hdoj 1285确定比赛名次 由于这道题要序号小的先输出,所以换用O(n^2)的模拟算法

#include <bits/stdc++.h>
using namespace std;
int book[510];
int mp[510][510];
int n, m;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("in.txt", "r", stdin);
    while (cin >> n >> m)
    {
        memset(mp, 0, sizeof(mp));
        memset(book, 0, sizeof(book));
        int u, w;
        for (int i = 0; i < m; i++)
        {
            cin >> w >> u;
            if (mp[w][u] == 0)
                book[u]++;
            mp[w][u] = 1;
        }
        int cnt = 0;
        vector<int> ans;
        while (cnt < n)
        {
            for (int i = 1; i <= n; i++)
            {
                if (book[i] == 0)
                {
                    book[i] = -1;
                    for (int j = 1; j <= n; j++)
                    {
                        if (mp[i][j])
                        {
                            mp[i][j] = 0;
                            book[j]--;
                        }
                    }
                    cnt++;
                    ans.push_back(i);
                    break;
                }
            }
        }
        for (int i = 0; i < n - 1; i++)
        {
            cout << ans[i] << ' ';
        }
        cout << ans[n - 1] << endl;
    }
    return 0;
}
在小范围的数据下还是可以接受的

22.5 LCA(强连通分量)

没找到题目测试,先咕了 (。ŏ_ŏ)

第24章:最小生成树

最小生成树问题是指,对于任意无向图,如何找到一组边(n-1条)让其所有节点在连接在一起,形成一棵树,并在此时使这些边的长度和最小

23.2Kruskal算法

Kruskal算法使用了贪心思想,先用并查集来维护连在一起的所有点的点集,每次检查最短的边,如果其能够将一个点加入点集或者合并两棵树,就将其加到边的总和里,最终实现将所有节点合并成一颗树。

时间复杂度mlog(n)

int n, m;
int date[10000];
struct edge
{
    int w, u, v;
    bool operator<(const edge a) const
    {
        return v < a.v;
    }
};
int find(int x)
{
    if (date[x] == x)
    {
        return x;
    }
    else
    {
        date[x] = find(date[x]);
        return date[x];
    }
}
void merge(int a, int b)
{
    int l = find(a);
    int r = find(b);
    if (l == r)
        return;
    else
        date[l] = r;
    return;
}
vector<edge> v;
int ans;
void Kruskal()
{
    sort(v.begin(), v.end());
    for (int i = 0; i <= n; i++)
    {
        date[i] = i;
    }
    for (int i = 0; i < v.size(); i++)
    {
        if (find(v[i].w) != find(v[i].u))
        {
            ans = v[i].v;
            merge(v[i].w, v[i].u);
        }
    }
    return;
}

测试题目:luogu P2330 [SCOI2005]繁忙的都市

23.3Prim算法

Prim算法的思想和Dijkstra算法类似,不过和其不同的是,Prim算法在对点进行“松弛操作”时,对dis数组的操作是dis[i]=min(mp[cut][i],dis[i])从而有效地防止了重边的加入,时间复杂度O(m+n^2),可以用堆(斐波那契堆)进行优化

const int inf = 1000000;
int mp[330][330];
int dis[1000];
int n, m;
int ans = 0;
void Prim()
{
    int flag[1000];
    memset(flag, 1, sizeof(flag));
    memset(dis, inf, sizeof(dis));
    dis[1] = 0;
    int cnt = 0;
    while (cnt < n)
    {
        int mi = inf + 100;
        int mix = 0;
        for (int i = 1; i <= n; i++)
        {
            if (flag[i] && mi > dis[i])
            {
                mi = dis[i];
                mix = i;
            }
        }
        ans = max(mi, ans);
        for (int i = 1; i <= n; i++)
        {
            if (flag[i])
            {
                dis[i] = min(mp[mix][i], dis[i]);
            }
        }
        flag[mix] = 0;
        cnt++;
    }
    return;
}

测试题目:luogu P2330 [SCOI2005]繁忙的都市

第24章单源最短路径

单源最短路径指的是求解不存在的负环的图,其中某一个点到图中其他点的最短路径的集合。

24.1Bellman-Ford算法

Bellman-Ford算法基于动态规划思想,他通过不断用边去“松弛”dis数组(用边来询问从起始点到对应节点的状态是否可以改善),实现状态间的转移,从而实现对最短路径的求解,并且可以判定负环。

时间复杂度O(nm)

struct edge
{
    int w, u, v;
};
vector<edge> v;
int n, m;
int dis[30000];
int Bellman_ford(int s, int e)
{
    memset(dis, 1000000, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            dis[v[j].u] = min(dis[v[j].u], dis[v[j].w] + v[j].v);
        }
    }
    return dis[e];
}

测试题目:luogu [USACO09OCT]Heat Wave

24.3Dijkstra算法

Dijstra算法基于贪心思想,因为对于与初始节点距离最短的节点来说,不存在任何一个节点可以作为中间节点使源节点到此节点的距离变小,然而我们却可以通过这个最短的节点,去尝试是否能够将其他节点到源点的距离也一并变小,不断地找到相对最小的节点,然后用其去松弛其他节点,最后将其出队,重复n次,便可以找到起点到各个点的最小路径。时间复杂度n(n^2)(可以用堆优化至(nlogn))

int n, m;
int mp[MAXN][MAXN];
int dis[MAXN];
int Dijkstra(int s, int t)
{
    memset(dis, 1000000, sizeof(dis));
    dis[s] = 0;
    int flag[MAXN];
    memset(flag, 1, sizeof(flag));
    int cnt = 0;
    while (cnt < n)
    {
        int mi = inf + 100;
        int mix = 0;
        for (int i = 1; i <= n; i++)
        {
            if (dis[i] < mi && flag[i])
            {
                mi = dis[i];
                mix = i;
            }
        }
        flag[mix] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (flag[i])
            {
                dis[i] = min(dis[i], mp[i][mix] + dis[mix]);
            }
        }
        cnt++;
    }
    return dis[t];
}

第25章:所有节点对的最短路径问题

对于寻找一个图中所有节点的最短路径问题,我们可以根据前一章所学到的Dijkstra算法和Bellman-Ford算法,对每个节点都跑一边,用一个二维的dis数组来存储结果,但是Dijkstra不能解决负环,而如果使用Bellman-Ford算法,在稠密图上的时间复杂度将达到O(n^4)显然不能推荐。

25.2Floyd-Warshall算法

Floyd算法采用动态规划思想,它先用边初始化一个临界矩阵,再通过起点i,终点j和中间节点k,试图通过中间节点使i和j之间的距离缩小,状态转移方程为 f[i][j] = min(f[i][j], f[i][k] + f[k][j])

由于要枚举三个节点,所以时间复杂度为O(n),算法实现也十分简单(我学的一个图论算法)。

void Floyd-Wallshall(){
for (k = 1; k <= n; k++) {
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    }
  }
 }
}

测试题目 hdoj 2544最短路

第26章:最大流

26.1流网络

作为一种经典的图论算法,最大流算法解决的问题也是基于点和边,不过这时,每条边都有着一个“容量值”,点和有容量属性边所构成的图便被称为"流网络",其中所有流量的起始点叫做"源节点",所有流量的重点叫做"汇点"。

最大流算法所能解决的问题就是通过调整每条边所经过的流量,是源节点到汇点的流量最大化。另外,如果存在多个源节点和汇点的话,只需假设一个“超级源节点”和“超级汇点”,然后将所有的源节点和汇点将其连接就可以了。

26.2 Ford-Fulkerson增广路算法

首先对于每一条边,我们定义它的容量减去他所流经的流量为他的剩余容量。对于一些有剩余流量的边构成的边集,我们叫其“残量网络”,如果我们发现有一条从源节点到汇点的路径都是由有剩余容量的边所组成的,则我们将其称作一条“增广路”。很显然,每条增广路都可以使源节点到汇点的流量增加。

Edmond-Karp 动能算法(EK 算法)

EK算法是 Ford-Fulkerson增广路算法 的一种实现,其原理就在于通过BFS(广度优先搜索)来查找增广路,并且在找到增广路之后加入反向边,然后继续重复搜索,直到找不到新的最短路为止,从而实现最大化流量。

时间复杂度:O(nm^2)n为点数,m为边数。

int pr[220];
int mp[220][220];
int flow[2020];
int m, n;
int bfs(int s, int e)
{
    memset(pr, -1, sizeof(pr));
    queue<int> q;
    q.push(s);
    flow[s] = 0x7FFFFFFF;
    pr[s] = 0;
    while (!q.empty())
    {
        int now = q.front();
        if (q.front() == e)
            break;
        for (int i = 1; i <= n; i++)
        {
            if (i != s && i != now && mp[now][i] && pr[i] == -1)
            {
                q.push(i);
                flow[i] = min(mp[now][i], flow[now]);
                pr[i] = now;
            }
        }
        q.pop();
    }
    if (pr[e] == -1)
        return pr[e];
    return flow[e];
}
int Edmond_Karpint(int s, int e)
{
    int ans = 0;
    int delita;
    while (true)
    {
        delita = bfs(s, e);
        if (delita == -1)
            break;
        int now = e;
        while (now != s)
        {
            mp[pr[now]][now] -= delita;
            mp[now][pr[now]] += delita;
            now = pr[now];
        }
        ans += delita;
    }
    return ans;
}

测试题目:HDOJ 1532.Drainage Ditches

Dinic算法

作为EK算法的一种优化(或者说是更优解法),虽然导论上没有提到,但是作为补充还是很有必要的。

Dinic算法通过分层思想,先通过bfs对图进行分层(源节点为0层,于源节点相邻的点为1层,于之在相邻的为二层,以此类推),分层之后,我们再使用dfs进行寻找增广路的时候,就能确保找到的增广路是最短的,同时可以对流量为0的图进行特判。

时间复杂度O(n^2m)n为点数,m为边数。


💭💭💭💭💭💭