数据结构第六章图

程序员文章站 2023-12-24 09:22:09

...

6.1 图的逻辑结构

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E)
其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。
在线性表中，元素个数可以为零，称为空表；
在树中，结点个数可以为零，称为空树；
在图中，顶点个数不能为零，但可以没有边。

若顶点v_i和v_j之间的边没有方向，则称这条边为无向边，表示为(v_i,v_j)。
如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。
若从顶点v_i到v_j的边有方向，则称这条边为有向边，表示为<v_i,v_j>。
如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。
简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。

数据结构中讨论的都是简单图。

邻接、依附
无向图中，对于任意两个顶点v_i和顶点v_j，若存在边(v_i，v_j)，则称顶点v_i和顶点v_j互为邻接点，同时称边(v_i，v_j)依附于顶点v_i和顶点v_j。
有向图中，对于任意两个顶点v_i和顶点v_j，若存在弧<v_i，v_j>，则称顶点v_i邻接到顶点v_j，顶点v_j邻接自顶点v_i，同时称弧<v_i，v_j>依附于顶点v_i和顶点v_j 。

在线性结构中，数据元素之间仅具有线性关系；
在树结构中，结点之间具有层次关系；
在图结构中，任意两个顶点之间都可能有关系。

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

稀疏图：称边数很少的图为稀疏图；
稠密图：称边数很多的图为稠密图。

顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。
顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；
顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？
数据结构第六章图在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？

