数据结构(图)

• 线性结构中，元素仅有线性关系，每个元素只有一个直接前驱和直接后继；
• 树形结构中，数据元素（结点）之间有着明显的层次关系，每层上的元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；
• 图形结构中，数据元素（顶点）之间具有任意关系，图中任意两个数据元素之间都可能相关。

(1) 图的定义

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

1. 无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi，Vj) 来表示。如下左图，G= (V1,{E1})，其中顶点集合V1={A，B，C，D}; 边集合E1={ (A,B) ，（B,C），(C,D)， (D,A) , (A,C) } 。圆括号
2. 有向边：若从顶点Vi 到Vj的边有方向，则称这条边为有向边，也称为弧。用有序偶〈Vi,Vj>来表示， Vi称为弧尾， Vj称为弧头。 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，表示弧，注意不能写成。如下右图，G= (V2,{E2})，其中顶点集合V2={A，B，C，D}; 弧集合E2={，，，}。尖括号

(2) 图的基本术语

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

2. 无向完全图和有向完全能图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n (n-1) 条边。
3. 稀疏图和稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，这里的概念是相对而言的。

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

5. 邻接点：对于无向图G= (V,{E})， 如果边(v,v&＃8217;)属于E， 则称顶点v和v‘互为邻接点，即v和v&＃8217;相邻接、边(v,v&＃8217;)依附于顶点v和v&＃8217;，或者说(v,v&＃8217;)与顶点v和v&＃8217;相关联。
6. 度、入度和出度：点v的度是和v相关联的边的数目，记为TD(v)。如上图左侧上方的无向图，顶点A与B互为邻接点，边(A，B) 依附于顶点A 与B 上，顶点A 的度为3。而此图的边数是5，各个顶点度的和=3+2+3+2=10，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。
   对于有向图G= (V,{E})，如果弧属于E，则称顶点v邻接到顶点v&＃8217;，顶点v&＃8217;邻接自顶点v的弧和顶点v， v&＃8217;相关联。以顶点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。

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

   

   10.连通、连通图和连通分量：在无向图G中，如果从顶点v到顶点v&＃8217;有路径，则称v和v&＃8217;是连通的。 如果对于图中任意两个顶点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满足)。 因此它不是图1的无向图的连通分量。

1. 强连通图和强分量：在有向图G中，如果对于每一对vi，vj属于E，vi不等于vj，从vi到vj和vj 到vi都有路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

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

   

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

   

(1)邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为:

如下无向图，

如下有向图

我们知道，每条边上带有权的图叫做网，如果要将这些权值保存下来，可以采用权值代替矩阵中的0、1，权值不存在的元素之间用∞表示，如下图，左图是一个有向网图，右图就是它的邻接矩阵。

邻接矩阵结构：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MVNum 100 /* 最大顶点数，应由用户定义 */
#define MaxInt 65535 //表示极大值，即∞
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VerTexType; /* 顶点类型应由用户定义 */
typedef int ArcType; /* 边上的权值类型应由用户定义 */
typedef struct{
VertexType vexs[MVNum]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
int vexnum, arcnum; /* 图中当前的顶点数和边数 */
}AMGraph;


1. 采用邻接矩阵表示法创建无向网

(1) 输入总顶点数和总边数。
(2) 依次输入点的信息存入顶点表中。
(3) 初始化邻接矩阵，使每个权值初始化为极大值。
(4)构造邻接矩阵。依次输入每条边依附的顶点和其权值。确定两个顶点在图中的位置之后，使相应的边赋予相应的权值，同时使其堆成边赋予相同的权值。
该算法的时间复杂度为O(n*n)

