图论算法

第1节 图的相关概念

图的定义：G（V,E）V：定点（数据元素）的有穷非空集合E：边的有穷集合总结就是，图是由点的集合和边的集合组成的。

无向图：每条边都是无方向的有向图：每条边都是有方向的

完全图：任意两个点都有一条边相连

完全无向图：假设有n个顶点，则有n(n-1)/2条边。从n个顶点中挑出两个顶点的方法数。

完全有向图：假设有n个顶点，n(n-1)条边。在n个顶点中挑出两个顶点的方法数，然后再乘以2。

稀疏图：含有方向的边也被称作弧。因此稀疏图是有很少边或者弧的图。

稠密图：稠密图是有较多边或者弧的图。

邻接：有边/弧相连的两个顶点之间的关系。存在（Vi，Vj），则称Vi和Vj互为邻接点。存在<Vi,Vj>,则称Vi邻接到Vj，Vj邻接于Vi。

关联：边/弧与顶点之间的关系存在（Vi，Vj）或者<Vi,Vj>，则称该边/弧关联于Vi和Vj。

顶点的度：与顶点相关联的边的数目。度在有向图中又称为入度和出度。

路径：接续的边构成的顶点序列路径长度：路径上边或弧的数目/权值之和回路：第一个顶点和最后一个顶点相同的路径简单路径：序列中所有顶点都不重复出现的路径简单回路：只有起点和终点重复的路径

连通图：无向图中任意两个顶点之间都存在路径（注意是路径而不是边）

强连通图：有向图中，任意两个顶点之间都存在路径

权：边或弧具有的相关数称为权。

网：边或者弧带权的图。

子图：从一个图中抽离出来的一个小图。

连通分量：无向图抽离出来的子图极大连通子图就叫做连通分量。

强连通分量：有向图抽离出来的极大连通子图（含有的顶点不能再多了）就叫做连通分量。

极小连通子图：抽离出来的连通子图，边不能再少了，再少就不连通了。

生成树：包含无向图所有顶点的极小连通子图（其实就是树）。

生成森林：对非连通图，由各个连通分量的生成树的组成的集合

第2节 图的数组存储

图中结点没有前驱与后继的关系（结点之间是多对多，没法顺序表示），因此图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系。所以图虽然借助数组来表示，但是由于元素之间没有先后关系，因此不叫做顺序存储，而是叫做邻接矩阵。

邻接矩阵的存储结构：1）用一维数组记录顶点信息2）用二维数组记录顶点之间是否存在边注：其实一维数组是可以省略的，但如果这样的话，所有顶点就只能用编号来表示了。

无向图邻接矩阵的分析：1)无向图的邻接矩阵是对称的（对称轴：从左上角到右下角的斜线）2)顶点i的度=第i行（列）中1的个数

有向图邻接矩阵的分析：1）第i行表示顶点Vi的入度2）第i列表示顶点Vi的出度3）顶点的度等于入度与出度之和

由无向网的算法可以轻易的改造出无向图、有向图、有向网的算法。因此，下面以构造无向网为例并编写相应算法。

创建无向网算法：

邻接矩阵的优缺点：优点：简单缺点：增加顶点和删除顶点都比较麻烦

邻接矩阵的存储结构

#deinfe MaxInt 32767 //表示极大值，即无穷
#define MAXSIZE 100

typedef char VerTexType; // 假设顶点的数据类型为字符型
typedef int ArcType; // 假设边的权值类型为int型

typedef struct
{
    VerTexType vexs[MAXSIZE]; //顶点表
    ArcType arcs[MAXSIZE][MAXSIZE]; // 邻接矩阵
    int vexNum,arcNum; // 图的顶点数和边数
}

创建邻接矩阵无向网

