图论基础 —— 跟WilliamYan一起学算法

又和你见面了!这里是《跟WilliamYan一起学算法》。今天我们将学习图论。
图论是数学中非常重要的一环,在研究许多实际问题时经常会用到。让我们直接开始吧!

定义

二元组G(V,E)称为图(Graph)。V为节点集,E为边集。

点,用数字 $0….n-1$ 表示

点对 $(u,v)\in E$ 称为边或弧

对于边 $(u,v) \in E$ :

  • $u$ 和 $v$ 邻接
  • $e$ 和 $u,v$ 关联

子图:边的子集和点的子集构成的图,满足边关联的点集在点的子集中

自环:如果一条边的起点和终点相同,称为自环

度数:从一个顶点 $V$ 引出的边的条数称为点的度数

  • 无向图顶点的度数之和是边数的两倍
  • 对有向图的顶点的度可进一步分为出度+入度,出度是指从该顶点出发的边数,入度是
    指到达该顶点的边数

同构

先看看下面2张图:
《图论基础 —— 跟WilliamYan一起学算法》
《图论基础 —— 跟WilliamYan一起学算法》
首先你的感觉是这2个图肯定不一样。但从图的角度出发,这2个图是一样的,即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系,不管顶点的位置在哪,边的粗细长短如何,只要不改变顶点代表的事物本身,不改变顶点之间的逻辑关系,那么就代表这些图拥有相同的信息,是同一个图。同构的图区别仅在于画法不同。

路径/最短路径

在图上任取两顶点,分别作为起点和终点,我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线,就是一条“路径”。两点之间存在路径,则称这2个顶点是连通的。
路径也有权重。路径经过的每一条边,沿路加权重,权重总和就是路径的权重(通常只加边的权重,而不考虑顶点的权重)。在路网中,路径的权重,可以想象成路径的总长度。在有向图中,路径还必须跟随边的方向。
值得注意的是,一条路径包含了顶点和边,因此路径本身也构成了图结构,只不过是一种特殊的图结构。

环,也称为环路,是一个与路径相似的概念。在路径的终点添加一条指向起点的边,就构成一条环路。通俗点说就是绕圈。

连通图/连通分量

如果在图G中,任意2个顶点之间都存在路径,那么称G为连通图。下面这张图中,顶点8和顶点2之间就不存在路径,因此下图不是一个连通图,当然该图中还有很多顶点之间不存在路径。
《图论基础 —— 跟WilliamYan一起学算法》
上图虽然不是一个连通图,但它有多个连通子图:0,1,2顶点构成一个连通子图,0,1,2,3,4顶点构成的子图是连通图,6,7,8,9顶点构成的子图也是连通图,当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图,也就是连通分量。连通分量有如下特点:

  1. 是子图;
  2. 子图是连通的;
  3. 子图含有最大顶点数。

显然,对于连通图来说,它的最大连通子图就是其本身,连通分量也是其本身。

在某图中,若删除顶点V以及V相关的边后,图的一个连通分量分割为两个或两个以上的连通分量,则称顶点V为该图的一个关节点。一个没有关节点的连通图称为重连通图。

在重连通图中,任意一对顶点之间至少存在两条路径,则再删去某个顶点即相关各边后也不破坏图的连通性。若在图的连通图上删去k个节点才能破坏图的连通性,则称K为此图的连通度。

生成树

在一个任意连通图 $G$ 中,如果取它的全部顶点和一部分边构成一个子图 $G’$ ,即:$V(G’)=V(G)$ 和 $E(G’)\subseteq E(G) $

若同时满足边集 $E(G’)$ 中的所有边既能够使全部顶点连通而又不形成任何回路,则称子图 $G’$ 是原图 $G$ 的一棵生成树。

=[定义 参考01]: https://my.oschina.net/RapidBird/blog/3402 "图结构(Graph)"
=[定义 参考02]: https://blog.csdn.net/saltriver/article/details/54428685 "图论(一)基本概念"

图的分类

简单图:如果一个图没有自环,并且每两个顶点之间最多只有一条边,这样的图称为简单图。可以把连接 $V_i,V_j$ 的边记作

