图论基础学习笔记

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

目录

画图工具


第一部分 图的遍历

$1.$ 什么是图

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

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


$2.$ 有向图和无向图

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

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

而有向图只有 a-bb-a 一条。


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

深度优先搜索:Depth-first searchdfs

广度优先搜索:Breadth-first searchbfs

示意图:

dfs 概念:

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

bfs 概念:

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

接下来,我们可以用 dfsbfs 来遍历图。

上方图中已经生动形象地介绍了 dfsbfs 主要思路。

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$

在上一部分已经讲解过。

  • $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. 树

上图就是一棵树。

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

  • 一棵树中任意两个结点有且仅有唯一一条路径联通。

  • 一棵树如果有 n 个结点,则它有 n-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 条线索,每天线索给出两个数 xy
表示 xy 是同伙。求一共有几个团伙。

样例:

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 算法

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 网,即有向无环图。

算法思想:

  • 选择一个入度为 0 的顶点并输出

  • 然后从 AOV 网中删除此顶点及以此顶点为起点的所有关联边。

  • 重复上述两步,直到不存在入度为 0 的顶点为止。

  • 若输出的顶点数小于 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;
}

Zhang, Xuheng

这个人很懒,什么都没写

相关推荐

2 条评论

  1. LaTeX炸了一些。。。

    • 啊这 我们只支持katex。。。sorry

Leave a Reply

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

图论基础学习笔记
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close