// 采用邻接矩阵表示法，创建无向网G
bool CreateUDN (AMGraph &G)
{
    cin>>G. vexNum>>G.arcNum;	//输人总顶点数，总边数
    for (int i=0; i<G.vexNum;i++) //依次输入点的信息
    {
        cin>>G.vexs[i];
    }    
    for (int i=0; i<G.vexNum;++i)	//初始化邻接矩阵，边的权值均置为极大值MaxInt
    {
        for (int j=0;j<G. vexNum;++j)
        {
            G.arcs[i][j]=MaxInt;
        }
    }
    for (int k=0; k<G.arcNum;++k)	//构造邻接矩阵
    {
        cin>>v1>>v2>>w;	//输入一条边依附的顶点及权值
        int i=LocateVex (G, v1) ;
        int j=LocateVex(G, v2); //WiE v1 40 v2 #G PBSYL. HDTLAABS FR
        G.arcs[i][j]=w;	/边<v1，v2>的权置为w
        G.arcs[j][i]=G.arcs[i][j]:	//置<v1 v2>的对称边くv2，v1>的权值为w
    }
    return true;
}

// 图G中查找顶点u，存在贝⌋返回顶点表中的下标;否则返回-1
int LocateVex(AMGraphG, VertexType u) 
{
    for(int i=0;i<G.vexnum;++i)
    {
        if(u==G.vexs[i])	
            return i;
    }   
    return -1;
}

邻接矩阵DFS

// 递归实现深度优先搜索遍历,类似于二叉树的先序遍历
// 需要一个数组用来记录顶点是否被访问过，v表示访问的起点
bool visted[G.vexNum]={false};
void DFS(AMGraph G, int v)
{
    cout<<v; // 输出访问第v个顶点
    visited[v]=true; //访问第v个起点
    for(int i=0;i<G.vexNum,i++)
    {
        if((G.arcs[v][i]!=0)&&(!visited[i]))
        DFS(G,i);
    }
}

邻接矩阵BFS（未完成）

// 广度优先搜索遍历，类似于二叉树的层次遍历

第3节 图的链式存储

一个结点可能与多个结点之间存在边，因此结点中指针域的数目是不固定的，所以用多重链表（含有多个指针域）来表示图很难。图的表示方法：邻接表、邻接多重表、十字链表

邻接表的特点

其实我们需要考虑的是如何表示顶点以及顶点之间的边关系邻接表的存储结构：表示顶点：使用一个一维数组来存储顶点表示边：以顶点元素为头结点的链表就表示该顶点元素与其它边结点之间都存在着边注：顶点的data域表示顶点的名字，边结点的data域表示对应顶点在数组中的位置。但是想一想，边结点的data域用来表示顶点名字也是没有问题的。这样的话，顶点与边结点的存储结构都是相同的，为什么不这样做呢？

无向图邻接表的特点：1）邻接表不唯一2）若无向图中有n个顶点，e条边则其邻接表需要n个头结点和2e个边结点。适合存储稀疏图。3）无向图中顶点Vi的度为第i个单链表中的边结点数4）每条边都被保存了两次

有向图邻接表的特点（存储出度边）：1）顶点Vi的出度为第i个单链表中的结点个数（很容易）2）顶点Vi的入度为整个单链表中邻接点阈值是i-1的结点个数（很难）

逆邻接表：存储入度边找入度容易，找出度难

一个思考：我们使用next指针来指向下一个边结点，那为什么不能用一个int变量来保存边结点在顶点数组中的位置了。这样，仅使用一个int变量既表示了顶点和边结点之间存在边，又能知道边结点的信息。如下，顶点后面跟着边结点的位置信息V1 i j k…… 这是一维数组如果这样继续深入思考下去，我们会发现n个顶点需要n个一维数组，而这n个一维数组的长度不相同。为了方便和统一，那么我们自然会想到使用n个相同的元素个数为n的数组，这样实际上我们使用的就是二维数组了。V1 x1 y1 z1……V2 x2 y2……V3 x2 y3…………这样我们也相当于用一个矩阵来表示图了。但是这样表示的效果不如邻接矩阵好，因为相同的二维数组，邻接矩阵能存储权重信息，保存了更多的信息。

