数据结构-图的相关概念

算法与数据结构

图

图(Graph)的定义：由顶点的有穷非空集合（在图结构中不允许没有顶点）和顶点之间边的集合组成，通常表示为:G(V,E)，其中，G是一个图，V是图G中顶点的集合，E是图G中边的集合。
图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
顶点 (Vertex) ：图中数据元素

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(Vi,Vj)来表示
无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图(Undirected graphs)
由于是无方向的，连接顶点A与D的边可以表示成无序对（A,D）也可以写成（D,A）

有向边:若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc）
，用有序偶来表示， Vi称为弧尾（Tail），Vj称为弧头（Head）
有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图(Directed graphs)
连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，表示弧

简单图：在图中若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
非简单图：

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

结论：对于具有n个顶点和e条边数的图，无向图0<=e<=(n-1)/2，有向图0<=e<=n(n-1)
稀疏图和稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图。这里稀疏和稠密是模糊的概念，都是相对而言的

网：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图称为网(Network)

子图：假设有两个图G=(V,{E})和G'=(V',{E'})，如果V∈V'且E∈E'，则称G'为 G子图(Subgraph)

(带底纹的图均为左侧无向图与有向图的子图)

邻接点：
对于无向图G=(V,{E})，如果边(V,V')∈E，则称顶点V和V'互为邻接点(Adjacent)，即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，即：边数其实就是各顶点度数和的一半，多出的一半是因为重复两次记数。记为：$e=1/2\sum_{i=1}^n TD(Vi)$

对于有向图G=(V,{E})，如果弧∈E，则称顶点 V邻接到顶点V'，顶点 V'邻接自顶点V，弧和顶点V,V'相关联。以顶点V为头的弧的数自称为V的入度（InDegree），记为ID(V);以V为尾的弧的数目称为V的出度（OutDegree），记为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，所以得到$e=\sum_{i=1}^nID(Vi)=\sum_{i=1}^nOD(Vi)$

路径的长度：路径上的边或弧的数目

回路：第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）
简单路径：序列中顶点不重复出现的路径称为简单路径
简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环

（粗线构成的环，左侧的环因第一个顶点和最后一个顶点都是B，且C,D,A没有重复出现，因此是一个简单环，而右侧的环由于顶点C的重复，它就不是简单环了）

连通图：在无向图G中，如果从顶点V到顶点V'有路径，则称V和V'是连通的。如果对于图中任意两个顶点Vi、Vj∈E，Vi和VJ都是连通的，则称G是连通图（Connected Graph）
非连通图：

连通图：

连通分量：无向图中的极大连通子图称为连通分量
• 要是子图;
• 图要是连通的;
• 连通子图含有极大顶点数;
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
以上无向非连通图的连通分量：
和

强连通图和强连通分量：在有向图G中，如果对于每一对Vi、Vj∈V、Vi！=Vj，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量

连通图的生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的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有向图的生成森林

图的存储结构

1、邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
$arc[i][j] = \begin{cases} 0, &\text{若(Vi,Vj)∈E或<Vi,Vj>∈E} \\ 1, &\text{反之} \end{cases}$

无向图的邻接矩阵：

对于矩阵的主对角线的值，即arc[0][0]、arc1、arc2、arc3，全为0是因为不存在顶点到自身的边，比如V0到V0。arc0=1是因为V0到V1的边存在，而arc1=0是因为V1到V3的边不存在。并且由于是无向图，V1到V3的边不存在，意味着V3到V1的边也不存在。所以无向图的边数组是一个对称矩阵。

根据这个矩阵，可知：

• 要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。比如顶点v1的度就是1+0+1+0=2
• 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点

有向图的邻接矩阵：

因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到arc1[0]=1，而v0到v1没有弧，因此arc0=0。 有向图讲究入度与出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。 与无向图同样的办法，判断顶点vi到vj是否存在弧，只需要查找矩阵中arc[i][j]是否为1即可。要求vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找arc[i][j]为1的顶点。

网的邻接矩阵：
设图G是网图，有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
$arc[i][j] = \begin{cases} Wij, &\text{若(Vi,Vj)∈E或<Vi,Vj>∈E} \\ 0, &\text{若i = j} \\ ∞, &\text{反之} \end{cases}$
这里Wij表示(Vi,Vj)或上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。不为0的原因在于权值Wij大多数情况下是正值，但个别时候可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。下就是一个有向网图，右图就是它的邻接矩阵：

2、邻接表

邻接矩阵对于边数相对顶点较少的图，存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。使用数组与链表相结合的存储方式，就诞生了邻接表（Ad-jacency List）

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

邻接表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。

有向图的邻接表：

有向图由于有方向，以顶点为弧尾来存储边表，这样就很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立一个链接为vi为弧头的表

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

3、十字链表

那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况
把邻接表与逆邻接表结合起来，这就是十字链表（Orthogonal List）
顶点表结点结构：

边表结点结构：

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值

虚线箭头其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中headvex为0的结点，如上图中的①。接着由入边结点的headlink指向下一个入边顶点v2，如图中的②。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如图中的③。顶点v2和v3也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

4、邻接多重表

如果在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，却是比较繁琐的。因此可以仿照十字链表的方式，对边表结点的结构进行一些改造
重新定义的边表结点结构：

其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构

邻接多重表构造过程：
① 先把顶点与边表节点画出；如下图，由于是无向图，所以ivex是0、jvex是1还是反过来都是无所谓的，不过为了绘图方便，都将ivex值设置得与一旁的顶点下标相同。

② 开始连线，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同；

③ 接着，由于顶点v0的(v0,v1)边的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。

④ 同样的道理，连线⑦就是指(v1,v0)这条边，它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附，所以在③之后就有了⑧⑨。连线⑩的就是顶点v3在连线④之后的下一条边。
（左图一共有5条边，所以右图有10条连线，完全符合预期）

邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的(v0,v2)这条边，只需要将右图的⑥⑨的链接指向改为∧即可

5、边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成，如下图：

边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。

图的遍历

图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）

图的遍历要比树的遍历复杂的多，因为它的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1

1、深度优先遍历

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS

遍历过程：
首先从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F，可以定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看上图的右图。此时发现有三条分支，分别通向顶点C、I、G，右手通行原则，使得我们走到了C顶点。就这样一直顺着右手通道走，一直走到F顶点。当依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时退回到顶点F，走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H，当面对通向H的两条通道D和E时，会发现都已经走过了。
此时是否已经遍历了所有顶点呢？没有。可能还有很多分支的顶点没有走到，所以按原路返回。在顶点H处，再无通道没走过，返回到G，也无未走过通道，返回到F，没有通道，返回到E，有一条通道通往H的通道，验证后也是走过的，再返回到顶点D，此时还有三条道未走过，一条条来，H走过了，G走过了，I，哦，这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A，确认已经完成遍历任务，找到了所有的9个顶点。

深度优先遍历其实就是一个递归的过程，就像是一棵树的前序遍历。从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

2、广度优先遍历

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。如下图，把深度优先遍历图形案例变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层，此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的

最小生成树

最小生成树（Minimum Cost SpanningTree）:一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边，我们把构造连通网的最小代价生成树称为最小生成树
找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法

1、普里姆（Prim）算法

使用邻接矩阵存储网：

2、克鲁斯卡尔（Kruskal）算法

普里姆（Prim）算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的，同样的，也可以以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树是很自然的想法，只不过构建时要考虑是否会形成环路。此时要用到了图的存储结构中的边集数组结构。

克鲁斯卡尔（Kruskal）算法的实现定义：

假设N=(V,{E})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}}，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止

