2020数据结构-图之基本概念_弧结点

一、图

1.图的基本概念

1.相关定义

• 图是由顶点的有穷非空集合以及顶点之间的边的集合组成的，通常表示为：G(V,E)，其中，G表示一个图，V是图中的顶点的集合，E是图G中边的集合。

• 线性结构中，元素仅有线性线性关系，每个元素仅有一个直接前驱和直接后继。

• 树形结构中，数据元素（结点）之间有着明显的层次关系，每层上的元素可能和下一层中多个元素相关，但只能和上一层中的一个元素相关。

• 图形结构中，数据元素（顶点）之间具有任意关系，图中任意两个数据元素之间都有可能相关。

• 无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对（Vi，Vj）来表示，如下左图，G= (V1,{E1})，其中顶点集合V1={A，B，C，D}; 边集合E1={ (A,B) ，（B,C），(C,D)， (D,A) , (A,C) } 。

• 有向边：从顶点Vi到Vj之间有方向，则称这条边为有向边，也成为弧，用有序偶〈Vi,Vj>来表示， Vi称为弧尾， Vj称为弧头。 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。 连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A, D>表示弧，注意不能写成<D， A>。如下右图，G= (V2,{E2})，其中顶点集合V2={A，B，C，D}; 弧集合E2={<A，D>，<B，A>，<C，A>，<B，C>}。
  

• 简单图：在图中若不存在顶点到其自身的边，且同一条便不重复出现，便是简单图。

• 目前讨论的都是简单图，在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n* (n-1) 条边。

• 稀疏图：有很少条边，反之为稠密图。

• 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。如下图就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。
  

• 子集：假设有两个图G= (V，{E})和G’= (V’，{E’})，如果V’是V的子集，且E’是E的子集，则称G’为G的子图。如下图带底纹的图均为左侧无向图与有向图的子图。
  

• 对于无向图G= (V,{E})， 如果边(v,v’)属于E，则称顶点v和v‘互为邻接点，即v和v’相邻接、边(v,v’)依附于顶点v和v’，或者说(v,v’)与顶点v和v’相关联。顶点v的度是和v相关联的边的数目，记为TD(v)。如上图左侧上方的无向图，顶点A与B 互为邻接点，边(A，B) 依附于顶点A 与B上，顶点A的度为3。而此图的边数是5，各个顶点度的和=3+2+3+2=10，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。

• 对于有向图G= (V,{E})，如果弧<v,v’>属于E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v的弧<v,v’>和顶点v， v’相关联。以顶点v为头的弧的数自称为v的入度 ，记为ID (v); 以v为尾的弧的数目称为v的出度，记为OD (v); 顶点v的度为TD(v) =ID(v) +OD (v)。上图 左侧下方的有向图，顶点A的入度是2 (从B到A的弧，从C到A的弧)，出度是1 (从A到D的弧)，所以顶点A 的度为2+1=3。此有向图的弧有4 条，而各顶点的出度和=1+2+1+0=4，各顶点的入度和=2+0+1+1=4。

• 从顶点v 到顶点v’的路径是一个顶点序列。路径的长度是路径上的边或弧的数目。有向图的路径也是有向的。第一个顶点到最后一个顶点相同的路径称为回路或环。 序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。如下图，左侧的环因第一个顶点和最后一个顶点都是B，且C、 D、 A没有重复出现，因此是一个简单环。 而右侧的环，由于顶点C的重复，它就不是简单环。
  

• 在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。 如果对于图中任意两个顶点vi、vj ∈E， vi，和vj都是连通的，则称G是连通图。 下图的图1，它的顶点A到顶点B、 C、 D都是连通的，但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A、 B、 C、D相互都是连通的，所以它本身是连通图。
  

• 极大连通子图和极小连通子图：1. 必须是子图（子图中的顶点和边都是原图的子集）；2.连通（对于两个顶点u、v，如果存在u到v的边，那这两个点就是连通的）；3.极大。
  极大指的是边数极大（意思是子图中包含了原图中所有和子图中顶点相关的边）；我们假设已经有了一个连通子图G，其顶点集为V，边集为E。如果E包含了在原图中和所有和V有关的边，那我们就认为它是极大连通子图。通常情况下，如果我们删除E中的某些边，该子图仍然是连通，当我们删除了所有能删除的边（再删除就会导致不连通），并且它仍然是连通的，我们就认为它是极小连通子图。