权：是指对边赋予的有意义的数值量。
网：边上带权的图，也称网图。
路径：在无向图G=(V, E)中，从顶点v_p到顶点v_q之间的路径是一个顶点序列(v_p=v_i0,v_i1,v_i2, …, v_im=v_q)，其中，(v_ij1,v_ij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<v_ij-1,v_ij>∈E。
数据结构第六章图回路（环）：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
子图：若图G=（V，E），G’=（V’，E’），如果V’⊆V 且E’ ⊆ E ，则称图G’是G的子图。
连通图：在无向图中，如果从一个顶点v_i到另一个顶点v_j(i≠j)有路径，则称顶点v_i和v_j是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。
连通分量：非连通图的极大连通子图称为连通分量。
数据结构第六章图强连通图：在有向图中，对图中任意一对顶点v_ji和v_j (i≠j)，若从顶点v_i到顶点v_j和从顶点v_j到顶点v_i均有路径，则称该有向图是强连通图。
强连通分量：非强连通图的极大强连通子图。
生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。
数据结构第六章图生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。

图的遍历操作

图的遍历是从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

在图中，如何选取遍历的起始顶点？

解决方案：从编号小的顶点开始。
在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；
在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；
在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。
为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。

从某个起点始可能到达不了所有其它顶点，怎么办？

解决方案：多次调用从某顶点出发遍历图的算法。

因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环?

解决方案：附设访问标志数组visited[n] 。

在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

解决方案：深度优先遍历和广度优先遍历。

1.深度优先遍历（DFS：Depth First Search）
⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
2.广度优先遍历（BFS：Broad First Search ；FIFO: First In First Out）
⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

6.2 图的存储结构及实现

基本思想：
用一个一维数组存储图中顶点的信息
用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。
假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
数据结构第六章图 无向图的邻接矩阵
无向图的邻接矩阵的特点：
主对角线为 0 且一定是对称矩阵。
求顶点i的度：
邻接矩阵的第i行（或第i列）非零元素的个数。
判断顶点 i 和 j 之间是否存在边：
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
求顶点 i 的所有邻接点：
将数组中第 i 行元素扫描一遍，若arc[i][j]为1，则顶点 j 为顶点 i 的邻接点。
有向图的邻接矩阵
有向图的邻接矩阵一定不对称？
不一定，例如有向完全图。
求顶点 i 的出度：
邻接矩阵的第 i 行元素之和。
求顶点 i 的入度：
邻接矩阵的第 i 列元素之和。
判断从顶点 i 到顶点 j 是否存在边：
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
网图的邻接矩阵
网图邻接矩阵可定义为的：
数据结构第六章图 邻接矩阵存储无向图的类

const int MaxSize=10; 
template <class T>
class Mgraph{
   public:
      MGraph(T a[ ], int n, int e );   
       ~MGraph( )
       void DFSTraverse(int v); 
       void BFSTraverse(int v);
        ……
   private:
       T vertex[MaxSize]; 
       int arc[MaxSize][MaxSize]; 
       int vertexNum, arcNum; 
};

构造函数MGraph(T a[ ], int n, int e );

1、确定图的顶点个数和边的个数；
2、输入顶点信息存储在一维数组vertex中；
3、初始化邻接矩阵；
4、依次输入每条边存储在邻接矩阵arc中；
4.1 输入边依附的两个顶点的序号i, j；
4.2 将邻接矩阵的第i行第j列的元素值置为1；
4.3 将邻接矩阵的第j行第i列的元素值置为1；

template <class T>
MGraph::MGraph(T a[ ], int n, int e) {
    vertexNum=n; arcNum=e;
    for (i=0; i<vertexNum; i++) 
        vertex[i]=a[i];
    for (i=0; i<vertexNum; i++)    //初始化邻接矩阵
	   for (j=0; j<vertexNum; j++)
           arc[i][j]=0;             
    for (k=0; k<arcNum; k++) {
        cin>>i>>j;     //边依附的两个顶点的序号
        arc[i][j]=1;  arc[j][i]=1;  //置有边标志    
    }
}

深度优先遍历

⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
递归定义

int visited[MaxSize];
template <class T>
void MGraph::DFSTraverse(int v)  
{
     cout<<vertex[v]; visited [v]=1;
     for (j=0; j<vertexNum; j++)
         if (arc[v][j]==1 && visited[j]==0)
           DFSTraverse( j );
}

广度优先遍历

⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

int visited[MaxSize];
template <class T>
void MGraph::BFSTraverse(int v){     
    front=rear=-1;   //假设采用顺序队列且不会发生溢出
   int Q[MaxSize]; cout<<vertex[v]; visited[v]=1;  Q[++rear]=v; 
    while (front!=rear)    {
         v=Q[++front];   
         for (j=0; j<vertexNum; j++)
            if (arc[v][j]==1 && visited[j]==0 ) {
                  cout<<vertex[j]; visited[j]=1; Q[++rear]=j;
            }
      }
}

邻接表
邻接表存储的基本思想：
对于图的每个顶点v_i，将所有邻接于v_i的顶点链成一个单链表，称为顶点v_i的边表（对于有向图则称为出边表）
所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
邻接表有两种结点结构：顶点表结点和边表结点。
数据结构第六章图 vertex：数据域，存放顶点信息。
firstedge：指针域，指向边表中第一个结点。
adjvex：邻接点域，边的终点在顶点表中的下标。
next：指针域，指向边表中的下一个结点。

定义邻接表的结点 :

struct ArcNode
{   
      int adjvex; 
      ArcNode *next;
};
template <class T>
struct VertexNode 
{
      T vertex;
      ArcNode *firstedge;
};

无向图的邻接表

边表中的结点表示：
每个结点对应图中的一条边，
邻接表的空间复杂度为O(n+e)。
求顶点 i 的度：
顶点i的边表中结点的个数。
判断顶点 i 和顶点 j之间是否存在边：
测试顶点 i 的边表中是否存在终点为 j 的结点。

有向图的邻接表（出边表）

求顶点 i 的出度：
顶点 i 的出边表中结点的个数。
求顶点 i 的入度：
各顶点的出边表中以顶点 i 为终点的结点个数。
求顶点 i 的所有邻接点：
遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。

邻接表存储有向图的类

const int MaxSize=10;    //图的最大顶点数
template <class T>
class ALGraph
{    
   public:
       ALGraph(T a[ ], int n, int e);   
       ~ALGraph;    
       void DFSTraverse(int v);      
       void BFSTraverse(int v);      
   ………
  private:
       VertexNode adjlist[MaxSize];   
       int vertexNum, arcNum;       
};

构造函数
确定图的顶点个数和边的个数；
输入顶点信息，初始化该顶点的边表；
依次输入边的信息并存储在边表中；
3.1 输入边所依附的两个顶点的序号i和j；
3.2 生成邻接点序号为j的边表结点s；
3.3 将结点s插入到第i个边表的头部；

template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{   
    vertexNum=n; arcNum=e; 
    for (i=0; i<vertexNum; i++)   
    {
       adjlist[i].vertex=a[i];
       adjlist[i].firstedge=NULL;      
    } 
    for (k=0; k<arcNum; k++)   
    {
         cin>>i>>j;    
         s=new ArcNode;s->adjvex=j;  	        
         s->next=adjlist[i].firstedge;    
         adjlist[i].firstedge=s;
     }
}

深度优先遍历

template <class T>
void ALGraph::DFSTraverse(int v){        
    cout<<adjlist[v].vertex;  visited[v]=1;
    p=adjlist[v].firstedge;    
    while (p!=NULL)     {
        j=p->adjvex;
        if (visited[j]==0) DFSTraverse(j);
    p=p->next;           
    }
}

广度优先遍历

template <class T>
void ALGraph::BFSTraverse(int v){
   front=rear=-1;   
   cout<<adjlist[v].vertex;    visited[v]=1;   Q[++rear]=v;   
   while (front!=rear)  {
       v=Q[++front];    p=adjlist[v].firstedge;    
       while (p!=NULL)  {
            j= p->adjvex;
            if (visited[j]==0) {
                cout<<adjlist[j].vertex;  visited[j]=1; Q[++rear]=j;
            }
            p=p->next;
       }
    }
}

十字链表：有向图的链式存储结构
邻接多重表：无向图的存储结构
边集数组

利用两个一维数组
一个数组存储顶点信息，另外一个数组存储边及其权
其中，数组分量包含三个域：边所依附的两个顶点，权值
各边在数组中的次序可以任意。

应用举例——最小生成树

生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。
最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。
普里姆（Prim）算法
基本思想：
设G=(V, E)是具有n个顶点的连通网，
T=(U, TE)是G的最小生成树，
T的初始状态为U={u₀}（u₀∈V），TE={ }，
重复执行下述操作：
在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。

Prim算法——伪代码:

初始化两个辅助数组lowcost（=arc[0][i]）和adjvex(=0)(0是始点)；
输出顶点u₀，将顶点u₀加入集合U中；
重复执行下列操作n-1次
3.1 在lowcost中选取最短边(lowcost[k])，取对应的顶点序号k；
3.2 输出顶点k和对应的权值；
3.3 将顶点k加入集合U中（lowcost[k]=0）；
3.4 调整数组lowcost和adjvex；

Void prime(MGraph G){
    for(int i=1;i<G.vertexNu;i++){
        lowcost[i]=G.arc[0][i];  adjvex[i]=0;
    }
    lowcost[0]=0;
    for(i=1;i<G.vertexNum;i+++){
        k=MinEdge(lowcost,G.vertexNum)
        cout<<K<<adjvex[k]<<lowcost[k];
        lowcost[k]=0;
        for(j=1;j<G.vertexNum;j++)
         if((G.arc[k][j]<lowcost[j]){
              lowcost[j]=G.arc[k][j];
              arcvex[j]=k;
           }
    }
}

克鲁斯卡尔（Kruskal）算法
1、设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，
2、然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。
2.1.若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；
2.2.若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，
3、如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

Kruskal算法思想：

初始化：U=V； TE={ }；
循环直到T中的连通分量个数为1
2.1 在E中寻找最短边(u，v);
2.2 如果顶点u、v位于T的两个不同连通分量，则
2.2.1 将边(u，v)并入TE；
2.2.2 将这两个连通分量合为一个；
2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；

Kruskal算法实现中的三个关键问题：

图的存储结构：采用边集数组存储图。
如何判断一条边所依附的两个顶点在同一个连通分两中(并查集)
定义Parent[i]数组。数组分量的值表示顶点i的双亲节点（初值为-1；）
当一条边（u,v）的两个顶点的根结不同时，这两个结点属于不同的连通分量（利用parent 数组查找一棵树的根节点。当一个结点n的parent==-1，树的根节点即为n）
如何将一条边所依附的两个顶点合并到同一个连通分量中
要进行联通分量的合并，其中一个顶点所在的树的根节点为vex1，另一个顶点所在的树的根节点为vex2，则：parent[vex2]=vex1；

int main(){
    int arcNum, int vertexNum;
    EdgeNode *edge;
    int *parent;

    cout<<"please input the number of vertexNum:"; cin>>vertexNum;
    cout<<"please input the number of edges:";	cin>>arcNum;
    edge=new EdgeNode[arcNum];	parent=new int[vertexNum];
    for(int i=0;i<arcNum;i++)	{
 	cout<<"Please input the edges:";
	cin>>edge[i].from>>edge[i].to>>edge[i].weight;
    }
    sort(edges, G); //对边集数组进行堆排序，时间复杂性为O(eloge)
    for (i=0;i<vertexNum;i++)
	parent[i]=-1;  //每个节点分属于不同的集合

    int k=0,begin,end,count=0;
    cout<<"next is the MST :"<<endl;
  for (k=0;k<arcNum;k++)	{
         begin=edge[k].from;	end=edge[k].to;	
         int m,n;
        m=Find(parent,begin);	n=Find(parent,end);
        if(m!=n)	{
            cout<<begin<<","<<end<<","<<edge[k].weight<<endl;
            parent[n]=m;	
            count++;
            if(count==vertexNum-1)	break;
       }
   }
   return 0;
}
int Find(int *parent, int node)
{
	int f;
	f=node;
	while(parent[f]>-1)
		f=parent[f];
	return f;
}

Kruskal算法的时间复杂性分析：
边集数组排序，时间复杂性O(eloge)
在e条边中选边，时间复杂性为O(e)
因此时间复杂性为O(eloge)

6.5 最短路径

在非网图中，最短路径是指两顶点之间经历的边数最少的路径。
在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。

单源点到其他顶点的最短路径
Dijkstra方法，O（n2）
任意一对顶点之间的最短路径
Floyd方法，O（n3）

单源点最短路径问题

问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。
迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。

路径长度递增的理解:
含有n个顶点的图
计算图中顶点v到其他顶点（n-1个）的最短路
总共要找多少条最短路？
n-1条
按路径长度递增指的是这n-1条路的计算原则即，
先找第一条最短路（v，v_i），所有n-1条路中最短的路
再找第二条最短路（v，v_j）
…

基本思想：
1、设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，
2、对v_i∈V-S，假设从源点v到v_i的有向边为最短路径（从v到其余顶点的最短路径的初值）。
3、以后每求得一条最短路径v, …, v_k，就将v_k加入集合S中，并将路径v, …, v_k , v_i与原来的假设相比较，取路径长度较小者为最短路径。
重复上述过程，直到集合V中全部顶点加入到集合S中。

路径长度最短的最短路径（即第一条最短路）的特点：
在这条路径上，必定只含一条边，并且这条边上的权值最小。
下一条路径长度次短的最短路径的特点：
它只可能有两种情况：
或者是直接从源点到该点(只含一条边)；
或者是从源点经过顶点v₁（第一条最短路径所依附的顶点），再到达该顶点(由两条边组成)。
再下一条路径长度次短的最短路径的特点:
它可能有四种情况：或者是直接从源点到该点(只含一条边)；或者从源点经过顶点v₁，再到达该顶点(由两条边组成)；或者是从源点经过顶点v₂，再到达该顶点（两条条边）；或者是从源点经过顶点v₁、v₂，再到达该顶点（多条边）。
其余最短路径的特点：
它或者是直接从源点到该点(只含一条边)；或者是从源点经过已求得最短路径的顶点（集合S中的顶点），再到达该顶点。

数据结构 :
图的存储结构：邻接矩阵存储结构
数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点v_i的最短路径的长度。初态为：若从v到v_i有弧，则dist[i]为弧上权值；否则置dist[i]为∞。
数组path[n]：path[i]是一个字符串，表示当前所找到的从始点_v到终点v_i的最短路径。初态为：若从v到v_i有弧，则path[i]为vv_i；否则置path[i]空串。
数组s[n]：存放源点和已经找到最短路径的终点，其初态为只有一个源点v。

迪杰斯特拉算法的主要步骤如下：
(1) g为用邻接矩阵表示的带权图。
S←{v₀} ， dist［i］= g.arcs［v₀］［v_i］,path[i]=“v₀v_i”或“”；
将v₀到其余顶点的路径长度初始化为权值；
(2) 选择v_k，使得dist［v_k］=min(dist［i］ | v_i∈V-S)
v_k为目前求得的下一条从v₀出发的最短路径的终点。
将v_k加入到S中
(3) 修改从v0出发到集合V-S上任一顶点vi的最短路径的长度。如果
dist[k]+ g.arcs[k][i]<dist[i]；则将dist[i]修改为dist[k]+ g.arcs[k][i]；path[i]=path[k]+”vi”；
(4) 重复(2)、(3) n-1次，即可按最短路径长度的递增顺序，逐个求出v₀到图中其它每个顶点的最短路径。

const int MAX=1000;
void  Dijkstra(MGraph g, int v){
       for ( i =0; i<g.vexnum ; i++){
	 dist[i]=g.arcs[v][i];  
               if ( dist[i]!= MAX) 
                      path [i]=g.vertex[v]+g.vertex[i];
               else
                      path[i]=“”;
       }
       S[0]=g.vertex[v]; 
       num=1;  
While (num<g.vextexNum){
    k=0;
    for(i=0;i<G.vertexNum;i++)
           if((dist[i]<dist[k])   k=i
    cout<<dist[k]<<path[k];
    s[num++]=G.vertex[k];                
    for(i=0;i<G.vertexNum;i++)
             if(dist[k]+g.arc[k][i]<dist[i] {
		 dist[i]=dist[k]+g.arc[k][i];
                       path[i]=path[k]+g.vertex[i];
               }
}
}

每一对顶点之间的最短路径

问题描述：给定带权有向图G＝(V, E)，对任意顶点v_i,v_j∈V（i≠j），求顶点v_i到顶点v_j的最短路径。

解决办法1：每次以一个顶点为源点，调用Dijkstra算法n次。显然，时间复杂度为O(n3)。
解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。

Floyd算法的基本思想：

设图g用邻接矩阵法表示，
求图g中任意一对顶点v_i、 v_j间的最短路径。
（-1）将v_i到v_j 的最短的路径长度初始化为(v_i,v_j)，然后进行如下n次比较和修正：
（0）在v_i、v_j间加入顶点v₀，比较（v_i, v₀, v_j）和(v_i, v_j)的路径的长度，取其中较短的路径作为v_i到v_j的且中间顶点号不大于0的最短路径。
（1）在v_i、v_j间加入顶点v1，得（v_i, …，v₁）和(v₁, …，v_j)，其中：（v_i, …, v₁）是v_i到v₁ 的且中间顶点号不大于0的最短路径，(v₁, …, v_j) 是v₁到v_j 的且中间顶点号不大于0的最短路径，这两条路径在上一步中已求出。
将（v_i, …, v₁, …, v_j）与上一步已求出的且v_i到v_j 中间顶点号不大于0的最短路径比较，取其中较短的路径作为v_i到v_j 的且中间顶点号不大于1的最短路径。
（2）在v_i、v_j间加入顶点v₂，得（v_i, …, v₂）和(v₂, …, v_j)，其中：（v_i, …, v₂）是v_i到v₂ 的且中间顶点号不大于1的最短路径，(v2, …, v_j) 是v₂到v_j 的且中间顶点号不大于1的最短路径，这两条路径在上一步中已求出。
将（v_i, …, v₂, …, v_j）与上一步已求出的且v_i到v_j 中间顶点号不大于1的最短路径比较，取其中较短的路径作为v_i到v_j 的且中间顶点号不大于2的最短路径。
……

数据结构:
图的存储结构：带权的邻接矩阵存储结构
数组dist[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式：
数据结构第六章图数组path[n][n]：放从v_i到v_j的最短路径，初始为path[i][j]=“v_iv_j”。

void Floyd(MGraph G)
{
    for (i=0; i<G.vertexNum; i++)        
       for (j=0; j<G.vertexNum; j++)
       {
          dist[i][j]=G.arc[i][j];
          if (dist[i][j]!=∞) 
               path[i][j]=G.vertex[i]+G.vertex[j];
          else path[i][j]=""; 
       }
     for (k=0; k<G.vertexNum; k++)         
        for (i=0; i<G.vertexNum; i++)       
           for (j=0; j<G.vertexNum; j++)
               if (dist[i][k]+dist[k][j]<dist[i][j]) {
                    dist[i][j]=dist[i][k]+dist[k][j];
                    path[i][j]=path[i][k]+path[k][j];
              }
}

6.6 有向无环图及其应用

AOV

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。

AOV网特点：
1.AOV网中的弧表示活动之间存在的某种制约关系。
2.AOV网中不能出现回路。

拓扑序列：
设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点的拓扑序列中顶点vi必在顶点vj之前。
拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序。

拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。

基本思想：
⑴ 从AOV网中选择一个没有前驱的顶点并且输出；
⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；
⑶ 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。

AOE

AOE网是一个带权的有向无环图。其中用顶点表示事件，弧表示活动，权值表示两个活动持续的时间。AOE网是以边表示活动的网。
AOV网描述了活动之间的优先关系，可以认为是一个定性的研究，但是有时还需要定量地研究工程的进度，如整个工程的最短完成时间、各个子工程影响整个工程的程度、每个子工程的最短完成时间和最长完成时间。在AOE网中，通过研究事件和活动之间的关系，可以确定整个工程的最短完成时间，明确活动之间的相互影响，确保整个工程的顺利进行。
在用AOE网表示一个工程计划时，用顶点表示各个事件，弧表示子工程的活动，权值表示子工程的活动需要的时间。在顶点表示事件发生之后，从该顶点出发的有向弧所表示的活动才能开始。在进入某个顶点的有向弧所表示的活动完成之后，该顶点表示的事件才能发生。
对一个工程来说，只有一个开始状态和一个结束状态。因此在AOE网中，只有一个入度为零的点表示工程的开始，称为源点；只有一个出度为零的点表示工程的结束，称为汇点。