图论-从七桥问题到欧拉路

本文总共 2.6k字 | 你数一下对不对

思考

小明比小华高，小华比小红高，于是我们就能很轻松的判断出小明比小红高。可是，如何让计算机处理这样的信息呢？这个时候，我们引进了<图>的概念。

对于一组有关联的数据如A>B ,B>C，我们的大脑可以很轻松的处理并整合这些信息，但是计算机并不能直接地判断出A与C的关系，此时就需要图的帮助。图论的确是一种十分有趣的算法，它能形象地将某种复杂的关系清晰地表现在计算机中。构造了图，可以结合其它有趣的算法，如BFS/DFS来遍历图从而获取图中的信息。

七桥问题

起源

18世纪，在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如右图的“一笔画”问题，证明上述走法是不可能的。

7qiao

七桥问题是图论中最重要的内容之一， 它最终是无解的，但是由此引发了大量的数学家的思考，推断和验证。数学家们把该问题简化为了一笔画问题，最后得出的结论是：连通图可以一笔画的充要条件是：奇点的数目不是0个就是2个（连到一点的数目如是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端）

推广

而计算机科学诞生之后，我们又一次的对原先的结论进行推广。首先我们规范了在图论中这些规律、事实的名称。

名称定义
欧拉路如果一个图存在一笔画，则一笔画路径称为欧拉路
欧拉回路在欧拉路的基础上，如果起点和终点相同，则称该欧拉路为欧拉回路
奇点跟这个点相连的边数目有奇数个的点

对于能够一笔画的图，我们有以下两个定理：

  • 【定理一】存在欧拉路的条件：图是连通的，有且只有2个奇点
  • 【定理二】存在欧拉回路的条件：图是连通的，有且只有0个奇点

求欧拉路/欧拉回路算法

一般的，我们会用DFS深度优先搜索来求某个图中的欧拉路/欧拉回路，这是最简单同时最容易理解的求法之一。
根据前面一笔画得出的定理，当我们需要寻找某个图中的欧拉路或欧拉回路时，先得寻找到图中的奇点，然后对其中从其中任意一个奇点开始DFS搜索，如果没有找到奇点，则从任意一点开始DFS即可。这样做的时间复杂度为$ O(M+N) $（其中$M$为边数，$N$为点数），这个时间复杂度稍微玄学了一点，不必计较。
我们来举一道题目：

求欧拉路/欧拉回路例题

给定一张图，寻找出其中的欧拉路或欧拉回路。给定的图保证有欧拉路/欧拉回路

输入格式

第一行输入n,m，表示有n个点，m条边，一下m行描述每条边连接的两点，每行输入x,y表示x,y相连。

输出格式

按顺序输出欧拉路或欧拉回路的路径，每个点中间空一格。如果有多条路径，允许输出任意一条。

输入样例与输出样例

输入样例

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

输出样例

1
1 5 4 3 2 1

数组解法ARRAY CODE

我们来贴一个数组代码理解一下。我们构建一个二维数组map[n][n]来表示每个节点之间的关系。初始化map全部为false，如果$i$节点与$j$节点相连，那么map[i][j]=true。同时还需要记录每个节点的度（与这个点相连的边有几条，也就相当于与该点相连的点有几条）。

重要变量

变量名称变量意义
int n总共有n个点
int m总共有m条边
int beg欧拉路/欧拉回路的起点
int map[n][n]记录哪些结点是相连的
int cntroad[n]记录每个点的度数
int vis[n]记录该点是否走过
int reroad[n]记录最终的欧拉路/欧拉回路所经历的点
int cntreroad记录当前欧拉路中点的个数

构造图

1
2
3
4
5
6
7
8
9
10
11
memset(map,0,sizeof(map));//如果是全局变量会自动清0，可省略
cin>>n>>m;
for(int i=1;i<=m;i++)
{
    int x,y;
    cin>>x>>y;
    g[x][y]=g[y][x]=1;//记录这两个点是相连的
    cntroad[x]++;
    cntroad[y]++;
    //这两个点的度数增加1
}

找到欧拉路/欧拉回路的起点

根据前面七桥问题得出的结论：如果一张图中有且仅有两个奇点，那么该图必定包含欧拉路，且两个奇点一个是起点，一个是终点。如果该图没有奇点，就说明该图包含欧拉回路，从任意一点出发都可以走回原点。于是可得一下代码来寻找欧拉路/欧拉回路的起点

1
2
3
4
5
6
7
8
9
10
beg=1;
for(int i=1;i<=n;i++)
    if(cntroad[i]%2==1)//找到奇点，即为起点
        beg=i;/*break; 
        找到了就可以退出，
        因为两个奇点中可以任选一个作为起点*/