• 对于极大和极小，个人理解为：在一个连通子图中，包含和顶点有关所有的边（the more the better），那就是极大连通子图；如果包含了必不可少的边（the less the better），那就是极小连通子图。

• 强连通图和强连通分量：在有向图中，顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任意一对顶点都是强连通的，则称此图为强连通图。（来自知乎的回答）
  

• 连通图的生成树：是一个极小的连通子图，它含有图中的全部n个顶点，但只有构成一棵树的n-1条边，比如下图的图1是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2 或图3，就满足n个顶点n-1条边且连通的定义了， 它们都是一棵生成树。从这里也可知道，如果一个图有n 个顶点和小于n-1条边，则是非连通图，如果多于n-1 边条，必定构成一个环， 因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2 和图3，随便加哪两顶点的边都将构成环。 不过有n-1条边并不一定是生成树，比如图4。
  

• 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点， 其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成， 含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 如下图的图1 是一棵有向图。去掉一些弧后，它可以分解为两棵有向树，如图2和图3，这两棵就是图1有向图的生成森林。
  

2.图的存储结构

1.邻接矩阵

• **图的邻接矩阵存储方式是用两个数组来表示图。**一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为:
  
  如下无向图：
  
  如下有向图：
  
• 我们知道，每条边上带有权的图叫做网，如果要将这些权值保存下来，可以采用权值代替矩阵中的0、1，权值不存在的元素之间用∞表示，如下图，左图是一个有向网图，右图就是它的邻接矩阵。
  
• 简单分析算法效率：从代码中也可以得到，n 个顶点和e 条边的无向网图的创建，时间复杂度为O(n+n^2+e)
  其中对邻接矩阵的初始化耗费了O(n^2)的时间。
  适合稠密图
  2.邻接表
• 对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的，特别是稀疏有向图。所以可以考虑用链表来按需存储。数组与链表相结合的存储方法称为邻接表。处理办法：

1. 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi 的边表，有向图则称为顶点vi作为弧尾的出边表。

如图是一个无向图的连接表结构，有向图则类似。

对于带权值的网图，可以在边表结点定义中再增加一个weight 的数据域，存储权值信息即可，如下图所示。

• 简单算法分析：以上采用头插法插入。由于对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对i 和j 分别进行了插入。本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e) 。
  3.十字链表
• 基本概念：十字链表是为了便于求得图中顶点的度（出度和入度）而提出来的。它是综合邻接表和逆邻接表形式的一种链式存储结构。在十字链表存储结构中，有向图中的顶点的结构如下所示：
  
  其中data表示顶点的具体数据信息，而firstIn则表示指向以该顶点为弧头的第一个弧节点。而firstOut则表示指向以该顶点为弧尾的第一个弧节点。为了表示有向图中所有的顶点，采用一个顶点数组存储每一个结点，如下图所示。
  
  另外，在十字链表存储结构中，有向图中的每一条弧都有一个弧结点与之对应，具体的弧结点结构如下所示：
  
  其中的tailVex表示该弧的弧尾顶点在顶点数组xList中的位置，headVex表示该弧的弧头顶点在顶点数组中的位置。hLink则表示指向弧头相同的下一条弧，tLink则表示指向弧尾相同的下一条弧。
• 从十字链表的数据结构来看，每一个顶点对应两个链表：以该顶点为弧尾的弧结点所组成的链表以及以该顶点为弧头的弧结点所组成的链表。
  如下图所示的一个有向图：
  
  其对应的顶点以及弧结点如下所示。拿结点A说明，该结点对应两个链表（绿色和黄色标记的）。绿色链表表示以结点Ａ为弧头的弧组成的链表。黄色链表表示以结点Ａ为弧尾的弧组成的链表。
  
  4.邻接多重表