此算法的Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为O(eloge)。
克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大\的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

最短路径

最短路径：对于非网图来说，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；对于网图来说，最短路径是指两顶点之间经过的边上权值之和最少的路径，并且称路径上的第一个顶点是源点，最后一个顶点是终点

1、迪杰斯特拉（Dijkstra）算法

迪杰斯特拉算法是一个按路径长度递增的次序产生最短路径的算法

2、弗洛伊德（Floyd）算法

拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网（ActivityOn Vertex Network）。AOV网中的弧表示活动之间存在的某种制约关系。比如演职人员确定了，场地也联系好了，才可以开始进场拍摄。另外就是AOV网中不能存在回路。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，……，vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。

上图这样的AOV网的拓扑序列不止一条。序列v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 是一条拓扑序列，而v0 v1 v4 v3 v2 v7 v6 v5 v8 v10 v9 v12 v11 v14 v13 v15 v16也是一条拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是AOV网。

拓扑排序算法：

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止

由于拓扑排序的过程中，需要删除顶点，所以邻接表会更加方便。为AOV网构建一个邻接表。考虑到算法过程中始终要查找入度为0的顶点，所以在原来顶点表结点结构中，增加一个入度域in，结构为：in|data|first|edge
因此对于上图的AOV网，我们可以得到如下的邻接表数据结构：

关键路径

拓扑排序主要是为解决一个工程能否顺序进行的问题，而关键路径是解决工程完成需要的最短时间问题。

AOE网: 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网为AOE网（Activity On Edge Net-work）。AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。正常情况下，AOE网只有一个源点一个汇点。

关键路径： AOE网路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

1、关键路径算法原理

找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。
为此，需要定义如下几个参数

1. 事件的最早发生时间etv（earliest time ofvertex）：即顶点vk的最早发生时间；
2. 事件的最晚发生时间ltv（latest time ofvertex）：即顶点vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期；
3. 活动的最早开工时间ete（earliest time ofedge）：即弧ak的最早发生时间；
4. 活动的最晚开工时间lte（latest time ofedge）：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。

由1和2可以求得3和4，然后再根据ete[k]是否与lte[k]相等来判断ak是否是关键活动。

2、关键路径算法