邻接表的存储结构

# define MAXSIZE 100
# typedef char VerTextType;

// 边结点
typedef struct ArcNode
{
    int adjvex; //该边所指向的顶点在顶点表中的位置，我认为该项直接记录结点信息也是可以的——VerTextType data; 
    struct ArcNode *nextArc; // 指向下一条边
    OtherInfo info; // 其它信息
}ArcNode;

// 顶点结点
typedef struct VNode
{
    VerTextType data; // 顶点信息
    ArcNode *firstArc; // 第一条边
}VNode,AdjList[MAXSIZE];


// 邻接表
typedef struct
{
    AdjList vertices;  // 图
    int vexNum,arcNum; // 图的顶点数和边数
}

创建邻接表无向网

// 采用邻接表表示法，创建无向图G
bool CreateUDG(ALGraph &G)
{
    cin>>G. vexnum>>G.arcnum;	//输人总顶点数，总边数
    for (i=0;i<G.vexnum; ++i)	//输人各点，构造表头结点表
    {
        cin>> G.vertices[i].data;	//输入顶点值
        G.vertices[i].firstarc=NULL;	//初始化表头结点的指针域为 NULL
    }
    for (k=0; k<G.arcnum;++k)	//输人各边，构造邻接表
    {
        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=pl;
        //将新結点*p1 括人頂点 v₁ 的辺表火部
        p2=new ArcNode;	//生成另一个对称的新的边结点*p2
        p2->adjvex=i;	//邻接点序号为i
        p2->nextarc=G.vertices[j].firstarc; G.vertices[j]. firstarc=p2;
        //将新結点*p2 括人頂点 v1的辺表火部
    }
    return true;

邻接表DFS（未完成）

邻接表BFS（未完成）

// 广度优先搜索遍历，类似于二叉树的层次遍历

十字链表与邻接多重表（未完成）

对于有向图邻接表，它的缺点是求结点的度困难。而十字链表就是为了解决这个问题。十字链表是将邻接表与逆邻接表相结合起来，试想一下怎样实现这种结构呢？对于无向图邻接表，它的缺点是每条边都要存储两遍。而邻接多重表就是为了解决这个问题。

第4节 最小生成树

生成树的特点：1）生成树是图的极小连通子图。2）一个具有n个顶点的连通图的生成树有n-1条边3）生成树不唯一4）生成树中任意两个顶点间的路径是唯一的

生成树可以通过深度优先搜索遍历（深度优先生成树）和广度优先搜索遍历（广度优先生成树）来生成。

最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边的权值之和最小的那棵生成树称为该网的最小生成树，也称之为最小代价生成树。

最小生成树的典型用途：欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市最多有n(n-1)/2条线路，那么，如何选择n-1条线路，使总费用最少？抽象出来的数学模型：顶点：表示城市，有n个边：表示线路，有n-1条边的权值：表示线路的经济代价

MST性质：

构造最小生成树有Prim算法和Kruskal算法，两种算法比较如下：Prim算法：选择点，时间复杂度n的平方，适合稠密图Kruskal算法：选择边，时间复杂度为NlogN,N为边数，适合稀疏图。

最小生成树算法—顶点

Prim（普里姆）算法思想：1）将一个连通网分成两部分，一部分是生成树，另一部分是连通网减去生成树的部分，后面简称剩余部分。2）初始条件是生成树只有一个结点。3）每次在生成树与连通部分之间挑一条权值最小的边，将对应顶点加入生成树，这样就保证生成树在不断增大，剩余部分在不断减少直至为0。那为什么这个算法不会导致生成树的过程中不会产生环呢？要想生成环，那么必定需要生成树中的一个结点与生成树中的另外一个结点之间存在边相连，而这是不可能的。因为生成树在增长时，生成的边始终是在生成树中挑一个结点，在剩余部分中挑一个结点。

Prim算法实现：1）准备一个visted数组，表示顶点V0到Vn-1是否被访问2）准备一个lowcost数组，表示生成树与剩余部分之间的最小距离，注意这个最小距离是生成树的任意结点到剩余部分的任意结点的最小距离3）传入一个顶点作为生成树的起点，假设为V0，遍历与V0相关联的边，对应权值填入lowcost数组4）所以，现在我们要在lowcost中挑选一个最小值作为生成树的顶点，这通过循环遍历lowcost数组很容易做到，假设挑选出来的顶点为V15）现在我们的生成树有两个顶点V0和V1了。现在我们要挑选出从生成树到剩余部分的最小的边，这个边可能与V0关联，也可能是与V1关联。6）我们只要遍历从顶点V1开始的边（遍历G.[V1]这个数组，边以V1开始，Vx结束），只要对应的边权值小于lowcost对应的边权值，那么就更新lowcost中对应元素。现在lowcost数组表示的权值既可能是从V0出发的，也可能是从V1出发的。因此，其实我们需要一个数组来表示一条边的起点是谁。7）重复以上，挑选最小边，找出最小边对应的顶点，再更新这个顶点所对应的最小边。

#define INF 32376
void prim(MGraph &G,int v0)
{
    int v=v0; //v0是生成树的第1个顶点
    int visted[max]; //表示顶点是否在生成树中，fasle表示顶点在剩余部分，true表示顶点在生成树中
    int lowcost[max]; //lowcost[i]表示生成树中一个顶点到剩余部分中顶点Vi的最小权值
    int parent[max]; //parent[i]表示Vi与parent[i]关联形成边，也可以说结点Vi的父结点的下标是parent[i]
    // 初始化,visted[v]=1,lowcost填充从V为起点到其它顶点的权值
    for(int i=0;i<G.vexNum;i++)
    {
        visted[i]=0;
        lowcost[i]=g.edge[v][i];
        parent[i]=v; //先假设所有结点的父结点下标为v
    }
    visted[v]=1;
    parent[v]=-1; //生成树的起点没有父节点，标为-1
    // 经过以上，初始化成功
    int k;
    for(int i=0;i<G.vexNum-1;i++)
    {
        int min=INF;
        // 在第1轮循环中，我们已经挑选出第2个顶点了，其坐标为k
        for(int j=0;j<G.vexNum;j++)
        {
            if(visted[j]==0&&lowcost[i]<min)
            {
                min=lowcost[j];
                k=j; //其实k这个变量是没有必要的
            }
        }
        if(min==INF)
        {
            cout<<"该图不连通,已有的生成树和剩余部分不连通"<<endl;
            break;
        }
        cout<<parent[k]<<" "<<k<<endl; //输出挑选出来的最小边
        visted[k]=1; // 将Vk加入到生成树中
        v=k; // 下一轮遍历求一个最小的边，我们以Vk顶点为起点
        // 开始更新lowcost数组
        for(int j=0;j<G.vexNum;j++)
        {
            //如果以当前的顶点Vk到顶点j的权值变得更小，那么就更新lowcost数组
            if(visted[i]==0&&G.edge[v][j]<lowcost[j])
            {
                lowcost[j]=G.edge[v][j];
                parent[j]=v; //表示顶点Vj的父节点为Vv或者说这条边的起点为v，终点为j
            }
        }
    }
}

总结：其实visted这个数组并不是必须的，只要我们在更新lowcost时，把已经加入的生成树的顶点置为0即可。不过，lowcost中其实记录了生成树中所有边的权值，看有无必要。思考：如果这个图不是连通图，上面的代码会发生什么？如果上面的图不是连通图，那么肯定就会存在这样的顶点，从生成树中的所有顶点到它的距离都为INF，换言之，lowcost数组中对应的权值为INF，导致lowcost有些元素总是无法更新。这样，一旦生成树再也无法增长时，对于剩余部分的顶点，从生成树到它们的路径总是为INF，导致后面进入循环时什么都不做。所以，其实我们可以通过计算生成树中结点的个数，最后判断生成树中结点个数是否为n-1来判断图是否连通。或者min=INF时也表示图不连通。思考：这个算法与最短距离算法的相似点和不同点是什么？

Prim算法还可参考博客：https://www.jianshu.com/p/683ffde4f3a3

最小生成树算法-边

克鲁斯卡尔（Kruskal）算法在n个结点的无向网中，把所有的边的权值按照重小到大排列，然后按从小到大的顺序取出边用来连接结点，如果在连接的过程中形成了环则丢弃该边，直到最后连接n-1条边即可。这个过程可能会生成许多连通分量，保证生成过程不出现环即可生成最小生成树。

Kruskal算法实现：1）首先肯定要求出图中所有的边，用一个结构体数组（begin，end，weight）保存。遍历邻接矩阵时，由于邻接矩阵关于y=-x对称，因此我们只需要遍历右上部分就可以得到所有的边（似乎是广度优先遍历）。2）按照权值对所有边进行排序。3）开始合并顶点，但是只有不属于同一个连通分量的顶点才进行合并，合并后注意统一连通分量。注意该算法还可以通过并查集来实现，待以后完成。

typedef struct {  // 边集数组
    int begin;
    int end;
    int weight;
}Edge;

// 无向网G以邻接矩阵形式存储,构造G的最小生成树T,输出了的各条边
// 我们假设已经有Edge数组。
void MiniSpanTree_ Kruskal(AMGraph G) {
    Sort(Edge); //将数组 Edge 中的元素按权值从小到大排序 
    for(i=0;i<G.vexnum; i++) //辅助数组,表示各顶点自成一个连通分量 
    {
        Vexset[i]=i;
    } 
    for(i=0;i<G.arcnum;i++) //依次查看数组 Edge 中的边 e 
    {
        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<< Edge[i].Head << Edge[i].Tail;//输出此边 
            for(j=0;j<G.vexnum;++j) //合并vs1和 vs2两个分量,即两个集合统一编号 
            {  if(Vexset[j]==vs2) 
                {    
                    Vexset[j]=vs1; //集合编号为 vs2 的都改为 vs1 
                }
            }
        }
    }
}

