【数据结构与算法】——第六章：图

 ============================ 【说明】 ===================================================
  大家好，本专栏是 数据结构与算法， 该科目是计算机类专业必修课之一，比较重要也比较基础，有想从事算法研究的同学，这些内容是专/本科、甚至硕士期间较为基础的内容，适用范围较广：大学专业课学习、考研复习等。
  通过自己的理解进行整理，希望大家积极交流、探讨，多给意见。后面也会给大家更新其他一些知识。若有侵权，联系删除！共同维护网络知识权利！

---

1、图的定义

  在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。
  在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。这和一对父母可以有多个孩子，但每个孩子却只能有一对父母是一个道理。

  可现实中，人与人之间关系就非常复杂，比如我认识的朋友，可能他们之间也互相认识，这就不是简单的一对一、一对多，研究人际关系很自然会考虑多对多的情况。

  今天要研究的主题一一图。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

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

  
   对于图的定义，我们需要明确几个注意的地方:

   1、线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
   2、线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。那么对于图呢？在图结构中，不允许没有顶点。在定义中，若v是顶点的集合，则强调了顶点集合v有穷非空。
   3、线性表中，相邻的数据元素之间具有线性关系；树结构中，相邻两层的结点具有层次关系；而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

  

1.1 图的其他定义

   (1) 无向图与有向图

  无向边：若顶点到顶点之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
  下图就是一个无向图，由于是无方向的，连接顶点A 与D的边，可以表示成无序对(A，D)，也可以写成(D，A)。对于下图中的无向图G1来说，G1= (V1,{E1})，其中顶点集合V1={A,B,C,D}，边集合E1={ (A,B)，(B,C), (C,D)，(D,A) , (A,C) }。

  有向边：若从顶点到顶点的边有方向，则称这条边为有向边，也称为弧。用有序偶<vi,vj>来表示，vi称为弧尾，vj称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。
  下图就是一个有向图。连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A，D>表示弧，注意不能写成<D，A>。对于下图中的有向图G2来说，G2=（V2，{E2}），其中顶点集合V2={A,B,C,D}，弧集合E2={<A,D>,<B,A>,<C,A>,<B,C>}。

  注意：无向边用小括号“()”表示，而有向边则是用尖括号“<>”表示。

  
   (2) 无向完全图与有向完全图

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

  例：下图就是无向完全图，因为每个顶点都要与除它以外的顶点连线，顶点A与BCD三个顶点连线，共有四个顶点，自然是4 × 3，但由于顶点A与顶点B连线后，计算B与A连线就是重复，因此要整体除以2，共有6条边。

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

  总结：从这里也可以得到结论，对于具有n个顶点和e条边数的图，无向图0 ≤ e ≤ n *(n -1) /2，有向图0 ≤ e ≤n*(n-1)。

  
   (3) 稀疏图、稠密图、网

   有很少条边或弧的图称为稀疏图，反之称为稠密图。这里稀疏和稠密是模糊的概念，都是相对而言的。
   有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
   这种带权的图通常称为网。下图就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。

  
   (4) 子图

   假设有两个图G= (V,{E})和G'= (V'{E’}),如果V'⊆V且U'⊆U 则称G'为G的子图。

   例下图带底纹的图均为左侧无向图与有向图的子图。

  

1.2 图的顶点与边之间的关系

   (1) 度

   对于无向图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) +0D (v)。

   例如：下图的有向图，顶点A的入度是2（从B到A的弧，从C到A的弧),出度是1（从A到D的弧），所以顶点A的度为2+ 1=3。

  
   (2) 路径

  无向图G= (V,{E))中从顶点v到顶点v’的路径是一个顶点序列。例如下图中就列举了顶点B到顶点D四种不同的路径：

  如果G是有向图，则路径也是有向的，例如下图，顶点B到D有两种路径。而顶点A到B,就不存在路径：

   注：树中根结点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却是不唯一。

  
   (3) 其他

  路径的长度是路径上的边或弧的数目。
  第一个顶点到最后一个顶点相同的路径称为回路或环。
  序列中顶点不重复出现的路径称为简单路径。
  除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

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

  

