图论基础学习笔记

Hello, 欢迎登录 or 注册!

/ 2评 / 0赞

本文作者：  本文分类：编程学习笔记  浏览：1276
阅读时间：10879字, 约12-18分钟

文章中包含的模板都集中在这里

目录

画图工具

第一部分 图的遍历

$1.$ 什么是图

由一些顶点和边组成的图形即为图。

上图中，边有 $1-2,2-5,2-3$ 等。

$2.$ 有向图和无向图

简单来说，如果有两个顶点 $a,b$。

那么无向图有 $a-b,b-a$ 两条。

而有向图只有 $a-b$ 或 $b-a$ 一条。

$3.$ 深度优先搜索遍历图与广度优先搜索遍历图

深度优先搜索：$Depth-first$ $search$ 即 $dfs$。

广度优先搜索：$Breadth-first$ $search$ 即 $bfs$。

示意图：

$dfs$ 概念：

从一个顶点开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

$bfs$ 概念：

广度优先搜索算法是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。$bfs$ 并不使用经验法则算法。

接下来，我们可以用 $dfs$ 和 $bfs$ 来遍历图。

上方图中已经生动形象地介绍了 $dfs$ 和 $bfs$ 主要思路。

$dfs$ 实现方法是递归， $bfs$ 则是队列。

$dfs$ 遍历：

#include <bits/stdc++.h>
using namespace std;
#define N 10005
int n,m;
int a[N][N],e[N][N],book[N] = {0};
int sum = 0;
void dfs(int cur) {
    printf("%d ",cur);
    sum++;
    if (sum == n) return;
    for (int i=1; i<=n; i++) {
        if (e[cur][i] == 1 && book[i] == 0) {
            book[i] = 1;
            dfs(i);
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i == j) e[i][j] = 0;
            else e[i][j] = 999999999;
        }
    } 
    for (int i=1; i<=m; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    book[1] = 1;
    dfs(1);
    return 0;
}

$bfs$ 遍历：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,m,a,b,cur,book[105] = {0},e[105][105];
    int que[100005],head,tail;
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999;
        }
    }
    for (int i=1; i<=m; i++) {
        scanf("%d%d",&a,&b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    head = 1;
    tail = 1;
    que[tail] = 1;
    tail++;
    book[1] = 1;
    while(head < tail && tail <= n) {
        cur = que[head];
        for (int i=1; i<=n; i++) {
            if (e[cur][i] == 1 && book[i] == 0) {
                que[tail] = i;
                tail++;
                book[i] = 1;
            } 
            if (tail > n) break;
        }
        head++;
    } 
    for (int i=1; i<tail; i++) printf("%d ",que[i]);
    return 0;
}

$4.$ 练习

样例：

input：

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3


output：

9

$Code:$

#include <bits/stdc++.h>
using namespace std;
int minn = 999999999;
int book[105] = {0};
int e[105][105];
int n,m;
int a,b,c;
void dfs(int cur,int dis) {
    if (dis > minn) return;
    if (cur == n) {
        if (dis < minn) minn = dis;
        return;
    }
    for (int j=1; j<=n; j++) {
        if (e[cur][j] != 999999999 && book[j] == 0) {
            book[j] = 1;
            dfs(j,dis + e[cur][j]);
            book[j] = 0;
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i == j) e[i][j] = 0;
            else e[i][j] = 999999999;
        }
    }
    for (int i=1; i<=m; i++) {
        scanf("%d%d%d",&a,&b,&c);
        e[a][b] = c;
    }
    book[1] = 1;
    dfs(1,0);
    printf("%d\n",minn);
    return 0;
}

样例：

input：

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

output：

2

$Code:$