第5节 最短路径

最短路径问题是在有向网中求一个结点到另外一个结点的权值之和最小的路径。它与生成树的区别在于最短路径不需要包含网中所有的结点。

第一类问题：两点间最短路径Dijkstra算法。

第二类问题：任意两个顶点之间的最短路径n重Dijkstra算法。弗洛伊德算法。

最短路径

假设有向网中有n+1个顶点，分别为V0到Vn。试求V0到其它任意顶点的最短距离。1）首先求出V0到各顶点之间的直接路径，如果没有直接路径则权值为无穷。这样，我们就能够在这n个权值直接找出一个最小值，假设该权值对应的顶点为Vx。所以现在V0要到达其它顶点，不仅可以选择直接路径，也可以通过Vx来到达了。我们尝试从Vx到达其它顶点，假设路径变得更短，填写这个更小的权值。否则权值保持不变。2）我们现在求通过Vx到达其它各顶点之间的路径，同样是没有直接路径的顶点权值记为无穷。挑出一个最小值，假设该权值对应顶点为Vy。所以现在V0要到达其它顶点，不仅可以选择直接路径，也可以选择先到达顶点Vx，或者先到达顶点Vy。我们尝试从Vy到达其它顶点，假设路径变得更短，那就填写相应的权值，否则权值保持不变。3）在第1轮我们一定可以求出与V0有最短直接路径的顶点，但这个顶点不一定就是我们的目标终点（如果它恰好是我们的目标终点的话，那我们就已经求出了我们想要的最短距离）。在第2轮，我们一定可以求出与V0有最短路径的顶点，但这个顶点也不一定是我们的目标终点。……所以我们一定要经过n轮之后，才能知道V0到其它各顶点之间的最短路径。此时，我们再根据目标终点查询对应的最短路径。