完全图:若一个图的每一对不同顶点恰有一条边相连,则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。$n$ 个端点的完全图有 $n$ 个端点及 $\frac{n(n − 1)}{2}$ 条边,以 $K_n$ 表示。

二分图:二分图又称作二部图,是图论中的一种特殊模型。 设 $G=(V,E)$ 是一个无向图,如果顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$ ,并且图中的每条边 $(i,j)$ 所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i \in A,j \in B)$,则称图G为一个二分图。

《图论基础 —— 跟WilliamYan一起学算法》

无向图:边没有方向的图称为无向图。无向图中的边均是顶点的无序对,无序对通常用圆括号表示

  • 无序对 $\left(V_i,V_j\right)$ 和 $\left(V_j,V_i\right)$ 表示同一条边

有向图:若图中的每条边都是有方向的,则称为有向图。有向图中的边是由两个顶点组成的有序对,有序对通常用尖括号表示

  • 如 $\left <V_i,V_j \right >$ 表示一条有向边,其中 $V_i$ 是边的始点,$V_j$ 是边的终点。$\left <V_i,V_j \right >$ 和 $\left <V_j,V_i \right >$ 代表两条不同的有向边

图的存储

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

设图 $G$ 有 $n$ 个顶点,则邻接矩阵是一个 $n\times n$ 的方阵,定义为:
$$
arc[i][j] = \begin{cases}
1& {(V_i,V_j)\in E \text{or} \left<V_i,V_j\right>\in E}\\
0& {\text{Other} \ situations}
\end{cases}
$$
我们来看一个实例,图7-4-2的左图就是一个无向图。

《图论基础 —— 跟WilliamYan一起学算法》

我们再来看一个有向图样例,如图7-4-3所示的左图。

《图论基础 —— 跟WilliamYan一起学算法》

对于每条边上都带有权的,这些权值就需要保存下来。

设图G是带权图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
$$
arc[i][j] = \begin{cases}
W_{(i,j)}& {(V_i,V_j)\in E \text{or} \left<V_i,V_j\right>\in E}\\
0& {i = j}\\
\infty & {\text{Other} situations}\\
\end{cases}
$$
如图7-4-4左图就是一个有向带权图。

《图论基础 —— 跟WilliamYan一起学算法》

=[邻接矩阵 内容来源]: https://blog.csdn.net/jnu_simba/article/details/8866705 "数据结构:图的存储结构之邻接矩阵"

无向带权图创建代码:

#define MAXVEX 100     /* 最大顶点数,应由用户定义 */
#define INFINITY 65535 /* 表示权值的无穷*/

typedef int EdgeType;    /* 边上的权值类型应由用户定义 */
typedef char VertexType; /* 顶点类型应由用户定义  */

typedef struct
{
    VertexType vexs[MAXVEX];      /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵,可看作边表 */
    int numNodes, numEdges;       /* 图中当前的顶点数和边数  */
} MGraph;
/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *Gp)
{
    int i, j, k, w;
    cout << "请输入顶点数和边数(空格分隔):" << endl;
    cin >> Gp->numNodes >> Gp->numEdges;
    cout << "请输入顶点信息(空格分隔):" << endl;
    for (i = 0; i < Gp->numNodes; i++)
        cin >> Gp->vexs[i];
    for (i = 0; i < Gp->numNodes; i++)
    {
        for (j = 0; j < Gp->numNodes; j++)
        {
            if (i == j)
                Gp->arc[i][j] = 0; /* 顶点没有到自己的边*/
            else
                Gp->arc[i][j] = INFINITY; /* 邻接矩阵初始化 */
        }
    }

    for (k = 0; k < Gp->numEdges; k++)
    {
        cout << "请输入边(vi, vj)的上标i,下标j和权值w(空格分隔):" << endl;
        cin >> i >> j >> w;
        Gp->arc[i][j] = w;
        Gp->arc[j][i] = Gp->arc[i][j]; /* 因为是无向图,矩阵对称 */
    }
}

int main(void)
{
    MGraph MG;
    CreateMGraph(&MG);
    return 0;
}

=[代码来源(有删改)]: https://book.douban.com/subject/6424904/ "《大话数据结构 》 程杰著 清华大学出版社"

邻接表