#include <bits/stdc++.h>
using namespace std;
struct note {
    int x;
    int s;
};
int main() {
    struct note que[2505];
    int e[55][55] = {0};
    int book[55] = {0};
    int head,tail;
    int n,m,a,b,cur,start,end,flag = 0;
    scanf("%d%d%d%d",&n,&m,&start,&end);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i == j) e[i][j] = 0;
            else e[i][j] = 999999999;
        }
    }
    for (int i=1; i<=m; i++) {
        scanf("%d%d",&a,&b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    head = 1; tail = 1;
    que[tail].x = start;
    que[tail].s = 0;
    tail++;
    book[start] = 1; 
    while(head < tail) {
        cur = que[head].x;
        for (int j=1; j<=n; j++) {
            if (e[cur][j] != 999999999 && book[j] == 0) {
                que[tail].x = j;
                que[tail].s = que[head].s + 1;
                tail++;
                book[j] = 1;
            }
            if (que[tail - 1].x == end) {
                flag = 1;
                break;
            }
        }
        if (flag == 1) break;
        head++;
    }
    printf("%d\n",que[tail - 1].s);
    return 0;
}

第二部分 最短路径

$1.$ $dfs$ $\&$ $bfs$

在上一部分已经讲解过。

给定一个有向图，每两个点之间有一个长度。求从第一个点到最后一个点的最小长度。

给定一个无向图，再给定起始顶点和终点顶点。求从起始点到终点最少需要走过多少条边。

$2.$ $Floyd - Warshall$

此算法简称 $Floyd$。

它是用来求任意两个结点之间的最短路的。

复杂度比较高，但是常数小，容易实现。一般来说，时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。

适用于任何图，不管有向无向，边权正负，但是最短路必须存在。

求两个点之间的最短路径，这个问题也被称为 “多源最短路径” 问题。

$Floyd$ 的思想就是用 $1-n$ 这几个点来作为中转点，然后反复更新最短路径。

核心部分：

for (int k=1; k<=n; k++) {
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            e[i][j] = min(e[i][j],e[i][k] + e[k][j]);
        }
    }
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
int e[105][105],n,m,t1,t2,t3;
const int INF = 999999999;
int start,endd;
int main() {
    scanf("%d%d%d%d",&n,&m,&start,&endd);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i == j) e[i][j] = 0;
            else e[i][j] = INF;
        }
    }
    for (int i=1; i<=m; i++) {
        scanf("%d%d%d",&t1,&t2,&t3);
        e[t1][t2] = t3;
    }
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                e[i][j] = min(e[i][j],e[i][k] + e[k][j]);
            }
        }
    }
    /*
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) printf("%d ",e[i][j]);
        printf("\n"); 
    }
    */
    printf("%d\n",e[start][endd]);
    return 0;
}

测试数据：

input：

4 8 2 4
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12


output：

4

$3.$ $Dijkstra$

本节写的是一个点（源点）到其余各个顶点的最短路径，也叫做 “单源最短路径”。

例如，一个图中有 $6$ 个顶点，那么 $Dijkstra$ 可以得出 $1$ 号顶点到 $2,3,4,5,6$ 号顶点的最短路径。

这种算法只适用于非负权图，但是时间复杂度非常优秀。

主要思想是，将结点分成两个集合：已确定最短路长度的，未确定的。

一开始第一个集合里只有 $S$。

然后重复这些操作：

直到第二个集合为空，算法结束。

暴力时间复杂度：$O(n^2+m)=O(n^2)$。

#include <bits/stdc++.h>
#define MAXN 0x7fffffff
using namespace std;
int dist[5005],n,m,edge[5005][5005],minn,idx,s;
bool vis[5005];
void dijkstra() {
    for(int j=1; j<n; j++) {
        minn = MAXN;
        for(int i=1; i<=n; i++) {
            if(!vis[i] && dist[i] < minn) {
                minn = dist[i];
                idx = i;
            }
        }
        vis[idx] = 1;
        for(int i=1; i<=n; i++) {
            if(edge[idx][i] != MAXN) {
                int t = edge[idx][i] + dist[idx];
                if(dist[i] > t) dist[i] = t;
            }
        }
    }
}
int main() {
    cin>>n>>m>>s;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; ++j) {
            if(i!=j) edge[i][j] = MAXN;
        }
    }
    for(int i=0; i<m; i++) {
        int x,y,len;
        cin>>x>>y>>len;
        edge[x][y]=len;
    }
    for(int i=1; i<=n; i++) {
        dist[i] = edge[s][i];
    }
    vis[s] = 1;
    dijkstra();
    for(int i=1; i<=n; i++) cout<<dist[i]<<" ";
    return 0;
}

测试数据：

input：

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

output：

0 2 4 3

$4.$ $SPFA$。

推荐 @NSObject 同学写的博客。

#include <bits/stdc++.h>
#define N 2<<20
#define INF 0x7fffffff
using namespace std;
int d[N],u[N],v[N],w[N],n,m,s,c;
int main() {
    cin>>n>>m>>s;
    for(int i=1; i<=m; i++)cin>>u[i]>>v[i]>>w[i];
    for(int i=1; i<=n; i++)d[i]=INF;
    d[s]=0;
    for(int k=1; k<=n-1; k++) {
        c=0;
        for(int i=1; i<=m; i++) {
            if(d[v[i]]>d[u[i]]+w[i]) {
                d[v[i]]=d[u[i]]+w[i];
                c=1;
            }
        }
        if(!c)break;
    }
    for(int i=1; i<=n; i++)cout<<d[i]<<' ';
    return 0;
}

题单

