图论入门(一)

图论入门(一)

0 在阅读之前

前备知识可阅读数据结构基础

1 图与图论

1.1 介绍

图是什么?图可以是一个表情图,拍摄的照片或者地图。在算法竞赛中图不是我们生活中那些图,而是一个截然不同的概念。

想像一个地图。地图上有许多的标记(建筑物),从一个标记到另一个标记需要走路,而路就是连接它们的线。这样,我们把标记看为顶点,把路看成线,这样地图就成为了数学上的“”。

是表示物与物之间关系的方法。与之紧密联系的是图论图论就是以图为研究对象,研究顶点和边组成的图形的数学理论和方法。

1.2 图的元素

边和顶点是图的两个重要的元素。下面给出图的三个依据元素的分类:

  • 边的方向
    • 无向图:边是双向联通的
    • 有向图:边是单向联通的(边有方向)

  • 有无边权

    • 边权是指这条边的长度或者权重等等
    • 有权图:边有边权
    • 无权图:边无边权
  • 有向图的度

    • 度是指有多少条边连接这个顶点
    • 出度:流出此点的边的数量
    • 入度:流入此点的边的数量

1.3 图的存储

一般来说涉及图论的题目都有这样的形式:题目会给两个整数u,v,分别代表两个顶点,如果边有边权的话,还会给一个整数w表示边权。

1 2    //无边权
2 3 5    //有边权

那么如何存储图呢?这里有三个存储图的方法,分别是邻接矩阵邻接表链式前量星⭐。

  • 邻接矩阵

邻接矩阵就是用二维数组map(不是C++STL里的map)来存图。

有向图:若u⇢v,则使map[u][v]=w。

无向图:若u⇢v,则使map[u][v]=map[u][v]=w。

注意没有边权的话就是map[u][v]=1。当b=a时,map[u][v]=0。map数组一般初始化为0,-1或者正无穷(0x3f)。

无向图的邻接矩阵摊开来看是关于主对角线对称的。

  • 例1.3.1
int map[maxn][maxn]    //maxn为点的数量上限
for (int i=1;i<=n;i++)    //n条边
{
    cin>>u>>v>>w;
    map[u][v]=w;    //无边权就去掉w
    //map[u][v]=map[v][u]=w;
}

邻接矩阵简单直白,容易理解,但是其浪费的空间十分之大。在点的数量超过5000时便有爆内存的可能。一般不用。

邻接矩阵的空间复杂度为$O(n^2)$,遍历点的时间复杂度为$O(n)$。

  • 邻接表

邻接表可以解决邻接矩阵会浪费大量空间的问题。邻接表用C++STL里的vector来存储图,一般要配对struct使用。

存图方式跟邻接矩阵差不多。一般建立一个结构体edge,内有两整形变量to,cost,分别表示这条边指向的顶点和边权。如果没有边权则不用结构体edge,直接用int即可。

  • 例1.3.2
strut edge
{
    int to,cost;
}

vector<edge> p[maxn];    //maxn为点的数量上限
//vector<int> p[maxn];    没有边权

int main()
{
    for (int i=1;i<=n;i++)    //n条边
    {
        cin>>u>>v>>w;
        p[u].push((node){v,w});    //(node){v,w}表示一个结构体常量
        //p[v].push((node){u,w})    无向图
        //p[u].push(v);    没有边权
    }
}

邻接表可以快速的求出图中点x的出度,即p[x].size()

  • 链式前向星

这个有链表的相关知识会好理解些。

首先说说什么是前向星⭐。前向星⭐就是把边存进一个边集数组中,然后按照边的起点进行排序,这样数组中起点相等的边就能够在数组中进行连续访问了。它的优点是实现简单,容易理解,缺点是需要在所有边都读入完毕的情况下需要对所有边进行一次排序,带来了时间开销。前向星⭐需要用数组head记录某个起点在边集数组中的首个存储位置。

  • 例1.3.3
struct edge
{
    int u;    //起点  
    int v;    //终点  
    bool operator < (const edge &a) const
    {
        return (u==a.u&&v<a.v)||u<a.u;
    }
}p[maxn];    //maxn为边的数量上限
int head[maxn];    //head[i]记录起点i在边集数组中的首个存储位置

int main()
{
    for (int i=0;i<n;i++)    //n条边
        cin>>edge[i].u>>edge[i].v;
    sort(edge,edge+n);
    memset(head,-1,sizeof(head));
    head[edge[0].u]=0;
    for (int i=1;i<n;i++)
        if (edge[i].u!=edge[i-1].u) head[edge[i].u]=i;
}

接下来就是链式前向星⭐了。链式前向星⭐就是在前向星⭐的基础上加上了链式结构,这同时省去了排序的操作。

  • 例1.3.4