最短路径算法实现：

#define INF 9999999
vector<int> Dijkstra(vector<vector<int>> &graph,int start)
{
    int n=graph.size(); //存储图中的顶点个数
    vector<int> visited(n,0); //标记顶点是否已经访问过
    vector<int> dist(n,0); //存储从start到其它顶点的最短距离

    //初始化
    for(int i=0;i<n;i++)
    {
        dist[i]=graph[start][i]; //初始化dist数组——从start到其它各顶点的距离
    }
    visted[start]=1; // 标记起始顶点

    for(int i=0;i<n;i++)
    {
        int min_dist=INF; //存储从起点到其它未被访问的顶点的最短距离
        int middle=0; //存储最短距离节点的编号

        //遍历n个顶点，寻找当前未被访问的顶点中距离起始顶点最短距离的顶点编号
        for(int j=0;j<n;j++)
        {
            if(visted[j]==0&&min_dist>dist[j])
            {
                min_dist=dist[j];
                middle=j;
            }
        }

        // 以middle为中间节点，如果先到达middle，然后再到到达其它各顶点距离会变得更小的话，更新相应距离
        for(int j=0;j<n;j++)
        {
            //如果从起始节点到j的距离dist[j]大于从起始节点先到middle，然后再从middle到j的距离则更新dist[j]
            if(visted[j]==0&&dist[j]>dist[middle]+graph[middle][j])
            {
                dist[j]=dist[middle]+graph[middle][j];
            }
        }
        visted[middle]=1;
    }
    return dist;
}

