第七章 图

专业基础►数据结构 评论

图

由于考试压力。。。还有待完善。。。

图的定义

  • 图由顶点集合和边集合产生

有向图和无向图

  • 有向图的边带有箭头，而无向图的边没有箭头。
  • 无向边用()表示，而有向边用<>表示。

图的基本术语

  • 端点和邻接点
    • 一条边的两头的顶点为端点，这两个端点互为邻接点。
  • 顶点的度、入度和出度
    • 有向图的度又分为出度和入度。
    • 度、顶点数和边数的关系
      • 每个顶点的度都代表了一条边，但是又因为每个边两头会有两个顶点，所以把所有顶点的度相加再除以2便是边的数目。
  • 完全图
    • 完全无向图：每个顶点都与剩下的n−1n-1个顶点直接有边相连，总共有n个结点，但是这样算，每条边都被算了两次，所以总边数为n(n−1)/2n(n-1)/2。
    • 完全有向图：因为每两个顶点之间都有两条方向不同的边，所以总边数直接就为n(n−1)n(n-1),无需再除以2。
  • 稠密图和稀疏图
    • 稠密图：接近完全图的图；
    • 稀疏图：含有边数较少的图（e<<n(n−1)e<<n(n-1)）。
  • 子图
    • 类似集合中子集的关系。
  • 路径和路径长度
    • 路径上无重复结点的路径为简单路径（开始和结尾可以重复）。
  • 回路和环
    • 开始与结尾相同的简单路径为简单回路或简单环。
  • 连通、连通图和连通分量
    • 连通图的连通分量为自身；而非连通图的连通分量可能有多个；
    • 非连通图的连通分量是原来图中不相连的几个部分；如果原来连通的部分再被拆开，则不是连通分量。例如：
      • 图2和图3是图1的连通分量，而图4不是。
  • 强连通图和强连通分量
    • 强连通图是针对有向图而言的，任意两个结点之间连通的前提下，还要这两个结点间可以互通。
    • 在非强连通图中找强连通分量的方法：
      • 先找出一个有向环，在这个环内各个顶点之间是互通的，然后再去增加环外与环上任一顶点互通的顶点，从而这个顶点肯定与环内其余顶点互通，从而构建出了强连通分量。
  • 权和网
    • 给边加上权，带权图即为网。

图的存储结构

1.邻接矩阵：

  • 特别适合于稠密图的存储。
  • 一个图的邻接矩阵的表示是唯一的。
  • 无向图与有向图均可存储。
    2.邻接表：
  • 特别适合稀疏图的存储；
  • 一个图的邻接表表示不唯一。
  • 普通邻接表不能表现边的方向性，所以存储有向图需要使用逆邻接表。
    3.十字链表
    • 储存有向图
      4.邻接多重表
  • 存储无向图

邻接矩阵

  • 邻接矩阵定义
    • 通过数组下标与顶点的编号之间的对应关系，来表示两个顶点之间的边。因为矩阵的大小是根据顶点数固定了的，所以当图很稀疏时，即图中的边数较少时，会有很多空间的浪费。
    • 由此可知，无向图的邻接矩阵一定是一个主对角线上的元素全为0的对称矩阵。
    • 示例：
  • 邻接矩阵存储类型定义
    • 需要设立一个二维数组（邻接矩阵）来存储边的信息，一个一维数组来存储顶点的信息；
    • 顶点的信息中包括顶点的编号和它的数据信息。
    • 实质是一种顺序存储结构。

邻接表

  • 邻接表的定义
    • 通过链表来表示顶点之间边的关系；因为链表的长度是动态的，所以当图较稀疏时，也不会有太多存储空间浪费。
    • 用一个数组来记录每个顶点的信息。
    • 每个顶点对应的单链表只是表示它们是顶点的邻接点，而单链表结点之间并无关系。
    • 示例：
  • 邻接表存储类型定义
    • 边结点类型即单链表结点的类型；
    • 头结点类型即存储在数组中的顶点类型；
    • 通过在数组中检索到顶点，再由顶点通过顶点类型中定义的指向对应单链表的指针来找到该顶点的边信息。
  • 逆邻接表
    • 用于存储有向图；
    • 对于每个顶点的单链表中，存储的是有边指向该顶点的顶点。