/*如果此时没有找到一个奇点，
说明这张图里包含的是欧拉回路，
那么beg就是初始定义的1
（其实随便从哪一点开始找都可以）*/

DFS寻找欧拉路/欧拉回路

搜索，把每一个点的子节点都列出来，找到路径。要注意的是同一条边走过了就应该记录一下，下一次不能再走，不然会陷入死循环，一直在两个点之间徘徊。有以下两种写法

1
2
3
4
5
6
7
8
9
10
11
12
void find(int x)
{
    for(int i=1;i<=n;i++)
        if(map[x][i]==1)
        {
            map[x][i]=map[i][x]=0;
            /*相当于删除了这条边
            下一次搜索就不会再走了*/
            find(i);
        }
    reroad[++cntreroad]=x;
}

1
2
3
4
5
6
7
8
9
10
11
12
void find(int x)
{
    for(int i=1;i<=n;i++)
        if(map[x][i]==1 && vis[i]==0)
        {
            vis[i]=1;
            /*记录一下已经走过了这个点，
            下一次就不会再走*/
            find(i);
        }
    reroad[++cntreroad]=x;
}

$\color{red} {注意}$！第二种方式仅限于计算欧拉路，一旦遇到欧拉回路就会出错
理解一下：第二种方法在每个点走过之后就会标记：这个点不能再走了，但是欧拉回路的起点和终点是一样的，也就说名起点必定要走两次，于是我们可以纠正一下，改成：

1
2
3
4
5
6
7
8
9
10
11
void find(int x)
{
    for(int i=1;i<=n;i++)
        if(map[x][i]==1 && (vis[i]==0 || i==beg))
        //满足一个即可
        {
            vis[i]=1;
            find(i);
        }
    reroad[++cntreroad]=x;
}

输出欧拉路

不必多说

1
2
for(int i=1;i<=cntreroad;i++)
    cout<<reroad[i]<<" ";

向量解法VECTOR CODE

相比之下，$vector$向量的解法逼格会高很多。对于学过向量的同学来说，$vector$的解法会方便很多。但是对于没学过的同学，会略微有点难以理解。$vector$解法不用记录每个点度数和最终欧拉路的点数，因为可以直接用.size()得到当前vector中有多少个数。
简单的讲一下吧：

重要变量

变量名称变量意义
int n总共有n个点
int m总共有m条边
int beg欧拉路/欧拉回路的起点
vector<int> map[n]记录哪些结点是相连的
int vis[n]记录该点是否走过
vector<int> reroad记录最终的欧拉路/欧拉回路所经历的点

构造图

在求欧拉路/欧拉回路的过程中，我们就不过多的纠结什么有向还是无向了，我们只要记录哪些点是相连的就足够了。

1
2
3
4
5
6
7
8
9
cin>>n>>m;
int ir,it;
for(int i=1;i<=m;i++)
{
	cin>>ir>>it;
	map[ir].push_back(it);//STL大法好
	map[it].push_back(ir);//STL大法好*2
	//双向路
}

找到欧拉路/欧拉回路的起点

与数组解法同理，如果一张图中有且仅有两个奇点，那么该图必定包含欧拉路，且两个奇点一个是起点，一个是终点。如果该图没有奇点，就说明该图包含欧拉回路，从任意一点出发都可以走回原点。这个时候我们可以调用$vector$的.size()函数来统计某个点的度数了。因为在.push_back()的时候$vector$会帮你进行size++的操作。

1
2
3
4
beg=1;
for(int i=1;i<=n;i++)
    if(vector[i].size()%2==1)//STL大法好*3
        beg=i;

DFS寻找欧拉路/欧拉回路

搜索，把每一个点的子节点都列出来，找到路径。要注意的是同一条边走过了就应该记录一下，下一次不能再走，不然会陷入死循环，一直在两个点之间徘徊。有以下两种写法

1
2
3
4
5
6
7
8
9
10
void find(int x)
{
    for(int i=1;i<=n;i++)
        if(map[x][i]==1)
        {
            map[x][i]=map[i][x]=0;
            find(i);
        }
    reroad.push_back(x);//STL大法好*4
}

输出欧拉路

不必多说

1
2
for(int i=1;i<=reroad.size()/*STL大法好*5*/;i++)
    cout<<reroad[i]<<" ";

总结

图论，数论是OI学习发育的重要关卡，十分的有意思，但是也必须静下心来琢磨，反复思考才能获取最好的学习效果。用代码构建的图看不见，摸不着，点点线线远没有真实的图画美丽，但是它们构建出的思想，十分让人着迷。

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

浙江杭州的<del>快退役的</del>信奥生。<br>今年初二呢。