• 邻接多重表（Adjacency Multilist）是无向图的另一种链式存储结构。
• 对无向图而言，邻接表的缺点：每一条边(va,vb)有两个结点，分别在第a和第b个单链表中，这可能会给边的搜索、删除等操作带来了不便。
• 邻接多重表与邻接表的区别仅在于，同一条边，在邻接表中要用两个结点表示，而在邻接多重表中只需要一个结点。
• 此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。

3.图的遍历

• 基本概念： 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。
• 深度优先遍历（DFS）：它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到。
• 具体过程看这个博客图文结合很详细深度优先遍历和广度优先遍历
• 深度遍历时，需要设置一个数组进行标志图中的顶点是否被访问过，访问过就将该位置改为True。
• 深搜类似于二叉树的先序遍历。
• 简单分析：对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(n^2)的时间。 而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
• 广度优先遍历（BFS）：如果说图的深度优先遍历类似树的前序遍历， 那么图的广度优先遍历就类似于树的层序遍历了；从首先访问的顶点V，然后访问v各个未被访问过的顶点w1，w2…然后访问完了之后再访问这几个顶点的未被访问过的邻接顶点。
• 对比图的深度优先遍历与广度优先遍历算法，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。不过如果图顶点和边非常多，不能在短时间内遍历完成，遍历的目的是为了寻找合适的顶点，那么选择哪种遍历就要仔细斟酌了。深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

4.图的应用

本部分包含最小生成树、最短路径、拓扑排序、关键路径。
1.最小生成树

• 如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。
  
  1.1Prim算法
• 定义：假设N= (P，{E}) 是连通网，TE 是N 上最小生成树中边的集合。算法从U={u0}(u0∈V)， TE={ }开始。重复执行下述操作：在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价最小的边(u0，v0) 并入集合TE，同时v0并入U，直至U=V为止。 此时TE中必有n-1条边，则T= (V,{TE}) 为N的最小生成树（所有的定义都是这么晦涩难懂，还是例子好）。
• 此算法的时间复杂度为O(n^2)。 由此得出的上述依次顺序加入的带权值边为：（0-1）、（0-5）、（1-8）、（8-2）、（1-6）、（6-7）、（7-4）、（7-3）。
  
  1.2Kruskal算法
  
• 普里姆(Prim) 算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。事实上，可以直接以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树也是很自然的想法， 只不过构建时要考虑是否会形成环路而已。此时我们就用到图的存储结构中的边集数组结构。我们可以通过将Prim算法中的邻接矩阵转化为上图右边的边集数组，并对它们按权值大小排序。
• 定义：假设N= (V，{E})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
• 克鲁斯卡尔算法的时间复杂度为O(eloge)。对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势； 而普里姆算法对于稠密图，即边数非常多的情况会更好一些。
  
  2.最短路径
  2.1Dijkstra
• Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。
  
  
  
  以上来自下面的博客，这个老哥太强了！！Dijkstra最强图文解析
  2.2Floyd
  看这个博客讲的很好很生动！Floyd–傻子都能看懂 这个标题可还行！
  3.拓扑排序
  较为简单不详说，贴一个讲的很好的博客！数据结构–拓扑排序
  4.关键路径
  一个大佬交给我的口诀正取大，反取小，关键路径相同找。
  
  大佬手稿，今天写累了，需要的私信，我再写详解。
  看了一眼右下角，发现自己写了5979个字，那就索性加一点加到6000吧，这样做虽然不太好，但是毕竟写了3个多小时，ok够了，明天继续而二叉树。

2019.10.18补充（王道课本上前两遍忽略的知识点和看说过程中发现的重点再写）