由于数据范围小，所以可以直接用 $Floyd$。

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int a,b;
double f[1005][1005];
double x[1005],y[1005];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) f[i][j] = 998244353;
    }
    for(int i=1; i<=n; i++) scanf("%lf%lf",&x[i],&y[i]);
    cin>>m;
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&a,&b);
        f[a][b] = f[b][a] = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a]-y[b]) * (y[a] - y[b]));
    }
    cin>>s>>t;
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
            }
        }
    }
    cout<<fixed<<setprecision(2)<<f[s][t]<<endl;
    return 0;
}

第三部分 图的连通性问题

搬运一下吧。

转载：Link。

这部分不是特别重要。

第四部分 树

1. 树

上图就是一棵树。

树不包含回路。有以下特性：

上图中，$0-1-2-0$ 就是一个回路。

树的结点之间的关系：

这里讲的比较清楚

叶结点：没有子结点的结点。

主要可以概括为：

2. 二叉树

上图为一棵二叉树。

二叉树每个结点最多有两棵子树。

特殊的二叉树：

一棵深度为 $h$ 且有 $2^h-1$ 个结点的二叉树。

上图即为一棵满二叉树。

如果一棵二叉树除了最右边位置上有一个或者几个叶结点缺少外，其他是丰满的，这种树叫做完全二叉树。

上图即为一棵完全二叉树。

3. 堆

一种很常用的优化方式。

堆排序：

#include <bits/stdc++.h>
using namespace std;
int h[105];
int n;
void swap(int x,int y) {
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    return;
}
void shiftdown(int i) {
    int t,flag = 0;
    while(i * 2 <= n && flag == 0) {
        if (h[i] > h[i*2]) t = i * 2;
        else t = i;
        if (i * 2 + 1 <= n) {
            if (h[t] > h[i*2+1]) t = i * 2 + 1;
        }
        if (t != i) {
            swap(t,i);
            i = t;
        }
        else flag = 1;
    }
    return;
}
void creat() {
    int i;
    for(i=n/2; i>=1; i--) shiftdown(i);
    return;
}
int deletemax() {
    int t;
    t = h[1];
    h[1] = h[n];
    n--;
    shiftdown(1);
    return t;
}
int main() {
    int sum;
    cin>>sum;
    for(int i=1; i<=sum; i++) scanf("%d",&h[i]);
    n = sum;
    creat();
    for(int i=1; i<=sum; i++) printf("%d ",deletemax());
    return 0;
}

更好的堆排序：

#include <bits/stdc++.h>
using namespace std;
int h[105];
int n;
void swap(int x,int y) {
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    return;
}
void shiftdown(int i) {
    int t,flag = 0;
    while(i * 2 <= n && flag == 0) {
        if (h[i] < h[i*2]) t = i * 2;
        else t = i;
        if (i * 2 + 1 <= n) {
            if (h[t] < h[i*2+1]) t = i * 2 + 1;
        }
        if (t != i) {
            swap(t,i);
            i = t;
        }
        else flag = 1;
    }
    return;
}
void creat() {
    int i;
    for(i=n/2; i>=1; i--) shiftdown(i);
    return;
}
void heapsort() {
    while(n > 1) {
        swap(1,n);
        n--;
        shiftdown(1);
    }
    return;
}
int main() {
    int sum;
    cin>>sum;
    for(int i=1; i<=sum; i++) scanf("%d",&h[i]);
    n = sum;
    creat();
    heapsort();
    for(int i=1; i<=sum; i++) printf("%d ",h[i]);
    return 0;
}

堆排序的时间复杂度为 $O(nlogn)$ ，和快排一样。

4. 并查集

例题：

有 $n$ 个小偷和 $m$ 条线索，每天线索给出两个数 $x$ 和 $y$。
表示 $x$ 和 $y$ 是同伙。求一共有几个团伙。

样例：

input：

10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6 
2 4

output：

3

并查集经典题。

并查集本质是维护一个森林。开始时，森林的每个点都是孤立的，每个结点都是一棵树。之后通过一些条件，逐渐将这些树合并成大树。

#include <bits/stdc++.h>
using namespace std;
int f[10005] = {0},n,m,k,ans = 0;
void init() {
    for(int i=1; i<=n; i++) f[i] = i;
    return;
}
int getf(int v) {
    if (f[v] == v) return v;
    else return f[v] = getf(f[v]);
}
void merge(int v,int u) {
    int t1,t2;
    t1 = getf(v); t2 = getf(u);
    if (t1 != t2) f[t2] = t1;
    return;
}
int main() {
    int x,y;
    cin>>n>>m;
    init();
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&x,&y);
        merge(x,y);
    }
    for(int i=1; i<=n; i++) {
        if (f[i] == i) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int f[10005] = {0},n,m,k;
void init() {
    for(int i=1; i<=n; i++) f[i] = i;
    return;
}
int getf(int v) {
    if (f[v] == v) return v;
    else return f[v] = getf(f[v]);
}
void merge(int v,int u) {
    int t1,t2;
    t1 = getf(v); t2 = getf(u);
    if (t1 != t2) f[t2] = t1;
    return;
}
int main() {
    int x,y,z;
    cin>>n>>m;
    init();
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&z,&x,&y);
        if (z == 1) merge(x,y);
        if (z == 2) {
            if (getf(x) == getf(y)) puts("Y");
            else puts("N");
        }
    }
    return 0;
}