思考：该算法与Prim算法的相似点和不同点是什么？这个算法求的是一条路径，所有节点都在一条线上，节点不能有分叉。而Prim算法中，节点是存在分叉的。相同点是，两个算法都维护一个数组用来记录路径权值。不同点在于最小生成树中，lowcost中的元素的值只由路径权值决定在最短距离算法中，dist中的元素值由路径和来决定

弗洛伊德（Floyd）算法

假设有向网中有n个顶点，则设一个n*n矩阵，这里假设n个顶点为V0到Vn-1。则矩阵的行表示起点，矩阵的列表示终点，<Vx,Vy>表示从Vx顶点到Vy顶点的弧，元素array[x][y]表示对应权值。这样的话，一个矩阵就可以表示任意一个顶点到其它所有顶点的权值。由于矩阵从左上到右下的对角线表示的是从Vx到Vx的距离，所以该对角线上的值全部为0。从V0顶点开始，如果到其它任意顶点有直接路径则对应的矩阵元素填写为相应权值，如果不存在直接路径则权值为无穷。我们开始尝试逐步在原来的直接路径中加入中间顶点，第1轮加入的是中间顶点V0，加入中间顶点V0后，假设原来Vx没有直达Vy的路径，则现在Vx可以通过V0间接达到Vy，array[x][y]的值由无穷修改为相应的路径和。现在问题来了，第2轮的时候，加入中间结点的时候，中间结点应该放在哪个位置？如有路径ABD，现在加入中间路径C，那么C是加到B之前还是B之后呢？我认为应该是在B之后，如果是在B之前那么就打乱了原来的AB路径。现在在AB及D之间加入中间结点C，是在探索AB到D之间有没有更短的路径。那么，ACBD这种情况是什么时候发生的呢？是在AC和D之间加入B这个中间结点。所以，综上我们能够推测，加入的中间结点其位置总是在终点结点的前一个位置。如ABD之间加入中间结点C，终点为D，故而加入到D之前，新的路径为ABCD。每一轮加入新的中间结点的时候，都要从头扫描二维矩阵以便填写新的路径和。如果加入中间结点所形成的路径变短，则修改对应元素的值，否则维持不变。当所有的顶点试探完之后，算法完毕。时间复杂度为n的三次方。

算法实现：参考《数据结构与算法》