struct node
{
    int to;
    int w;
    int next;    //指向下一个相同起点的边
}edge[maxn];    //maxn为边的数量上限

int head[maxn];    //head[i]记录起点i在边集数组中的首个存储位置

void add(int u,int v,int w)
{
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int main()
{
    for (int i=1;i<=n;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
    }
}

1.4 图的遍历

图的遍历≈数组遍历,都是将所有数据扫一遍。只不过图不像数组是线性的一个结构。图的遍历有两种,分别是DFSBFS。下面用邻接表的存图方式来举例。

  • DFS(深度优先搜索)

基本操作:

  1. 当前结点有若干个子结点a,b,c,...
  2. 先遍历a以及a的子结点,再遍历b以及b的子结点,再遍历...

上述操作是递归进行的,请看代码实现。

  • 例1.4.1
bool pd[maxn];    //pd[i]表示该点有无被读过
void dfs(int x)
{
    cout<<x<<' ';    //先遍历当前结点
    for (int i=0;i<p[x].size();i++)    //再遍历它的子结点
    {
        if (!pd[p[x][i]])
        {
            pd[p[x][i]]=1;
            dfs(p[x][i]);    //递归进行
        }
    }
}

我们再画图来一步一步模拟,看看是怎么遍历的:

首先从1开始,先遍历了1,然后开始遍历1的子结点2,3,4,首先遍历的是子结点2,然后开始遍历2的子结点5,7,首先遍历的是2的子结点5,然后开始遍历5的子结点6,子结点6没有子结点,退回遍历2的子结点7,子结点7没有子结点,退回遍历1的子结点3,然后开始遍历3的子结点7,8,3的子结点7已经被遍历过不能再遍历,于是遍历3的子结点8,然后开始遍历8的子结点6,8的子结点6已经被遍历不能再遍历,于是返回遍历1的子结点4,子结点4没有子结点,返回退出了函数,此时整个图已经被被读完。

可以发现,这样做会使得先一直往深处走,到达最底端也就是相对起始结点最远的地方,这样的遍历方法叫做图的深度优先搜索

  • BFS(广度优先搜索)

基本操作:

  1. 当前结点有若干个子结点a,b,c,...
  2. 先遍历这若干个子结点,再遍历这若干个子结点的子结点

上述操作是使用队列进行的。请看代码实现。

  • 例1.4.2
bool pd[maxn];    //pd[i]表示该点有无被读过
queue<int> q;    //创建队列
 
int main()
{ 
    pd[1]=1;
    q.push(1);
    while (!q.empty())
    {
        int x=q.front();
        cout<<x;
        q.pop();
        for (int i=0;i<p[x].size();i++)
        {
            if (!pd[p[x][i]])
            {
                pd[p[x][i]]=1;
                q.push(p[x][i]);    //压入队列
            }
        }
    }
}

还是这个图,再次一步一步模拟,看看是怎么遍历的:

  1. 首先从1开始,此时队列[1],取首元素1输出,遍历子结点,把子结点压入队列[2,3,4]。
  2. 接着取首元素2输出,遍历子结点,把子结点压入队列[3,4,5,7]。
  3. 接着取首元素3输出,遍历子结点,把子结点压入队列[4,5,7,8]。
  4. 接着取首元素4输出,无子结点。队列[5,7,8]。
  5. 接着取首元素5输出,遍历子结点,把子结点压入队列[5,7,8,6]。
  6. 接下来不会再有元素入队了,于是队列里的元素一个一个的取出。

输出的内容为[1,2,3,4,5,7,8,6],可以发现,遍历的顺序是从左到右,从上到下一层一层的遍历。这样的遍历方法叫做图的广度优先搜索

其他存储方式的遍历是类似的,可以自行尝试写一下。

1.5 图的遍历-DFS

原题

考虑一下,直接莽的话就是dfs每个结点找到最大的编号,而题目是最多$10^5$个点和边,可以想象得出花费的时间是非常大,这样做必然会TLE。题目求的是每个点经过的最大的编号,那么可不可以反向思维,从最大编号的点开始找能经过它的点?这样绝对遍历时间会少很多,不过这样做我们需要先把边反向一下。请看代码。

#include<bits/stdc++.h>
using namespace std;

vector<int> p[100005];
int pd[100005];    //判断该点是否被找过
int maxn[100005];    //编号最大的点

void dfs(int x,int color)
{
    pd[x]=color;
    for (int i=0;i<p[x].size();i++)
    {
        if (!pd[p[x][i]]) dfs(p[x][i],color);
    }
}
    
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n,m;
    cin>>n>>m;

    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        p[v].push_back(u);    //反向边
    }

    for (int i=n;i;i--)
    {
        if (!pd[i])
            dfs(i,i);
    }

    for (int i=1;i<=n;i++)
        cout<<pd[i]<<' ';
    return 0;
}