邻接表存储的基本思想:对于图的每个顶点vi,将所有邻接于vi的顶点链成一个单链表,称为顶点vi的边表(对于有向图则称为出边表),所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

  • 邻接表有两种结点结构:顶点表结点和边表结点.。《图论基础 —— 跟WilliamYan一起学算法》

其中:vertex:数据域,存放顶点信息。 firstedge:指针域,指向边表中第一个结点。 adjvex:邻接点域,边的终点在顶点表中的下标。 next:指针域,指向边表中的下一个结点。

=[邻接表 内容来源]: https://www.cnblogs.com/smile233/p/8228073.html "图的存储结构(邻接矩阵与邻接表)及其C++实现"

代码(不是自己写的)

#include<iostream>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
typedef struct __EDGE_
{
    int nxt;
    int to;
} edge;

edge e[M];

int head[N], cnt;

void addedge(int nodeX, int nodeY)
{
    ++cnt;
    e[cnt].nxt = head[nodeX];
    e[cnt].to = nodeY;
    head[x] = cnt;
    //以上四句可以压成一行:
    //e[++cnt]=(edge){head[nodeX],nodeY};head[x]=cnt;
}

int main(){
    int n,m;
    cin>>n>>m;
    memset(head,0,sizeof head); cnt=0;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    for(int x=1;x<=n;x++){
        cout<<x<<":";
        for(int i=head[x];i!=0;i=e[i].nxt){
            int y=e[i].to;
            cout<<y<<" ";
        }
        cout<<endl;
    }
    return 0;
}

图的遍历

图的遍历是指从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。

  • 由于图结构本身的复杂性,所以图的遍历操作也较复杂,主要表现在以下四个方面:
    1. 在图结构中,没有一个“自然”的首结点,图中任意一个顶点都可作为第一个被访问的结点。
    2. 在非连通图中,从一个顶点出发,只能够访问它所在的连通分量上的所有顶点,因此,还需考虑如何选取下一个出发点以访问图中其余的连通分量。
    3. 在图结构中,如果有回路存在,那么一个顶点被访问之后,有可能沿回路又回到该顶点。
    4. 在图结构中,一个顶点可以和其它多个顶点相连,当这样的顶点访问过后,存在如何选取下一个要访问的顶点的问题。

遍历时应当思考:

  1. 图没有首尾之分,所以算法中必须指定访问的第一个结点
  2. 图的遍历过程中可能会构成一个回路,造成死循环,所以要考虑到所有的死循环问题
  3. 一个结点可能和多个结点都是邻接关系,所以要使一个结点的所有邻接结点按照某种次序被访问。

图分连通图和非连通图,连通图中,从初始结点出发,一定存在路径和图中的所有其他结点相连。而非连通图,从某一结点开始并不能访问图中的所有结点。此处我们只讨论连通图的遍历。

图遍历算法可以按照节点访问顺序进行分类,根据访问目的或使用场景的不同,算法大致可分为28种:

《图论基础 —— 跟WilliamYan一起学算法》

其中,两种遍历方式较为常用:深度优先遍历(DFS)和广度优先遍历(BFS)。他们对无向图和有向图都适用。下面我们将重点讨论这两种算法。

BFS

广度优先遍历需要一个队列以保存访问过的结点顺序,以便按访问过的结点顺序来访问这些结点的邻接结点,设计如下。

  1. 访问结点v并标记结点v为已访问
  2. 结点v入队列
  3. 当队列非空,则继续执行,否则算法结束
  4. 出队列取得队头结点u
  5. 查找结点u的第一个邻接结点w
  6. 若结点u的邻接结点w不存在,转步骤3,否则循环执行以下:
    • 若结点w未被访问,则访问结点w,并标记w为已访问
    • 结点w入队列
    • 查找结点u的w邻接结点的下一个邻接结点w,转步骤6

代码(也不是自己写的)(图的存储基于邻接表):

#include<iostream>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
typedef struct __EDGE_
{
    int nxt;
    int to;
} edge;

edge e[M];

int head[N], cnt,q[N],d[N];

void addedge(int nodeX, int nodeY)
{
    e[++cnt]=(edge){head[nodeX],nodeY};
    head[x]=cnt;
}