void shortestPath_Floyd(AMGraph& G)
{
    for(int i=0;i<G.vexNum;i++)
    {
        for(int j=0;j<G.vexNum;j++)
        {
            D[i][j]=G.arcs[i][j];
            if(D[i][j]<maxInt)
            {
                Path[i][j]=i; //如果i和j之间有弧,则将j的前驱置为i
            }
            else
            {
                Path[i][j]=-1; //如果i和j之间无弧,则将j的前驱置为-1
            }
        }
    }

    for(int k=0;k<G.vexNum;++k) //加入第k个顶点作为中间顶点
    {
        for(int i=0;i<G.vexnum;++i) //以第i个顶点作为起始顶点
        {
            for(int j=0;j<G.vexnum;++j) //以第j个顶点作为终点
            {
                if(D[i][k]+D[k][j]<D[i][j]) //从i经k到j的一条路径更短
                {
                    D[i][j]=D[i][k]+D[k][j]; //更新D[i][j]
                    Path[i][j]=Path[k][j]; //更改j的前驱为k

                }
            }
        }
    }
}

总结：D[i][j]表示从顶点i到顶点j的最短路径之和假设k=Path[i][j]，Path[i][j]表示示从顶点i到顶点j时，j的前驱为k，此时通过Path[i][k]查找k的前驱……当查询到Path[i][x]的前驱为i时，那么就找到了路径上的所有顶点。

第6节 拓扑排序

AOV网的定义：假设有这样一个问题，在大学的学习课程中，很多课程有先修课程，在没有完成先修课程前不能学习该课程。这样一门课程可以使用一个结点来表示，一个结点发出一条弧到另外一个结点就表示该结点是另外一个结点的先修课程。现在有许多课程，它们构成了一个有向网，假设这个有向网不存在环，那么称该网为AOV网。那么如何给这些课程进行线性排序使得所有课程的先修课程一定排在该课程的前面呢？这个排序过程就叫做拓扑排序，注意拓扑排序不唯一。还需要考虑的一个问题是，如何判断一个有向网到底是不是AOV网呢(即有向网中不存在环)？

AOV网中的结点存在着前驱和后续，假设每个结点代表一个活动，则只有前驱结点所代表的事件完成之后才能够开始后续的活动。<i,j>表示i是j的前驱。AOV网不允许有回路。

拓扑排序：在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列中，i一定排在j的前面，具有这种性质的线性序歹称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序的过程：1）在有向图中选一个无前驱的顶点且输出它。2）从图中删除该顶点和所有以它为尾的弧。3）重复1）和2），直至不存在元前驱的顶点。4）若此时输出的顶点数小于有向图日中的顶点数、则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列。

算法实现：使用栈对邻接表实现拓扑排序，参考严蔚敏《数据结构与算法》。

bool topoSort(ALGraph,int topo[])
{
    //若G无回路,则生成G的一个拓扑序列 topo[]并返回OK,否则 ERROR
    FindInDegree(G,indegree); //求出各顶点的人度存入数组 indegree中
    InitStack(S); //栈 s初始化为空
    for(i=0;i<G.vexnum;++i)
    {
        if(!indegree[i])
        {
            Push(S,i); //入度为0者进栈
        } 
    }
    int m=0; //对输出顶点计数,初始为 0 
    while(!StackEmpty(S)) //栈S非空
    {
        Pop (S,i);//将栈顶顶点Vi出栈
        topo[m]=i; //将 v保存在拓扑序列数组topo中
        m++ //对输出顶点计数
        p=G.vertices[i].firstarc; //p指向 v;的第一个邻接点
        while(p!=NULL)
        {
            k=p->adjvex; //Vk为Vi的邻接点 
            indegree[k]--; //v的每个邻接点的人度减1
            if(indegree[k]==0) 
            {
                Push(S,k); //若入度减为 0,则入栈
            }
            p=p->nextarc; //p指向顶点 v:下一个邻接结点
        }           
    }
    if(m<G.vexnum)
    {
        return false;
    }
    return true; 
}