十字链表

  • 十字链表的基本概念
    • 在邻接表的基础上，每个顶点结点增加一个指向边结点的指针。即每个顶点结点中既记录了出边的信息，又记录了入边的信息；
    • 每个边结点增加相对的起点和终点信息（起点即指向它的顶点，终点即它指向的顶点）,另外使用指向下一个相同终点或起点的指针（即指向对同一个顶点的入边或者出边）,来为某一个顶点的入边或者出边形成一个相对的单链表。
  • 十字链表的实现模型
    • 例如：0顶点的两条入边，2和3在第一列被链起来了；而3的三条出边2，0，1在最后一行被链起来了。

邻接多重表

  • 邻接多重表的基本概念
    • 与十字链表类似，只不过去掉了方向性（即起点与终点之分）
  • 邻接多重表的实现模型
    • 例如：0的两条边，3和1在第一行通过靠0来识别的指针链起来了；1的三条边，0、2和4通过以1为标识来识别的指针在第一列链起来了。

图的基本运算（邻接表）

图的创建

  • 先给邻接表分配空间（AdjGraph）;
  • 再让所有头结点（即储存图顶点的数组adjlist）指向第一条边结点的指针域为空；
  • 遍历邻接矩阵中的所有元素，将存在的边，存入边结点类型中（Arcnode）,之后再将边结点以头插法的方式插入到头结点后面。
  • 有两重循环，时间复杂度为O(n2)O(n^2)

图的输出

  • 把邻接表的头结点的编号，相邻结点，边的权重，依次打印即可。

图的销毁

  • 依次遍历所有头结点；
  • 在遍历每个头结点时，遍历它身后的边结点链，并逐个释放。

邻接表转换为邻接矩阵

  • 进入头结点后的边结点链表，然后将当前扫描的边结点编号作为邻接矩阵的列标（头结点编号作为行标）,并修改当前行标列标下的邻接矩阵元素的权重值。
  • 虽有两重循环，但实际只对所有头结点和边结点访问了一次，所以算法的时间复杂度为O(n+e)O(n+e),n为头结点数，e为边结点数。而把邻接矩阵转化为邻接表的的算法，却对许多没有存在的边也要访问一次，所以时间复杂度要高一些。

图的遍历

  • 图的遍历：从给定的图中的任意一个顶点开始，按照某种方法，沿着图的边访问图中所有的顶点，且每个顶点仅被访问一次。
  • 图的遍历序列：通过图的遍历得到的顶点序列称为图的遍历序列。
  • 图的遍历方法：
    1. 深度优先遍历（DFS：depth-first search）
    2. 广度优先遍历(BFS: breadth-first search)

深度优先遍历（对无向连通图）

  • 基本原理
    1.首先访问出发点v，并将其标记为已访问过；
    2.然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。
    3.若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。
    4.注意：深度优先遍历尽可能优先往深层次进行搜索。
    5.使用一次深度优先遍历只能访问到初始点所在连通分量中的所有顶点，不可能访问到其它连通分量中的顶点

  • 实现过程

    • 按照访问一个顶点之后便找它的邻接点来访问的递归思路，可以一直穷尽一条通路；
    • 一条路走完之后，便重新找一个没有被访问过的顶点，继续重复这样的访问；
    • 直到最后所有顶点都已被访问过，便停止访问。

  • 算法实现

    • 设计一个全局数组，用它的下标代表顶点的编号，每次一个顶点被访问过之后，就将该数组对应的元素置为1，表示该顶点已经被访问过了；
    • 最后退出递归时，是因为到了通路的最后一个顶点，这个顶点唯一的邻接点已经被访问过了，然后终止循环退出；但是，一旦退出递归，若这条通路上的所有顶点，都不与某个顶点向连通，那个顶点便永远无法访问到,这也是这种算法只能遍历无向连通图的原因。

