517编程普及组数学之图论基础

在算法或数学中，图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

基本概念

  • 节点（或顶点）：图中的一个元素，可以用来表示某个实体或概念。在C++中，通常可以用整数或自定义的结构体来表示节点。
  • 度：指与一个点相连的节点数量。
  • 边：连接图中两个节点的线，可以是有向的（箭头指向）也可以是无向的。
  • 边权：指一条边的权值，可以理解为长度。

分类

  • 无向图：指每条边都是没有方向的图，可以从任意一边出发，类似双行道。
  • 有向图：指每条边都是有方向的，只能按照相应的方向，类似单行道。
  • 完全图：只每两个点之间都有一条边。一个有 $n$ 个节点的完全图有 $n*(n-1)/2$ 条边。
  • 连通图：指每个点都可以到达另一个点。
  • 连通块：一张非连通图中会有多个连通块，每一个连通块中的每个点都可以到达另一个点。
  • 树：指 $n$ 个点，$n-1$ 条边的连通图。

表示

在 C++ 中，图有两种表达：

  • 邻接矩阵：

    通过矩阵存储图，a[i][j] 表示点 $i$ 到点 $j$​ 是否有边。

    1
    2
    int a[N][N]//定义
    a[u][v]=1//添加一条 u 指向 v 的节点

  • 邻接表

    使用向量数组存储图， a[i] 存储所有点 $i$​​ 指向的点。

    1
    2
    vector<int> a[N]//定义
    a[u].push_back(v)//添加一条 u 指向 v 的节点

算法

  • 拓扑排序

    概念

    拓扑排序针对于有向无环图(DAG)。

    每一个节点在进行拓扑排序后会先于所有它能到达的点。

    这样似乎不好理解，用一个简单的图排序一遍就懂了。

    A
    B
    C
    D
    E

    对于上面这幅图：

    • A->B->C->D->E
    • A->B->D->C->E
    • A->C->B->D->E
    • …

    都是这幅图的拓扑排序结果，当然，在很多时候会要求你输出字典序最小的情况。

    思路

    要实现拓扑排序，我们发现，第一个节点的入度为 $0$，而删去第一个节点后，第二个节点入读仍然为 $0$。

    它的大概逻辑就是：

    1. 找到所有入度为 $0$ 的节点，并加入答案数组
    2. 删去入度为 $0$ 的节点，并更新其它节点的入度
    3. 反复 1、2 步，直到没有节点

    A
    B
    C
    D
    E

    1
    B
    C
    D
    E

    1
    2
    3
    D
    E

    1
    2
    3
    4
    E

    实现
    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
    #include <bits/stdc++.h>
    using namespace std;

    int n,m;
    vector<int> mp[100005];//使用邻接表存图
    map<int,int> in;
    vector<int> ans;

    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int u,v;
            cin>>u>>v;
            mp[u].push_back(v);//表示 u 有一条指向 v 的边
            in[v]++;//统计入度
        }
        queue<int> q;//存储当前所有入度为 0 的点
        for(int i=1;i<=n;i++)
        {
            if(in[i]==0)//如果入度为 0
                q.push(i);//加入队列
        }
        while(!q.empty())
        {
            int t=q.front();
            q.pop();
            ans.push_back(t);//将 t 加入答案数组
            for(int i=0;i<mp[t].size();i++)
            {
                in[mp[t][i]]--;//t 指向的所有节点入度减一
                if(in[mp[t][i]]==0)//如果入度为 0
                    q.push(mp[t][i]);//加入队列
            }
        }
        for(int i=0;i<ans.size();i++)
            cout<<ans[i]<<" ";
        return 0;
    }

  • 最短路

    概念

    字面意思，最短路指的是从一个点到达另一个点的最短路径

    思路

    这里讲解 Dijkstra 算法。

    这个算法运用到了一个贪心的思想，即走到当前节点时路径最优。走到这个节点时，我们去遍历所有下一个节点，如果从这个节点走过去比原来的路径短的话，就更新。当然，一开始都得赋值为极大值。

    代码

    由于是图论基础，不展示（（（没写出来用vector的，一个邻接矩阵一个前向星