思考：上面的算法属于深度优先搜索遍历吗？为什么要使用栈保存入度为0的顶点，使用队列行不行？上面的算法与图的深度优先搜索遍历有什么不同？在上面的算法中，首先将入度为0的顶点压入栈中，然后再将入度为0的顶点弹出栈，同时在出栈过程中，将所有满足条件的顶点又压入栈，所以我认为这很像深度优先搜索遍历，不知道是否可以定义为深度优先搜索遍历呢？其实拓扑排序本质上可以看作是对图的遍历，既然是对图的遍历，那么理论上就有深度优先搜索遍历和广度优先搜索遍历。

下面给出使用队列对图实现拓扑排序的思想：1）统计每个节点的入度（即有多少个节点指向它）。2）将入度为0的节点加入队列中。3）从队列中取出一个节点，将其加入结果列表中，并将其所有邻居节点的入度减1。4）如果邻居节点的入度为0，则将其加入队列中。5）重复步骤3和步骤4，直到队列为空。6）如果结果列表中的节点数小于图中的节点数，则说明图中存在环，无法进行拓扑排序。

第7节 关键路径（未完成）

AOE网的定义：假设有这样一个问题，要举办一场小型的家庭宴会，要完成该宴会有许多事情要做。有些事情可以同时开始做（每个人负责不同的事情，那就可以同时开始做啦），有些事情则必须要等它前面的事情做完了才能开始。这样，我们就可以把所有的事情抽象成一个有向网，一个结点表示活动开始，另外一个结点表示活动结束。弧就能够表示活动（一个结点可以发出两条弧到另外一个结点表示不同的时间），弧的权表示活动持续时间。像这样的网就被称为AOE网。

现在我们要考虑的问题是，某件事情最早什么时候可以开始做？最晚什么时候可以开始做？整个宴会至少要多长时间才能完成？某件事情最早什么时候可以开始做，它受限于它前面的事情必须要先完成。如果我们让某件事情之前的所有事情都尽早完成，那么该事情就可以尽早完成。某件事情最晚什么时候必须开始做，它受限于必须要保证自己后面的时间都能够及时完成。如果我们让某件事情之后的所有事情都尽量晚完成，那么该事情就可以尽量晚完成。

所有事情都尽早完成，那么一定可以求得宴会最短时间。但不一定所有事情都要尽早完成，在我们求出最短时间之后，就能够发现某些事情不一定要尽早开始，只要及时完成即可。某些事情一定要尽早完成，因为这些事情如果不尽早开始一定会影响总的时间，称这样的事情为关键事情。这样，所有影响总时间的关键事情形成的路径称之为关键路径。首先顺推可以得到所有事情的最早开始时间，然后再通过最短时间逆推可得到每件事情的晚开始时间。

描述边的最早开始时间与最晚开始时间描述顶点的最早开始时间与最晚开始时间在求得关键路径之后，那么AOE网中非关键路径的顶点时间就可以浮动。同样边的开始时间和结束时间也可以浮动。

描述顶点的最早开始时间和最晚开始时间：先顺求最早开始时间，再逆求最晚开始时间。

描述活动的最早开始时间和最晚开始时间：一个活动关联两个顶点，其最早开始时间等于弧尾（不带箭头的那端）所关联的顶点的最早开始时间。最晚开始时间等于弧头（带箭头的那端）所关联的顶点最晚开始时间-活动持续时间最晚活动的最晚开始时间-最早开始时间，结果为0则表示该活动是关键活动，由关键活动组成的路径称之为关键路径。

关键路径的定义：把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。事件表示在它之前的活动已经完成， 在它之后的活动可以开始。工程的开始点叫做源点（入度为0）。工程的结束点叫做汇点（出度为0）。

对于AOE网，我们关心两个问题：1）完成整项工程至少需要多少时间？2）哪些活动是影响工程讲度的关键？

关键路径：路径长度最长的路径。路径长度：路径上各活动持续时间之和。