int main(){
    int n,m,s;
    cin>>n>>m>>s;
    memset(head,0,sizeof head);
    cnt=0;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    int l,r,x;
    for(q[l=r=1]=s;l<=r;l++){
        for(int i=head[x=q[l]];i;i=e[i].nxt){
            int y=e[i].to;
            if (d[y]==-1) 
            {
                q[++r]=y;d[y]=d[x]+1;
            }
        }
    }
    for(q[l=r=1]=s,d[s]=0;l<=r;l++){
        for(int i=head[x=q[l]];i;i=e[i].nxt){
            int y=e[i].to;
            if(d[y]==-1) q[++r]=y; d[y]=d[x]+1;
        }
    }
    for(int i=1;i<=n;i++)cout<<d[i]<<" ";
    cout<<endl;
    return 0;
}

DFS

从初始结点出发,遵守深度优先规则,即在图的所有邻接结点中,每次都在访问完当前结点后首先访问当前结点的第一个邻接结点,该算法是一个递归算法,设计如下。

  1. 访问结点v并标记结点v为已访问
  2. 查找结点v的第一个邻接结点w
  3. 若结点w存在,则继续执行,否则算法结束
  4. 若结点w尚未被访问,则以结点w开始进行深度优先遍历(递归)访问结点w
  5. 若结点w已被访问过,则查找结点v的w邻接结点的下一个邻接结点w,转步骤3

=[^DFS]: 该递归算法属于回溯算法

代码(仍然不是自己写的)

#include <iostream>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
typedef struct __EDGE_
{
    int nxt;
    int to;
} edge;

edge e[M];

int head[N], cnt, vis[N], d[N];

void addedge(int nodeX, int nodeY)
{
    e[++cnt] = (edge){head[nodeX], nodeY};
    head[x] = cnt;
}

void dfs(int x)
{
    d[x] = ++t;
    for (int i = head[x]; i; i = e[i].nxt)
    {
        int y = e[i].to;
        if (!d[y])
            dfs[y];
    }
}

int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    memset(head, 0, sizeof head);
    cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        addedge(x, y);
        addedge(y, x);
    }
    t = 0;
    memset(vis, 0, sizeof(vis));
    dfs(s);
    for (int i = 1; i <= n; i++)
    {
        if (!d[i])
            dfs(i);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << d[i] << ' ';
    }
    cout << endl;
    return 0;
}

=[图的遍历 参考01]: https://blog.csdn.net/sinat_32561655/article/details/71439442 "图的遍历"
=[图的遍历 参考02]: https://www.cnblogs.com/weizhixiang/p/5815994.html "图的深度遍历和广度遍历"
=[图的遍历 参考03]: https://www.jianshu.com/p/c26266ee0f20 "图遍历算法之DFS/BFS"
=[图的遍历 参考04]: https://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html "图的遍历"

拓扑排序

预备知识

一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网,简称AOV网

定义

给定一幅有向图,将所有顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素(或者说明无法做到这一点)

有向无环图才有拓扑排序,非有向无环图没有拓扑排序一说

有向无环图(DAG, Directed Acyclic Graph)必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

步骤

由AOV网构造拓扑序列的拓扑排序算法:

  1. 选择一个入度为0的顶点并输出之
  2. 从网中删除此顶点及所有出边
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

=[拓扑排序 参考01]: https://my.oschina.net/HuoQibin/blog/1592861 "有向图问题1–深度优先、广度优先遍历和拓扑排序"
=[拓扑排序 参考02]: https://www.cnblogs.com/newpanderking/archive/2012/10/18/2729552.html "拓扑排序"
=[拓扑排序 参考03]: https://blog.csdn.net/lisonglisonglisong/article/details/45543451 "拓扑排序(Topological Sorting)"
=[拓扑排序 参考04]: https://www.geeksforgeeks.org/topological-sorting/ "Topological Sorting"

总结

你们在看到标题的时候一定会疑惑,为什么算法学习会要学习图论呢?其实,在我们解决许多类似地图的问题的时候,图论总是一个好的办法。学会了图论,不说一定能获得什么好处,至少在比赛时不至于吃亏。况且,今天我们学习的还是图论中极为简单的一部分,如果有人像我一样最开始不能很好理解的话,应当仔细研究,争取早日化为己用。

© 2019 William Yan

点赞

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据