• 线性表可以是空表，树可以是空树，但是图不可以是空图。
• 简单图：不存在重复边，不存在顶点到自身的边，称图G为简单图。（数据结构中仅讨论简单图）
• 在无向图中，任意两个顶点之间都存在边，称该图为无向完全图，含有n(n-1)/2条边。在有向图中任意两顶点之间含有相反的两个弧，称为有向完全图，含有n(n-1)条有向边。
• 任意两个顶点之间是连通的，就称两顶点连通。图中任意两个顶点都是连通的，称为连通图，否则称为非连通图。
• 强连通图，强连通分量只针对有向图而言；两顶点之间相互有路径，称为强连通。
• 生成树是包含图中全部顶点的极小连通子图，图中顶点数为n，边数为n-1.
• 树的度和图的度不相同，树是指的分支节点的分支数量，而图指的是其一个顶点的边数。
• 邻接矩阵是属于顺序存储，邻接表是属于链接存储结构。
• 邻接矩阵使用一个一维数组存储图中顶点的信息，一个二维数组存储图中边的信息（即各顶点之间的邻接关系），这个二维数组称为邻接矩阵（下标从1开始）。
• 无向图邻接矩阵中的二维数组中存放的是0和1，当两顶点之间的边是属于图边的集合时，存放1，否则存放0.
• 有向图邻接矩阵与无向图邻接矩阵相同；在存放有权值的图时，两顶点之间有权值则对应二维数组的位置存放权值，其余放的是∞。
• 无向图的邻接矩阵是对称矩阵；其第i行（第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度；反之对应有向图则是出度（或入度）。
• 当存储的图是稀疏图时，对邻接矩阵的浪费是巨大的，所以使用邻接表（采用顺序存储和链式存储方法），大大减少不必要的浪费。
• 在邻接表中存在顶点表结点和边表结点；顶点表结点由顶点域和指向第一条边的指针构成，边表结点由邻接点域和指向下一条邻接边的指针域构成。
• 若为无向图则所需存储空间为O(V+2E)，若为有向图则所需存储空间为O(V+E)。倍数2是由于无向图中，每条边在邻接表中出现了两次。
• 图的邻接表表示并不唯一，在每个顶点对应的单链表中，各边的链接次序是任意的。
• 十字链表是有向图的一种链式存储结构；对应于每个弧由一个结点，对应于每个顶点也有一个结点；在弧结点中存在5个域，分别是尾域和头域：指示狐尾和弧头两个顶点在图中的位置。链域1指向弧头相同的下一条弧；链域2指向狐尾相同的下一条弧；info域存储弧的相关信息；这样一来，弧头相同的弧位于同一链表上，弧尾相同的弧位于同一链表上。顶点结点中有一个存放顶点信息的结点；还有两个指针指向以该顶点为弧头或者狐尾的第一个弧结点。
• 在十字链表中，容易求出顶点的入读和出度，且一个十字链表可以确定一个图，但是图的十字链表表示不是唯一的。
• 邻接多重表是无向图的另一种链式存储方式；在邻接表中容易求出顶点和边的信息，但是求两顶点之间是否存在边而对边执行操作时，效率比较低。临界多重表与十字链表类似，也是设立一个边结点和一个顶点结点；所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个结点同时链接在两个链表中。
• 广度优先搜索类似于二叉树的层序遍历算法，是一种分层的查找过程，每向前一步可能访问一批结点，不像深搜有回退的情况。为实现逐层访问，需要设置一个辅助队列，用来记忆正在访问的顶点的下一层结点；可用来求解单元最短路径。
• 深度优先搜索类似于树的先序遍历，尽可能深的搜索一个图。其是一个递归算法，需要借助一个递归工作栈。
• 若无向图是连通的，则从任一结点出发仅需一次就饿能够访问图中的所有顶点；若无向图菲联同，则从某一顶点出发无法一次遍历所有顶点。
• 最小生成树不是唯一的，即树形不唯一。当图中的各边权值互不相等时，G的最小生成树是唯一的。
• 最小生成树的边数为顶点数减一。
• prim算法适合求解边稠密的图的最小生成树。在Kruskal中采用堆来存放边的集合。（prim选定一个顶点然后从此顶点出发选取权值最小的边，之后下一个顶点进入集合，依次寻找；Kruskal则是在最开始先找权值最小的边进入集合，按照权值由小到大的顺序进行边进集合）
• 广搜针对无权图，若图是带权的，带权最短的路径称为最短路径。dijkstra是求单源最短路径，Floyd是求两对顶点之间的最短路径。（P214表仔细理解，dijkstra不适合边上有负权值的图；floyd执行过程floyd允许有负权值的边存在，但不允许有负权值组成的边的回路）。
• 拓扑排序（删除无前驱的结点输出，然后删除结束之后，找现在没有前驱的点，以此类推获得排序序列）。
• 关键路径看上面的图。