1.3 连通图相关术语

   在无向图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、子图要是连通的，
   3、连通子图含有极大顶点数
   4、具有极大顶点数的连通子图包含依附于这些顶点的所有边。

   例如：下图的图1是一个无向非连通图。但是它有两个连通分量，即图2和图3。而图4，尽管是图1的子图，但是它却不满足连通子图的极大顶点数（图2满足）。因此它不是图1的无向图的连通分。

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

   例如：下图1并不是强连通图，因为顶点A到顶点D存在路径，而D到A就不存在。图2不是强连通图，而且显然图2是图1的极大强连通子图，即是它的强连通分量。

---

2、图的存储结构

   图的存储结构相比较线性表与树来说就更加复杂了。
   首先，我们口头上说的“顶点的位置”或“邻接点的位置"只是一个相对的概念。其实从图的逻辑结构定义来看，图上任何一个顶点都可被看成是第一个顶点，任一顶点的邻接点之间也不存在次序关系。

   比如下图的四张图，仔细观察发现，它们其实是同一个图，只不过顶点的位置不同，就造成了表象上不太一样的感觉。

   也正由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。

   对于图来说，如何对它实现物理存储是个难题，但是已经解决，以下提供多种不同的存储结构：

  

2.1 邻接矩阵

   考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。

  顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一维搞不定，那就考虑用一个二维数组来存储。于是我们的邻接矩阵的方案就诞生了。

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

   设图G有n个顶点，则邻接矩阵是一个nXn的方阵，定义为:

   例如：下图就是一个无向图：

   我们可以设置两个数组，顶点数组为vertex[4] ={ v0，v1,v2,v3}，边数组arc[4][4]为上图图这样的一个矩阵。解释一下矩阵，无向图的边数组是一个对称矩阵。

  有了这个矩阵，我们就可以很容易地知道图中的信息：

  1、我们要判定任意两顶点是否有边无边就非常容易了；
  2、我们要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i 列）的元素之和。比如顶点V1的度就是1+0+ 1+0=2；
  3、求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

---

   例如：我们再来看一个有向图样例，如下图：

   有向图讲究入度与出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第V1行的各数之和。

   与无向图同样的办法，判断顶点到vj是否存在弧，只需要查找矩阵中arc[i][j]是否为1即可。要求Vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找arc [i][j] 为1的顶点。

---

   前面在图的概念中，我们提到了网的概念。也就是每条边上带有权的图叫做网。那么这些权值就需要存下来，如何处理这个矩阵来适应这个需求呢？

  设图G是网图，有n个顶点，则邻接矩阵是一个 n*n的方阵，定义为:

  这里表示(vi,vj)或<vi,vj>上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下图的左图就是一个有向网图，右图就是它的邻接矩阵：

  

2.2 邻接表

   邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。 比如说：如果我们要处理下图这样的稀疏有向图，邻接矩阵中除了arc[1][0]有权值外，没有其他弧，其实这些存储空间都浪费掉了。

   因此我们考虑另外一种存储结构方式：

   回忆下在 线性表时谈到，顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

   再回忆在 树中谈存储结构时，讲到了一种孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题。

   以上两种思路同样适用于图的存储。我们把这种数组与链表相结合的存储方法称为 邻接表 。

   邻接表的处理办法是这样：

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

   例如：下图所示的就是一个无向图的邻接表结构：

   从图中我们知道，顶点表的各个结点由data和firstedge两个域表示。data是数据域，存储顶点的信息；firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。

   边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标；next则存储指向边表中下一个结点的指针。

  这样的结构，对于我们要获得图的相关信息也是很方便的：
  1、比如我们要想知道某个顶点的度，就去查找这个顶点的边表中结点的个数。
  2、若要判断顶点vi到vj是否存在边，只需要测试顶点vi的边表中adjvex是否存在结点vj的下标j就行了。
  3、若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点。

---

  若是有向图，邻接表结构是类似的，比如下图中第一幅图的邻接表就是第二幅图。
  但要注意的是有向图由于有方向，我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。

  但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的 逆邻接表，即对每个顶vi点都建立一个链接为vi为弧头的表。如下图第三幅图所示。

   其他存储方式还有：十字链表、邻接多重表、边集数组。有兴趣的请查阅其他相关资料。