广度优先遍历（对无向连通图）

  • 基本原理
    1.首先访问出发点v
    2.接着依次访问v的所有邻接点w1、w2…wt
    3.然后依次访问w1、w2…wt邻接的所有未曾访问过的顶点。
    4.以此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
    5.注意：广度优先遍历按层次优先搜索最近的结点，一层一层往外搜索。深度优先是不断深挖每一个被访问了的顶点的邻接点，广度优先是先将当前顶点的所有邻接点访问完。
    6. 同深度优先遍历一样，由于每次访问的都是与当前顶点有一定关系的顶点，所以只能适用于遍历无向连通图

  • 实现过程

    • 先访问完当前顶点的所有未被访问过的邻接点；
    • 到最后一个邻接点时，转向其它顶点。
    • 直到所有顶点均已被访问，便停止访问。

  • 算法实现

    • 使用队列来实现广度优先遍历，并未像深度优先算法一样才用递归的方法;
    • 设置一个标记数组（无需全局数组，因为广度优先算法直接使用队列，借用一个循环便可完成，不须递归使用函数）,来确定某个顶点是否已经被访问过了。
    • 将第一个要访问的顶点访问后进队；
    • 之后设置循环将队列元素出队并访问它的未被访问过的邻接点，然后将每个被访问的邻接点被访问后都进队，直到当前出队的元素的所有邻接点均已被访问完，之后再出队一个元素，重复此过程，直到队列为空。由于访问的元素与初始元素都有关系，所以这种算法只能用来遍历无向连通图。

非连通图的遍历

  • 可以通过多次调用DFS或者BFS算法，来访问多个连通分量。

深度优先遍历

  • 其中DFS算法是前面遍历无向连通图的深度优先算法；

广度优先遍历

  • 其中BFS算法是前面遍历无向连通图的广度优先算法。
  • 此处的标记数组visted是全局数组。

利用遍历来判断无向图是否连通

  • 基本思路
    • 使用某种遍历算法遍历该邻接表；
    • 若一次遍历后，标记数组visited的所有元素均为1，即所有元素都已被遍历过了，则该图是连通图，反之，则不是。
  • 算法实现
    • 在调用依次遍历算法后，在遍历标记数组，看是否有元素为0.

深度优先遍历的应用

判断某两个顶点之间是否存在简单路径（深度优先）

  • 基本思路

  • 算法实现

输出某两个顶点之间的一条简单路径(深度优先)

  • 基本思路

  • 算法实现

？？输出某两个顶点之间的全部简单路径（深度优先）

  • 基本思路

  • 算法实现

??输出某个顶点的全部回路

  • 基本思路

  • 具体算法

广度优先遍历的应用

求不带权无向连通图某两顶点之间的一条最短路径

  • 算法实现
    • 为什么这样找就是最短的？

生成树和最小生成树

生成树的定义

  • 连通图的生成树
    • 连通图的最小生成树含有全部n个顶点，和对应的n-1条边。
  • 带权连通图的最小生成树
    • 最小生成树是针对于带权连通图而言的；
    • 所有边权值之和最小的生成树称为该带权连通图的最小生成树。
  • 遍历方法产生生成树
    • 深度优先生成树：
    • 广度优先生成树：
    • 一个连通图的生成树不一定是唯一的
  • 非连通图的生成森林
    • 多次调用遍历过程。每个连通分量中的顶点集和走过的边一起构成一棵生成树。
    • 所有连通分量的生成树组成非连通图的生成森林。

最小生成树的构造算法（邻接矩阵存储）