板子题。

#include <bits/stdc++.h>
using namespace std;
int f[10005] = {0},n,m,p; 
void init() {
    for(int i=1; i<=n; i++) f[i] = i;
    return;
}
int getf(int v) {
    if (f[v] == v) return v;
    else return f[v] = getf(f[v]);
}
void merge(int v,int u) {
    int t1,t2;
    t1 = getf(v); t2 = getf(u);
    if (t1 != t2) f[t2] = t1;
    return;
}
int main() {
    cin>>n>>m>>p;
    init();
    for(int i=1; i<=m; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        merge(x,y);
    }
    for(int i=1; i<=p; i++) {
        int pi,pj;
        scanf("%d%d",&pi,&pj);
        if (getf(pi) == getf(pj)) puts("Yes");
        else puts("No");
    }
    return 0;
}

5. 最小生成树

https://365726.blog.luogu.org/zui-xiao-sheng-cheng-shu-xue-xi-bi-ji#

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

查询两点是否连通可以用并查集维护。

时间复杂度为 $O(mlogm)$。

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int u;
    int v;
    int w;
}e[200005];
int n,m;
int f[5005] = {0},ans = 0,cnt = 0;
int getf(int v) {
    if (f[v] == v) return v;
    else return f[v] = getf(f[v]);
}
int merge(int v,int u) {
    int t1,t2;
    t1 = getf(v); t2 = getf(u);
    if (t1 != t2) {
        f[t2] = t1;
        return 1;
    }
    return 0;
}
bool cmp(edge a,edge b) {
    return a.w < b.w;
}
int main() {
    cin>>n>>m;
    for(int i=0; i<m; i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e,e + m,cmp);
    for(int i=0; i<n; i++) f[i] = i;
    for(int i=0; i<m; i++) {
        if (merge(e[i].u,e[i].v)) {
            cnt++;
            ans += e[i].w;
        }
        if (cnt == (n - 1)) break;
    }
    cout<<ans<<endl;
    return 0;
}

Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。

和 $dijkstra$ 算很相似。

时间复杂度为 $O(n^2)$。

#include <bits/stdc++.h>
using namespace std;
bool b[5005] = {0};
int ans=0,dis[5005],w[5005][5005],x,y,z,n,m;
int INF = 68260499;
int main() {
    cin>>n>>m;
    for(int i=0; i<=n; i++) {
        for(int j=i+1; j<=n; j++) w[i][j] = w[j][i] = INF;
        w[i][i] = 0;
    }
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&x,&y,&z);
        w[x][y] = w[y][x] = min(w[x][y],z);
    }
    for(int i=0; i<=n; i++) dis[i] = w[1][i];
    dis[1] = 0;
    b[1] = 1;
    for(int i=1; i<n; i++) {
        int k = 0;
        for(int j=1; j<=n; j++) {
            if(b[j] == 0 && dis[j] < dis[k]) k = j;
        }
        b[k] = 1;
        ans += dis[k];
        for(int j=1; j<=n; j++) {
            if(dis[j] > w[k][j]) dis[j] = w[k][j];
        }
    }
    cout<<ans<<endl;
    return 0;
}

堆优化时间复杂度会降为 $O(mlogn)$。

对于洛谷数据，$Kruskal$ 跑得更快。

第五部分 拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

只适用于 AOV 网，即有向无环图。

算法思想：

#include <bits/stdc++.h>
using namespace std;
int a[105][105],c[105],r[105],ans[105];
int tot = 0,temp = 0,num = 0;
int n,m;
int j;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        do {
            scanf("%d",&j);
            if (j != 0) {
                c[i]++; //点i出度
                a[i][c[i]] = j;
                r[j]++; //点i入度
            }
        } while(j != 0);
    }
    for (int i=1; i<=n; i++)
        if (r[i] == 0) ans[++tot] = i;          //把图中所有入度为0的点入栈
    do {
        temp = ans[tot];
        printf("%d " ,temp);
        tot--; num++;             
        for (int i=1; i<=c[temp]; i++) {
            r[a[temp][i]]--;
            if (r[a[temp][i]] == 0) //如果入度减1后变成0，则将这个后继点入栈
                ans[++tot] = a[temp][i];
        }
    } while (num != n);           
    return 0;
}

关于作者

  1. Zhang, Xuheng说道：
    2021年2月3日 下午7:34

    LaTeX炸了一些。。。

    回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注