---

3、图的遍历

   图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做 图的遍历。通常有两种遍历次序方案：深度优先遍历和广度优先遍历。

  

3.1 深度优先遍历

   深度优先遍历(Depth-First-Search),也有称为深度优先搜索，简称为DFS。

   深度优先遍历其实就是一个递归的过程，其实转换成如上图的右图后，就像是一棵树的前序遍历。
   它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。

  

3.2 广度优先遍历

   广度优先遍历(Breadth-first-search)，又称广度优先搜索，简称BFS。类似树的层序遍历。

---

   不过如果图顶点和边非常多，不能在短时间内遍历完成，遍历的目的是为了寻找合适的顶点，那么选择哪种遍历就要仔细斟酌了。
   深度优先更适合目标比较明确，以找到目标为主要目的的情况；而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

   对于深度和广度而言，已经不是简单的算法实现问题，完全可以上升到方法论的角度。你求学是博览群书，还是深钻细研；你旅游是走马观花、蜻蜓点水，还是下马看花、深度体验；你交友是四海之内皆兄弟，还是人生得一知己足矣……其实都无对错之分，只视不同人的理解而有了不同的诠释。

4、最小生成树

   假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，村庄位置大致如下图，其中v0-v8是村庄，之间连线的数字表示村与村间的可通达的直线距离，比如v0至V1就是10公里（个别如v0与v6，v6与v8，v5与v7未测算距离是因为有高山或湖泊，不予考虑)。你们领导要求你必须用最小的成本完成这次任务。你会怎么办？

   一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为 最小生成树。

  经典的有两种算法， 普里姆算法和克鲁斯卡尔算法。

4.1 普利姆算法(Prim)

  为了能讲明白这个算法，我们先构造如下图的邻接矩阵：

  1、程序开始运行，我们由第4-5行，创建了两个一维数组lowcost和adjvex，长度都为顶点个数9。
  2、第6、7行我们分别给这两个数组的第一个下标位赋值为0，arjvex[0]=0其实意思就是我们现在从顶点v0开始（事实上，最小生成树从哪个顶点开始计算都无所谓，我们假定从v0开始），lowcost[0]=0就表示v0已经被纳人到最小生成树中，之后凡是lowcost数组中的值被设置为0就是表示此下标的顶点被纳人最小生成树。
  3、第8-12行表示我们读取邻接矩阵的第一行数据。将数值赋值给lowcost数组，所以此时lowcost数组值为 {0，10，65535，6553s65535，11，65535，65535，65535}，而adjvex则全部为0。

  4、第13-36行，整个循环过程就是构造最小生成树的过程。
  5、第15-16行，将min设置为了一个极大值65535，它的目的是为了之后找到一定范围内的最小权值。j是用来做顶点下标循环的变量，k是用来存储最小权值的顶点下标。
  6、第17-25行，循环中不断修改min为当前lowcost数组中最小值，并用k保留此最小值的顶点下标。经过循环后，min=10，k=1。注意19行if判断的lowcost[j]！=0表示已经是生成树的顶点不参与最小权值的查找。

  7、第26行，因k=1, adjvex[1]=0，所以打印结果为（0，1),表示v。至VI边为最小生成树的第一条边。如下图所示。

  8、第27行，此时因k=1我们将lowcost[k]=0就是说顶点V1纳人到最小生成树中。此时lowcost数组值为{0，0，65535，65535，65535，11，6553s，6s535，65535}。

  9、第28-35行，j循环由1至8，因k=1，查找邻接矩阵的第V1行的各个权值，与lowcost的对应值比较，若更小则修改lowcost值，并将k值存入 adjvex数组中。因第V1行有18、16、12均比65535小，所以最终lowcost数组的值为：{0，0，18，65535，11，16，65535，12}。adjvex数组的值为：{0，0，1，0，0，0，1，0，1}。这里第30行if判断的lowcost[j]！=0也说明v0和V1已经是生成树的顶点不参与最小权值的比对了。
  10、再次循环，由第15行到第26行，此时min=11，k=5，adjvex[5]=0。因此打印结果为（0，5）。表示v0至v5边为最小生成树的第二条边，如下图所示：

  11、接下来执行到36行，lowcost数组的值为：{0，0，18，65535，26，0，16，65535， 12}。adjvex数组的值为：{0，0，1,0，5，0，1，0，1}。

  12、之后，可以自己去模拟。通过不断的转换，构造的过程如下图所示结果。