普里姆（Prim）算法

  • 基本思想
    • 在一个集合中存储已经被访问过的顶点，然后每次在与这些被访问过的顶点相连的边中选一条权值最小的边，然后将该边的另一个未被访问的顶点加入集合中，重复这个步骤，直到所有的顶点都被加入了这个集合。
  • 过程示例

  • 具体算法


    • INF 即无穷大的意思，它经常取32767或者65535这样不可能会取到的值，权重为INF表示，这两个顶点不直接相连。
    • 设置两个数组，lowcost存储与已访问过的顶点相连的边的权重,比如lowcost[j]表示j到已访问结点的边的权重。而closest存储已访问过的顶点的下标。
    • 第一步，给两个数组赋初值，lowcost的初值就是与初始顶点与剩余顶点的所有边的权重（到自己的权重为0，到邻接的顶点的权重为实际权重，到不相邻的顶点的权重为INF）,closest的初值便为便为初始顶点。
    • 之后，比较lowcost中元素的大小，找到最小的权重对应的顶点，记录它的编号到k中，**将lowcost[k]设为0，表示编号为k的顶点已经访问过了。
    • 找到k顶点后，将与k元素相连的边的权重与lowcost中储存的边的权重比较，若较小，则存入lowcost中，同时将对应位置的closest设置为k;例如：若lowcost[j]<g.edges[k][j],则将closest[j]设为k,因为closest与lowcost是一一对应的，lowcost和closest的下标都对应未被访问过的顶点（已经被访问过的顶点会由于lowcost[j]而被跳过）,而lowcost的值对应的是与已访问顶点之间权重较小的边的权重，closest的值对应的就是这条边另一头已经被访问过的顶点。
    • 找k的循环循环n-1次，则将整个图的所有元素都被访问了。
    • 每次找到一个k顶点，则将对应的边和顶点输出。（边就是closest[k]到k,顶点就是closest[k]和k)。
  • 时间复杂度
    • 该算法中有两重循环，外重循环n-1次，内重n+n次。所以算法的时间复杂度为O(n2)O(n^2).
  • Prim算法的特点
    • 适合于稠密图求最小生成树，因为每两个顶点间，不管是否存在边，都会被检查，所以如果图很稀疏，那么无用的检查就会很多。

克鲁斯卡尔（Kruskal）算法

  • 基本思想
    • Prim算法是以顶点为中心，依次寻找相邻的权值最小的边；而Kruskal算法是一边为中心，逐次选取权值较小的边，最后包含n-1条边便组成了最小生成树。
    • 不过需要注意的是，一旦选取的边生成的回路，便要舍弃这条边。
  • 算法实现
    • 存放边的结构：
    • 具体算法：


      * 设置一个标识数组vset来确定一条边的两个顶点是否已经被连接为一个连通分量（一个集合中）,来防止选取的边是生成树形成回路。
      * 用一个边数组存储所有的边，并将数组中的边按照权值递增排序。
      * 依次选取边数组中的边（因为事先已经排好序了）,利用标识数组vest确定这条边的两个顶点不在一个连通分量中，则输出该边，并将该边的两个顶点对应的表示数组值，改为相同（都为边的起始顶点值），之后选取下一条边；否则，跳过该边，选取下一条边；
      * 当选取成功了n-1条边时，终止程序。
  • Krustal算法的特点
    • 因为是根据边来选择，所以适合于边稀疏图
  • Krustal算法的时间复杂度
    • 该算法的时间复杂度为O(elog2e)O(elog_2e),其中e为边数。

最短路径

最短路径定义

  • 对带权有向图而言，路径为从此顶点到目的顶点，而路径长度则为这条路径上所有边的权值之和。

单源最短路径问题-狄克斯特拉（Dijkstra）算法

  • 问题描述

    • 给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径（限定各边上的权值大于或者等于0）。

  • 基本原理

    • 一步步求出每个顶点与源点的最短距离，每次求最短路径都是基于已经求出最短路径的顶点而求更远顶点的最短路径。

  • 基本过程


    • 将顶点分为两个集合，一个是已经计算过最短路径的，一个没有；
    • 每次从未被计算过的集合中寻找距离已被计算过的集合最短的顶点，加入该集合中。
    • 最后直到所有顶点都已被计算过最短路径。

  • 具体算法

多源最短路径问题-Floyed算法

  • 问题描述
  • 基本原理



  • 基本过程






  • 具体算法

拓扑排序（有向图）

拓扑排序概念

I

  • 拓扑序列与拓扑排序

拓扑排序操作

  • 基本过程

  • 具体算法
    • 顶点类型
    • 算法

AOE网与关键路径

AOE网

关键路径

关键路径定义

![](https://zjpicture.oss-cn-beijing.aliyuncs.com/giteePic/picgo-master/img/20200820225342.jpg)

求解关键路径

  • 事件的最早开始时间和最迟开始时间

  • 活动的最早开始时间和最迟开始时间
  • 求关键活动
  • 示例





Zestaken计算机小白一枚

吾好梦中读书~