1.6 一笔画

图论的一个经典问题就是一笔画问题(戈尼斯堡七桥问题)。其问题就是给一些顶点和边,问你能不能用一条线连接所有的顶点,有就写出来。

首先需要引进一些概念:

  1. 欧拉路:欧拉路就是这个问题的那一条线,如果这一条线又连回了起点,那么这个欧拉路称为欧拉回路。
  2. 奇点和偶点:跟这个顶点连接的边有奇数条的顶点叫做奇点。跟这个顶点连接的边有偶数条的顶点叫做偶点。

引进了概念之后,如何判断有无欧拉路或者欧拉回路?

  1. 存在欧拉路:图是联通的,有且只有两个奇点。
  2. 存在欧拉回路:图是联通的,没有奇点。

这里只给结论,怎么推出来的请自行搜索

怎么操作?

  1. 先判断联通:这个简单,用并查集即可。
  2. 判断度数:这个也简单,用一个数组来存储即可。
  3. DFS求路径:如果是欧拉路,则从奇点开始dfs即可;如果是欧拉回路,则从任意一个顶点开始dfs即可。

时间复杂度是$O(n+m)$。

1.7 无序字母对-一笔画

原题

这道题表面上是字符串其实本质就是一笔画问题。那么就可以用套路了,先判断联通,再判断度数,最后dfs求路径。

我们一步一步的来分析怎么解决问题,首先是选择存图方式。这道题的字符数最多也就52个,数据规模并不大,所以可以直接使用简单的邻接矩阵。

int graph[256][256];    //char类型最大值为256,这样可以包含所有char

然后是判断联通,这个直接写个并查集就可以了。

int check_anc(int x)    //寻找祖先
{
    if (fa[x]) return fa[x]=check_anc(fa[x]);
    return x;
}
void union_anc(int x,int y)    //合并
{
    x=check_anc(x); y=check_anc(y);
    if (x!=y)
    fa[x]=y;
}

接着是度数,我们直接用一个数组记录即可。

int d[256];

最后是找欧拉回路,dfs直接遍历一遍就可以了。

void dfs(int x)
{
    for(int i=65;i<=122;i++)
        if(b[x][i])
        {
             b[x][i]=b[i][x]=0;    //两个方向全部弄掉
             dfs(i);
        }
    ans[n--]=x;//因为是回溯的时候存,所以倒着存
}

这样最后拼接再补全完善就称为了这道题的答案,请看代码。

  • 例1.7.1
#include<bits/stdc++.h>
using namespace std;

int graph[256][256];    //邻接矩阵,char类型最大值为256,这样可以包含所有char
int d[256];      //度数
int fa[256];    //存祖先
string ans;    //答案
int n;      

int check_anc(int x)    //寻找祖先
{
    if (fa[x]) return fa[x]=check_anc(fa[x]);
    return x;
}
void union_anc(int x,int y)    //合并
{
    x=check_anc(x); y=check_anc(y);
    if (x!=y)
    fa[x]=y;
}

void dfs(int x)
{
    for(int i=65;i<=122;i++)
        if(graph[x][i])
        {
          graph[x][i]=graph[i][x]=0;    //该路已走
          dfs(i);
        }
    ans[n--]=x;    //因为是回溯的时候存,所以倒着存
}

    
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int setout=0;    //记录起点
    int cnt=0;    //记录奇点数量

    cin>>n;
    ans.resize(n+1);    //确定答案长度,无论是欧拉路还是欧拉回路,都是n+1长

    for (int i=0;i<n;i++)    //存图
    {
        string s;
        cin>>s;
        graph[s[0]][s[1]]=graph[s[1]][s[0]]=1;
        d[s[0]]++;
        d[s[1]]++;
        union_anc(s[0],s[1]);
    }

    for (int i='A';i<='z';i++)    //判断联通
        if (check_anc(i)==i&&d[i]) cnt++;

    if (cnt!=1) {cout<<"No Solution\n"; return 0;}    //图不联通

    cnt=0;
    for (int i='A';i<='z';i++)    //判断度数
        if (d[i]&&d[i]%2)
        {
            cnt++;
            if (!setout) setout=i;    //记录欧拉路起点(奇点)
        }
    
    if (cnt&&cnt!=2) {cout<<"No Solution\n"; return 0;}    //奇点数不为2

    if (setout) dfs(setout);    //如果是欧拉路
    else for (int i='A';i<='z';i++)    //如果是欧拉回路
            if (d[i])    //任意点出发
                {dfs(i); break;}

    cout<<ans<<'\n';
    return 0;
}

代码的注释多到足以让你理解。代码还是很长的,写的时候一定要细心。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。