4.2 克鲁斯卡尔(kruskal)

  通俗点讲：克鲁斯卡尔主要是找图中最小权值的边，直至所有顶点相连，但是要注意：整个过程中不能形成回路！

---

  对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

5、最短路径

  现实中，每个人需求不同，选择方案就不尽相同。有人为了省钱，它需要的是路程最短（定价以路程长短为标准），但可能由于线路班次少，换乘站间距离长等原因并不省时间；而另一些人，为了要赶飞机火车或者早晨上班不迟到，他最大的需求是总时间要短；还有一类人，如老人行动不便，或者上班族下班，忙碌一天累得要死，他们都不想多走路，哪怕车子绕远路耗时长也无所谓，关键是换乘要少，这样可以在车上好好休息一下（有些线路方案换乘两次比换乘三四次耗时还长）。
  这些都是老百姓的需求，简单的图形可以靠人的经验和感觉，但复杂的道路或地铁网就需要计算机通过算法计算来提供最佳的方案。我们今天就要来研究关于图的最短路径的问题。

5.1 迪杰斯特拉(Dijkstra)算法

  大致明白，这个迪杰斯特拉（Dijkstra)算法是如何干活的了。
  它并不是一下子就求出了v0到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

5.2 弗洛伊德(Floyd)算法

6、拓扑排序

  我们会把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待，所有的工程都可分为若干个“活动”的子工程。
  例如下图是非专业人士绘制的一张电影制作流程图，现实中可能并不完全相同，但基本表达了一个工程和若干个活动的概念。
  在这些活动之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。就像电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。因此这样的工程图，一定是无环的有向图。

  在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。AOV网中的弧表示活动之间存在的某种制约关系。

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

  所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

  构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；
  如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是AOV网。

  一个不存在回路的AOV网，我们可以将它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。

7、关键路径

  在前面讲了AOV网的基础上，我们来介绍一个新的概念。
  在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网(Activity On Edge Network)。

  我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE网只有一个源点一个汇点。

  如下图就是一个AOE网。其中V0即是源点，v0表示一个工程的开始，V9是汇点，表示整个工程的结束，顶点v0，v1,…,v9分别表示事件。弧<v0，v1>，<V0， V2>…都表示一个活动，用a0，a1,…,a12表示，它们的值代表着活动持续的时间，比如弧<v0，v1>就是从源点开始的第一个活动 a0，它的时间是3个单位。

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

  案例：

  假设一个学生放学回家，除掉吃饭、洗漱外，到睡觉前有四小时空闲，而家庭作业需要两小时完成。
  不同的学生会有不同的做法，抓紧的学生，会在头两小时就完成作业，然后看看电视、读读课外书什么的；但也有超过一半的学生会在最后两小时才去做作业，要不是因为没时间，可能还要再拖延下去。
  这里做家庭作业这一活动的最早开始时间是四小时的开始，可理解为0，而最晚开始时间是两小时之后马上开始，不可以再晚，否则就是延迟了，此时可以理解为 2。显然，当最早和最晚开始时间不相等时就意味着有空闲。
  接着，你老妈发现了你拖延的小秘密，于是买了很多的课外习题，要求你四个小时，不许有一丝空闲，省得你拖延或偷懒。此时整个四小时全部被占满，最早开始时间和最晚开始时间都是0，因此它就是关键活动了。

  也就是说，我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。

  为此，定义如下几个参数。
  1、事件的最早发生时间etv：即顶点的最早发生时间;
  2、事件的最晚发生时间ltv：即顶点Vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期;
  3、活动的最早开工时间ete ：即弧ak的最早发生时间。
  4、活动的最晚开工时间Ite：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。

  上图中的结果：

  关键路径为：v0–>v2–>v3–>v4–>v7–>v8–>v9
  关键活动为：a1、a4、a6、a8、a11、a12

  关键路径不一定唯一。