首页 教程算法正文

跟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张图:
同构1
同构2
首先你的感觉是这2个图肯定不一样。但从图的角度出发,这2个图是一样的,即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系,不管顶点的位置在哪,边的粗细长短如何,只要不改变顶点代表的事物本身,不改变顶点之间的逻辑关系,那么就代表这些图拥有相同的信息,是同一个图。同构的图区别仅在于画法不同。

路径/最短路径

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

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

连通图/连通分量

如果在图G中,任意2个顶点之间都存在路径,那么称G为连通图。下面这张图中,顶点8和顶点2之间就不存在路径,因此下图不是一个连通图,当然该图中还有很多顶点之间不存在路径。
连通图
上图虽然不是一个连通图,但它有多个连通子图: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为一个二分图。

二分图

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

  • 无序对 $\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的左图就是一个无向图。

img

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

img

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

设图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左图就是一个有向带权图。

img

=[邻接矩阵 内容来源]: 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的边表(对于有向图则称为出边表),所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

  • 邻接表有两种结点结构:顶点表结点和边表结点.。img

其中: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种:

序号算法名称应用场景
1\alpha-\beta 修剪算法减少树搜索过程中minimax算法评估的节点数量,属于对抗性搜索算法
2A^{\star}算法用于寻路和图遍历,在多个节点之间寻找路径,多用于点对点
3B^{\star} 算法一种最佳优先图搜索算法,用于查找给定初始节点到任何目标节点的最低成本路径
4回溯算法(backtracking)通用算法,用于查找某些计算问题的所有可行解,特别是约束满足问题,逐步构建候选解,并在确定候选解不可行时进行回溯
5波束搜索(beam) 算法启发式搜索算法,通过扩展有限集中最可能的节点来探索图形
6Bellman-Ford 算法计算加权有向中单个源节点到其他节点的最短路径,比Dijkstra算法慢,但更通用
7Best-first 算法根据指定规则选择最可能的点来进行图搜索
8双向(Bidirectional)搜索从有向图中找出给定初始点到目标点的最短路径,进行两次搜索:一次从初始点开始向前搜索,一次从目标点向后搜索,相遇时停止
9Boruvka算法贪婪算法,从图中找到所有边缘权重不同的最小生成树或最小生成林
10分支定界(Branch & Bound) 算法通过状态空间搜索可行解
11广度优先搜索BFS (Breadth-first search)遍历或搜索树或图数据结构,从图任意节点开始,并在移动到下一节点之前探索当前深度水平的所有相邻节点
12D^{\star}算法增量搜索算法
13深度优先搜索DFS(Depth-first search)遍历或搜索树或图数据结构的算法,选择任意节点作为根节点,在回溯之前尽可能地沿着每个分支进行搜索
14Dijkstra算法(SPF 算法, shortest path faster)搜索节点之间的最短路径。单源最短路径搜索:给定初始点,搜寻初始点到其他点的最短路径,生成最短路径树
15Edmonds算法最小生成树的定向模拟
16Floyd-Warshall算法在具有正或负边缘权重的加权图中寻找最短路径
17Fringe搜索寻找从给定初始节点到目标节点之间的最低成本路径
18爬山(Hill Climbing) 算法从图的任意节点开始,然后尝试通过对节点进行增量更改来找到更好的节点
19IDA (Iterative deepening A^{\star})算法在加权图中找到从给定初始节点到一组目标节点中任意节点之间的最短路径
20迭代深化搜索算法(Iterative deepening)具有深度限制的深度优先搜索
21Johnson算法在稀疏边缘加权有向图中找到节点之间最短路径
22跳跃点搜索JPS (Jump point)算法A^{\star}算法优化版本
23Kruskal 算法最小生成树算法,找到联通树中任意两棵树的最小权重边缘
24词典宽度有限搜索Lex-BFS算法对图节点进行排序的线形时间搜索算法
25LPA^{\star}算法基于A^{\star}算法的增量启发式搜索算法
26Prim 算法一种贪婪算法,用于从加权无向图中找到最小生成树
27SMA^{\star}算法使用有界内存的A^{\star}算法,继承了A^{\star}算法的特性
28最短路径快速SPFA算法Bellman-Ford算法的改进,在加权有向图中计算单源最短路径

其中,两种遍历方式较为常用:深度优先遍历(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


评论