Status CreateUDN(AMGraph &G)
{//采用邻接矩阵表示法，创建无向网G
cin>>G.vexnum>>G.arcnum; //输入总顶点数和总边
for(i=0;i {
cin>>G.vexs[i];//依次输入点的信息
}
for(=0;i for(j=0;j G.arcs[i][j] = MaxInt;//初始化邻接矩阵，边的权值均置为最大值MaxInt
for(k=0;k {
cin>>v1>>v2>>w;//输入一条边依附的顶点及权值
i=LocateVex(G,v1);j=LocateVex(G,v2);que'd
G.arcs[i][j] = w;
G.arcs[j][i] = w;
}
return OK;
}
int LocateVex(AMGraph G,VerTextType u)
{
int i;
for(i=0;i {
if( u == G.vexs[i]) return i;
}
return -1;
}


2.邻接矩阵表示法的优缺点

优点：
（1） 便于判断两个顶点之间是否有 边，即根据A[i][j] = 0或1来判断。
（2） 便于 计算各顶点的度。对于无向图，邻接矩阵的第i行元素之和就是顶点i的度。对于有向图，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度。
缺点：
（1） 不便于增加删除顶点。
（2） 空间复杂度高。如果是有向图，n个顶点需要nn个单元存储边。如果无向图，其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角元素，这样需要n(n-1)/2个单元。无论哪种存储方式，邻接矩阵表示法的空间复杂度均为0(nn)

(2)邻接表

数组与链表相结合的存储方法称为邻接表。
1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

1. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi 的边表，有向图则称为顶点vi作为弧尾的出边表。
   如图是一个无向图的连接表结构，有向图则类似。

   

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

   

图的邻接表存储表示

#define MVNum 100 //最大顶点数
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int OtherType; /* 边上的权值类型应由用户定义 */
typedef struct ArcNode /* 边表结点 */
{
int adjvex; /* 邻接点域,存储该顶点对应的下标 */
OtherType info; /* 用于存储权值,对于非网图可以不需要 */
struct ArcNode *next; /* 链域,指向下一个邻接点 */
}ArcNode;
typedef struct VNode /* 顶点表结点 */
{
VertexType data; /* 顶点域,存储顶点信息 */
ArcNode *firstedge;/* 指向第一条依附顶点的边指针 */
}VNode, AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum,arcnum; /* 图中当前顶点数和边数 */
}ALGraph;


1.采用邻接表表示法创建无向图

(1)输入总顶点数和总边数
(2)依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。
(3) 创建邻接表。依次输入每条边依附的两个顶点，确定这两个顶点的序号i和j之后，将此边结点分别插入vi 和vj对应的两个链表的头部。
该算法的时间复杂度为O（n+e）

Status CreateUDG(ALGraph &G)
{
cin>>G.vexnum>>G.racnum;//输入总顶点数，总边数
for(i=0;i {
cin>>G.vertices[i].data;//输入顶点值
G.vertices[i].firstarc = NULL；//初始化表头结点的指针域为NULL
}
for(k=0k {
cin>>v1>>v2;
i = LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中位置，即顶点G.vertices中的序号
p1 = new ArcNode;//生成一个新的边结点*p1
p1->adjvex = j;//邻接点序号为j
p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//将新结点*p1插入顶点vi的边表头部
p2 = new ArcNode;
p2->adjvex = i;
p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc=p2;
}
return OK;
}


2. 邻接表表示法的优缺点

优点：
（1） 便于增加和删除结点。
（2） 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+e)。
（3）空间效率高。对于一个具有n个顶点e条边的图G，若图G是无向图，则在邻接表表示中有n个顶点表结点和2n个边表结点。若G是有向图，则在它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此，邻接表的空间复杂度为O(n+e)。
缺点：
（1） 不便于判断顶点之间是否有边，要判断vi 和vj之间是否有边，就需扫描第i个边表，最换情况下要耗费O(n)时间。
（2） 不便于计算有向图各个顶点的度。

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

（1） 深度优先遍历

深度优先遍历类似于数的先序遍历，是树的先序遍历的推广。

1. 从图中某个顶点v出发，访问v。
2. 找到刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有未被访问的邻接点为止。
3. 返回前一个访问过得且扔有未被访问的邻接点的顶点，找到该顶点的下一个未被访问的邻接点，访问该顶点。

4. 重复步骤2，3，直至图中所有顶点都被访问过。

   

1. 深度优先遍历算法的实现

为了在遍历过程中便于区分顶点是否已经被访问，需附设访问标志组visited[i]n],其初值为false，一旦某个顶点被访问，则其相应的分量置为true。

深度优先遍历连通图

1. 从图中某个顶点v出发，访问v，并置visited[v]的值为true。
2. 依次检查v 的所有邻接点w，如果visited[w]的值为false，再从w出发进行递归遍历，直至图中所有顶点都被访问过。

bool visited[MVNum];//访问标志数组，其初值为false
void DFS(Graph G,int v)
{//从v个顶点出发递归地深度优先遍历图
cout< for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w))
//依次检查v的所有邻接点w，FirstAdjVex(G,v)表示v第一个邻接点
//NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w>0表示有邻接点。
if(!visited[w]) DFS(G,w);//对于v的尚未访问的邻接顶点w递归调用DFS
}


深度优先遍历非连通图

void DFSTraverse(Graph G)
{
for(v=0;v for(v=0;v}


采用邻接矩阵表示图的深度优先遍历

void DFS_AM(AMGraph G,int v)
{//图G为邻接矩阵类型，从v个顶点出发深度优先遍历图G
cout< for(w=0;w {
if((G.arcs[v][w] !=0)&& (!visited[w])) DFS_AM(G,w);
//G.arcs[v][w] != 0 表示w是v的邻接点，如果w未被访问，则递归调用DFS_AM
}
}


采用邻接表表示图的深度优先遍历

void DFS_AL(ALGraph G ,int v)
{//图G为邻接表类型，从v个顶点出发的深度优先遍历图
cout < p= G.vertices[v].firstarc;//p指向v的边链表的第一个结点
while(P!=NULL)//边结点非空
{
w = p->adjvex;表示w是v 的邻接点
if(!visited[w]) DFS_AL(G,w);//如果w未被访问，则递归调用DFS_AL
p=p->nexttrac;//p指向下一个边结点
}
}


(2)广度优先遍历

图的广度优先遍历就类似于树的层序遍历。

1. 从图中某个顶点v出发，访问v。
2. 依次访问v的各个未被访问过得邻接点。

3. 分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤3，直至图中所有已被访问的顶点的邻接点都被访问到。

   

1.广度优先遍历连通图

1. 从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。
2. 只要队列不为空，则重复下述操作：

• 队头顶点u出队。
• 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w,并置visited[w]的值为true。然后将w进队。

void BFS(Graph G,int v)
{
cout< InitQueue(Q);//辅助队列Q初始化，置空
EnQueue(Q,v);//v进队
while(!QueueEmpty(Q))//队列非空
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
{//依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点
//NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w>=0表示存在邻接点
if(!visited[w])//w为u的尚未访问的邻接顶点
{
cout< EnQueue(Q,w);//w进队
}
}
}
}
4. 图的应用

(1) 最小生成树

如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。

1. 普利姆（Prim）算法

假设N=(V,E)是连通图，TE是N上的最小生成树中边的集合。

1. U={u0}(u0∈V)， TE={ }。
2. 在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价(权值)最小的边(u0，v0) 并入集合TE，同时v0并入U。

3. 重复2，直至U=V为止。
   此时TE中必有n-1条边，则T= (V,{TE}) 为N的最小生成树。

   

算法步骤：
为实现这个算法需附设一个辅助数组closedge,以记录从U到V-U具有最小权值的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，他包含2个域：lowcost和adjvex,其中lowcost存储最小边上的权值，adjvex存储最小边在U中的那个顶点。显然closedge[i-1].lowcost = Min{cost(u,vi)|u∈U},其中cost(u,v)表示赋予边（u,v）的权。

struct
{
VerTextType adjvex;//最小边在U中的那个顶点
ArcType lowcost;//最小边上的权值
}closedge[MVNum];


1. 首先将初始顶点u加入U中，对于其余的每一个顶点vj,将closedeg[j]均初始化为到u的边信息。
2. 循环n-1次，做如下处理：

• 从各组边closedeg中选出最小边closedge[k],输出此边。
• 将k加入U中。
• 更新剩余的每组最小边信息closedeg[j],对于V-U中的边，新增加一条从k到j的边，如果新边的权值比closedeg[j].lowcost小，则将closedge[j].lowcost更新为新边的权值。

void MiniSpanTree_Prim(AMGraph G,VerTexType u)
{//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树，输出T的各条边
k = LocateVex(G,u);//k为顶点u的下标
for(j=0 ;j if (j!=k) closedge[j] = {u,G.arcs[k][j]};//{adjvex,lowcost}
closedeg[k].lowcost = 0;//初始，U={u}
for(i=1;i {//选择其余n-1个顶点，生成n-1条边（n = G.vexnum）
k= Min(colsedge);
//求出T的下一个结点，第k个顶点，closedge[k]中存有当前最小边
u0 = closedge[k].adjvex;//u0为最小边的一个顶点，u0 ∈U
v0 = G.vexs[k];//v0为最小边的另一个顶点，v0∈V-U
cout< closedge[k].lowcost = 0;//第k个顶点并入U集
for(j=0;j if(G.arcs[k][j] colsedge[j] = {G.vexs[k],G.arcs[k][j]};
}
}


2. 克鲁斯卡算法

假设连通网N=(V,E),将N中的边按权值从小到大的顺序排列。

1. 初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。
2. 在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中(即不形成回路)，否则舍去此边而选择下一条代价最小的边。

3. 重复2，直至T中所有顶点都在同一个连通分量上为止。

   

   算法的实现要引入以下辅助的数据结构。

1. 结构体数组Edge:存储边的信息，包括边的两个顶点信息和权值。

struct
{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost; // 边上的权值
}Edge[arcnum]


1. Vexset[i]:标识各个顶点所属的连通分量。对每个顶点vi∈V ,在辅助数组存在一个相应元素Vexset[i]表示该顶点所在连通分量。初始时Vexset[i],表示各个顶点自成一个连通分量。

int Vexset[Mvnum];


算法步骤：

1. 将数组Edge中的元素按权值从小到大排序。
2. 依次查看数组Edge中的边，循环执行以下操作：

• 依次从排序好的数组Edge中选出一条边（U1,U2）
• 在Vexset中分别查找v1和v2 所在的连通分量vs1 和vs2，并进行判断：

*如果vs1 和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1 和vs2两个连通分量。
*如果vs1 和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。

void MiniSpanTree_Kruskal(MGraph G)
{//无向网以邻接矩阵形式存储，构造G的最小数T，输出T的各条边
sort(Edge);//将数组Edge中的元素按权值从小到大排序
for(i=0;i Vexset[i] = i;
for(i=0;i {
v1 = LocateVex(G,Edge[i].Head);//v1为边的始点Head的下标
v2 = LocateVex(G,Edge[i].Tail);//v2为边的终点Tail的下标
vs1 = Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1
vs2 = Vexset[v2];//获取边Edge[i]的终点所在的连通分量vs2
if(vs1 != vs2)//边的两个顶点分属不同的连通分量
{
cout < for(j=0 ; j if(Vexset[j] == vs2) Vexset[j] =vs1;//集合编号为vs2的都改为vs1
}
}
}


(2) 最短路径

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。关于最短路径主要有两种算法，迪杰斯特拉(Dijkstra) 算法和弗洛伊德(Floyd) 算法。

1. 迪杰斯特拉算法

从某个源点到其余各顶点的最短路径

对于网N=（V，E），将N中的顶点分成两组：
第一组S：已求出的最短路径的终点集合（初始时只包含源点v0）。
第二组V-S：尚未求出最短路径的终点集合（初始时V-{v0}）。
算法将各项顶点与v0 间最短路径长度递增的次序，逐个将集合V-S的顶点加入集合S中去。在这个过程中，总保持从v0到集合S中各顶点的路径长度始终不大于到集合V-S中各顶点x 的路径。

算法的实现要引入以下辅助数据结构

1. 一位数组S[i]:记录从源点v0到终点vi是否已被确定最短路径长度，true表示确定，false表示尚未确定。
2. 一位数组Path[i]：记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号。其初始值为：如果从v0到vi有弧，则Path[i]为v0,否则为-1。

3. 一位数组D[i]:记录从源点v0到终点vi的当前最短路径长度。其初始值为：如果从v0到vi有弧，则D[i]为弧上的权值，否则为∞。
   显然，长度最短的一条最短路径必为（v0,vk），满足以下条件：
   D[k] = Min{D[i]|vi∈V-S}
   求得顶点vk的最短路径后，将其加入到第一组顶点集S中。
   每当加入一个新的顶点到顶点集S，对第二组剩余的各个顶点而言，多一个中转顶点，从而多一个中转路径，所以要对第二组剩余的各个顶点的最短路径长度进行更新。
   原来v0到vi的最短路径长度为D[i],加入k作为中间顶点的中转路径长度为：D[k]+Garcs[k][i],若D[k]+Garcs[k][i] 更新后，再选择数组D中值最小的顶点加入到第一组顶点集S中，如此进行下去，直至图中所有顶点到第一组顶点集S中为止。

   
   
   

2. 弗洛伊德算法

每个顶点之间的最短路径

(3) 拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。AOV网中的弧表示活动之间存在的某种制约关系，且不能存在回路。 设G=(V，E)是一个具有n个顶点的有向图， V中的顶点序列v1，v2，……， vn, 满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 则称这样的顶点序列为一个拓扑序列。所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环(回路)的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。
拓扑排序的基本思路是: 从AOV网中选择一个入度为0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。整个算法的时间复杂度为O(n+e)。

https://blog.csdn.net/qq_35644234/article/details/60578189

(4) 关键路径

https://blog.csdn.net/qq_35644234/article/details/52664108