数据结构第七章图

柔情只为你懂 2022-06-08 11:23 636阅读 0赞

**数据结构笔记链接：**

[第一章 绪论][Link 1]

[第二章 线性表][Link 2]

[第三章 栈和队列][Link 3]

[第四章 串][Link 4]

[第五章 数组和广义表][Link 5]

[第六章 树和二叉树][Link 6]

[第七章 图][Link 7]

[第八章 排序][Link 8]

[第九章 查找][Link 9]

--------------------

*   *   *  7.1 图的基本概念
            
             *  7.1.1 概念
             *  7.1.2 有向图和无向图
             *  7.1.3 完全图、稠密图和稀疏图
             *  7.1.4 度、入度、出度和握手定理
             *  7.1.5 子图
             *  7.1.6 权和网
             *  7.1.7 路径、路径长度
             *  7.1.8 回路和简单路径
             *  7.1.9 连通图
             *  7.1.10 生成树、生成森林
         *  7.2 图的存储
            
             *  7.2.1 邻接矩阵
                
                 *  7.2.1.1 图的邻接矩阵表示
                 *  7.2.1.2 网的邻接矩阵表示
                 *  7.2.1.3 语言描述
             *  7.2.2 邻接表
                
                 *  7.2.2.1 定义
                 *  7.2.2.2 优缺点
                 *  7.2.2.3 语言描述
             *  7.2.3 比较
         *  7.3 图的遍历
            
             *  7.3.1 深度优先搜索遍历
                
                 *  7.3.1.1 步骤
                 *  7.3.1.2 邻接矩阵实现
                 *  7.3.1.3 邻接表实现
             *  7.3.2 广度优先搜索遍历
                
                 *  7.3.2.3 步骤
                 *  7.3.2.3 邻接矩阵实现
                 *  7.3.2.3 邻接表实现
         *  7.4 生成树与最小生成树
            
             *  7.4.1 生成树
             *  7.4.2 最小生成树
                
                 *  7.4.2.1 构造准则
                 *  7.4.2.2 Prim算法
                 *  7.4.2.3 Kruskar算法
         *  7.5 最短路径
            
             *  7.5.1 Dijkstra算法
                
                 *  7.5.1.1 算法思想
                 *  7.5.1.2 实现步骤
                 *  7.5.1.3 例题
                 *  7.5.1.4 算法实现
             *  7.5.2 Floyd算法
                
                 *  7.5.2.1 算法思想
                 *  7.5.2.2 实现步骤
                 *  7.5.2.3 算法实现
         *  7.6 拓扑结构与AOV网
            
             *  7.6.1 AOV网
             *  7.6.2 拓扑排序
             *  7.6.3 说明
             *  7.6.4 例题
         *  7.7 关键路径与AOE网
            
             *  7.7.1 AOE网
             *  7.7.2 关键路径
         *  7.8 例题
            
             *  7.8.1 例1
             *  7.8.2 例2
             *  7.8.3 例3
             *  7.8.4 例4
             *  7.8.5 例5
             *  7.8.6 例6
             *  7.8.7 例7
             *  7.8.8 例8
             *  7.8.9 例9

--------------------

### 7.1 图的基本概念 ###

#### 7.1.1 概念 ####

**图G**由一个`非空项点集V`和一个`顶点间的关系集合E（边的集合）`组成的一种数据结构，可以用二元组定义为：`G=(V, E)`。

#### 7.1.2 有向图和无向图 ####

在图中，若用箭头标明了边是有方向性的，则称这样的图为**有向图**，否则称为**无向图**。

在无向图中，一条边(x, y)与(y, x)表示的**结果相同**，用**圆括号**表示。

在有向图中，一条边< x,y >与< y,x >表示的**结果不相同**，用**尖括号**表示。

< x,y >表示从顶点x指向顶点y的边，x为始点，y为终点。有向边也称为`弧`, x为`弧尾`, y为`弧头`。则< x,y >表示为一条弧, 而< y,x >表示y为弧尾, x为弧头的另一条弧 。

![有向图和无向图][20171107164935361]

#### 7.1.3 完全图、稠密图和稀疏图 ####

具有`n`个顶点，`n(n-1)/2`条边的图，称为`完全无向图`；具有`n`个顶点，`n(n-1)`条弧的有向图，称为`完全有向图`。

完全无向图和完全有向图都称为`完全图`。

当一个图接近完全图时，则称它为`稠密图`。相反地，当一个图中含有较少的边或弧时(e < nlogn)，则称它为`稀疏图`。

#### 7.1.4 度、入度、出度和握手定理 ####

在无向图中，关联于该顶点v的边的数目，称为该顶点的`度`，记为：`D(v)`。

在有向图中，把以顶点v为终点的边的数目，称为v的`入度`，记为：`ID(v)`；

把以顶点v为始点的边的数目，称为v的`出度`，记为：`OD(v)`；

顶点v的入度和出度之和称为该顶点的`度`，`D(v)=ID(v)+OD(v)`。

`握手定理`：度之和为边的两倍(有向图中入度必须等于出度等于边的个数)。

例1：在G1=(V1,E1)中：

V1={v1,v2,v3,v4 ,v5 }
    E1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
    D(v1)=2, D(v2)=3, D(v3)=3, D(v4)=2, D(v5)=2。

![7.1.4.1][]

例2：在G2=(E2,V2)中：

V2={
       a,b,c,d}
    E2={<a,b>,<a,c>,<c,d>,<d,a>}
    D(a)=ID(a)+OD(a)=1+2=3, 
    D(b)=ID(b)+OD(b)=1+0=1, 
    D(c) =ID(c)+OD(c)=1+1=2, 
    D(d)=ID(d)+OD(d)=1+1=2。

![7.1.4.2][]

#### 7.1.5 子图 ####

若有两个图G1和G2，G1=(V1, E1)，G2=(V2, E2)，满足如下条件：

![tmp][]

即V2为V1的子集，E2为E1的子集，称图G2为图G1的`子图`。下图给出了7.1.2中图的子图：

![图的子图][20171107165302919]

#### 7.1.6 权和网 ####

图中每一条边都可以附有一个对应的数值，这种与边相关的数据信息称为`权`。边上带有权的图称为`带权图`，也称作`网`。

#### 7.1.7 路径、路径长度 ####

路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。

例如7.1.4中`v1→v2→v5`与`v1→v4→v3→v5`是从顶点v1到顶点v5的两条路径，路径长度分别为2和3。

#### 7.1.8 回路和简单路径 ####

若一条路径上的开始点与结束点为**同一个顶点**，则此路径被称为`回路`或`环`。开始点与结束点相同的简单路径被称为`简单回路`或`简单环`。

例如7.1.4中`a→c→d→a`为简单回路或简单环。

#### 7.1.9 连通图 ####

在无向图 G=（V，\{E\}）中，若从 vi到 vj有路径相通，则称顶点 vi与 vj是连通的。如果对于图中的任意两个顶点 vi、vj∈V，vi，vj都是连通的，则称该无向图 G 为`连通图`。**无向图中的极大连通子图**称为该无向图的`连通分量`。

![无向图连通分量][20171107170257188]

在有向图 G=（V，\{A\}）中，若对于每对顶点 vi、vj∈V 且 vi≠vj，从 vi 到 vj和 vj到 vi都有路径，则称该有向图为`强连通图`。**有向图的极大强连通子图**称做有向图的`强连通分量`。

![强连通图][20170924014155942]

显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。

#### 7.1.10 生成树、生成森林 ####

连通图G的`生成树`，是G的包含其全部n个顶占的一个**极小连通子图,**它必定包含且仅包含G的`n-1`条边。

![生成树][20170924014409918]

在非连通图G中，由每个连通分量都可以得到一个极小连通子图（一棵生成树）。这些连通分量的生成树就组成了一个非连通图的`生成森林`。

![生成森林][20170924014423883]

### 7.2 图的存储 ###

#### 7.2.1 邻接矩阵 ####

##### 7.2.1.1 图的邻接矩阵表示 #####

在邻接矩阵表示中，**除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。**若(i,j)∈E(G) 或 < i,j >∈E(G)，则矩阵中`第i行第j列`元素值为1，否则为0 。

![图的邻接矩阵表示][20170924015009710]

![图的邻接矩阵][20171107172022971]

##### 7.2.1.2 网的邻接矩阵表示 #####

类似地可以定义网的邻接矩阵：

![网的邻接矩阵表示][20170924015107845]

![网的邻接矩阵][20171107172119683]

##### 7.2.1.3 语言描述 #####

#define n 6 /* 图的顶点数*/
    #define e 8 /* 图的边数*/
    typedef char vextype;   /* 顶点的数据类型*/
    typedef float adjtype;  /* 权值类型*/
    
    typedef struct{ 
    vextype vexs[n];    /* 存储顶点信息*/
        adjtype arcs[n][n];     /* 邻接矩阵~存储边的信息*/
    } graph;    /* 图的定义*/

算法时间复杂度：`O(n×n)`

#### 7.2.2 邻接表 ####

##### 7.2.2.1 定义 #####

图的邻接矩阵表示法虽然有其自身的优点，但对于稀疏图来讲，用邻接矩阵的表示方法会造成存储空间的很大浪费，为此引入邻接表表示法。

`邻接表表示法`实际上是图的一种链式存储结构，它包括两部分：

*  单链表，用来存放边的信息
 *  数组，主要用来存放顶点本身的数据信息

![邻接表][20170924015616266]

下图为某网的邻接表和网络图的示例：

![邻接表例子][20170924015647300]

##### 7.2.2.2 优缺点 #####

优点：空间效率高；容易寻找顶点的邻接点。

缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。

##### 7.2.2.3 语言描述 #####

typedef char vextype;       /*顶点的数据类型*/
        typedef struct  node{  
        int adjvex;             /*邻接点域 */
        int weight;             /*权值域*/
        struct  node  *next ;   /*链域*/
    }edgenode;                  /*边表结点*/
    
    typedef struct {
        vertype  vertex;        /*顶点信息*/
        edgenode  *link;        /*边表头指针*/
    }vexnode;                   /*顶点表结点*/
    
    vexnode ga[n];              /*存储顶点信息一维表 */

#### 7.2.3 比较 ####

（1）联系  
邻接表中每个链表对应于邻接矩阵中的**一行**，链表中**结点个数等于一行中非零元素的个数**。

（2）区别  
对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表**不唯一**(**链接次序与顶点编号无关**)。

邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度为O(n+e)。

（3）用途  
邻接矩阵多用于**稠密图**的存储，而邻接表多用于**稀疏图**的存储。

### 7.3 图的遍历 ###

为避免同一顶点被多次访问，必须为每个被访问的顶点作一标志。为此引入一**辅助数组**，记录每个顶点是否被访问过。

设置一个全局型标志数组`visited[0..n-1 ]`来标志某个顶点是否被访问过，未访问的值为 0，访问过的值为 1。

#### 7.3.1 深度优先搜索遍历 ####

##### 7.3.1.1 步骤 #####

首先访问顶点vi，并将其访问标志置为访问过，即`visited[i]=1`。

然后搜索与顶点vi有边相连的下一个顶点vj ，若vj未被访问过，则访问它，并将vj的访问标志置为访问过，`visited[j]=1`，然后从vj开始重复此过程；若vj已访问，再看与vi有边相连的其它顶点。

若与vi有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。

##### 7.3.1.2 邻接矩阵实现 #####

算法描述如下所示

void dfs (int i) {          // 从顶点i 出发遍历
        int j;
        visit(i);               //输出访问顶点
        visited[i]=1;           //全局数组访问标记置1表示已经访问
        for(j=1; j<=n; j++)
            if ((A[i][j]==1) && (!visited[j]))
                dfs(j); 
    }

![邻接矩阵实现DFS][DFS]

上图描述从顶点1出发的深度优先搜索遍历过程，其中实线表示下一层递归调用，虚线表示递归调用的返回。得到从顶点1的遍历结果为: 1, 2, 4, 8, 5, 6, 3, 7。

##### 7.3.1.3 邻接表实现 #####

算法描述如下所示：

void  dfsl(int i) {                 //从V i+1出发深度优先搜索图gl，gl用邻接表表示
        edgenode *p;
        visit(gl[i].vertex) ;           // 输出访问顶点
        visted[i]=1;                    // 全局数组访问标记置为1表示已访问
        p=gl[i].link;                   // 取V i+1的边表头指针
        while (p!=NULL) {               // 依次搜索V i+1的邻接点
            if  (!visited[p->adjvex]) 
                fsl (p->adjvex);        //从V i+1的未曾访问的邻接点出发进行DFS
            p=p->next;                  //找V i+1的下一个邻接点
        }
    }

![邻接表实现DFS][DFS 1]

上图描述从顶点7出发的深度优先搜索遍历，其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。从顶点7出发的深度优先搜索遍历序列： 7, 3, 1, 2, 4, 8, 5, 6。

#### 7.3.2 广度优先搜索遍历 ####

和深度优先搜索类似，在遍历的过程中也需要一个**访问标志数组**。

并且，为了顺次访问路径长度为2、3、…的顶点，需附设**队列**以存储已被访问的路径长度为1，2，…的顶点。

##### 7.3.2.3 步骤 #####

首先访问顶点i，并将其访问标志置为已被访问，即`visited[i]=1`；

接着依次访问与**顶点i有边相连**的所有顶点W1，W2，…，Wt；

然后再按顺序访问与W1，W2，…，Wt**有边相连且未曾访问过的顶点**；依此类推，直到图中所有顶点都被访问完为止。

##### 7.3.2.3 邻接矩阵实现 #####

算法描述如下所示：

void  bfs( int  k) {  
        //从顶点V k+1出发广度优先搜索图g，图g用邻接矩阵表示，visited为访问标志向量
        int  i, j ;
        SETNULL(Q);                 //设置空队列Q
        printf(“%c”, g.vexs[k]);        //访问出发点V k+1
        visited[k]=1 ;              //标记置1表示已经访问
        ENQUEUE(Q, K) ;             //已访问过的顶点入队列
        while (!EMPTY(Q)){
            i=DEQUEUE(Q) ;          //队头元素出队列
            for (j=0; j<n; j++)
                if ( (g.arcs[i][j]==1) && (!visited[j]) ) {
                    printf(“%c”, g.vexs[j]);  vsited[j]=1 ;
                    ENQUEUE(Q, j); 
                } 
        }
    }

![邻接矩阵实现BFS][BFS]

若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8

若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5

##### 7.3.2.3 邻接表实现 #####

算法描述如下所示：

void  bfsl (int k) {
        //从V k+1出发深度优先搜索图gl，gl用邻接表表示
        int i;
        edgenode *p;
        SETNULL(Q);                             //设置空队列Q
        printf(“%c”, gl[k].vertex);
        visited[k]=1 ;
        ENQUEUE(Q, k) ;
        while (!EMPTY(Q)){
            i=DEQUEUE(Q) ;                      //队头元素出队列
            p=gl[i].link;                       //取V k+1的边表头指针
            while (p!=NULL){                    //依次搜索V k+1的邻接点
                if (!visited[p->adjvex]) {
                    printf(“%c”, gl[p->adjvex].vertex);
                    visited[p->adjvex]=1;
                    ENQUEUE(Q, p->adjvex) ;     //访问过的顶点入队
                }
                p=p->next; //找V i+1的下一个邻接点
            }
        }
    }

![邻接表实现BFS][BFS 1]

若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8

若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2

### 7.4 生成树与最小生成树 ###

#### 7.4.1 生成树 ####

连通图G的一个**极小连通子图**，它含有图中`n`个顶点，但只有`n-1`条边。

由深度优先搜索遍历得到的生成树，称为`深度优先生成树`(DFS生成树)。

由广度优先搜索遍历得到的生成树，称为`广度优先生成树`(BFS生成树)。

例1：画出下图的最小生成树（从V0出发）

![生成树问题1][1]

![生成树答案1][1 1]

例2：画出下图的最小生成树

![生成树问题2][2]

![生成树答案2][2 1]

#### 7.4.2 最小生成树 ####

生成树中每条边上**权值之和**达到**最小**，称为`最小生成树`。

##### 7.4.2.1 构造准则 #####

*  必须只使用该网络中的边来构造最小生成树；
 *  必须使用且仅使用**n-1条边**来联结网络中的**n个顶点**；
 *  不能使用产生回路的边。

##### 7.4.2.2 Prim算法 #####

*  假设`G=<V,E>`是连通图，TE是G上最小生成树中边的集合。
 *  算法从U=\{u0\}(u0∈V)，TE=\{ \}开始，任取一个顶点u0作为开始点。
 *  重复执行下述操作：在所有u∈U, v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。

**注意：**选择最小边时，可能有多条同样权值的边可选，此时任选其一。

例：假设开始顶点就选为顶点1，故首先有U=\{1\}，W=V-U=\{2, 3, 4, 5, 6\}：

![Prim][]

//时间复杂度O(n×n)
    struct {
        VertexData adjvex;
        int lowcost;
    } closedge[MAX_VERTEX_NUM]; /* 求最小生成树时的辅助数组*/
    
    /*从顶点 u 出发，按普里姆算法构造连通网 gn 的最小生成树，并输出生成树的每条边*/
    MiniSpanTree_Prim(AdjMatrix gn, VertexData u) {
        k = LocateVertex(gn, u);
        closedge[k].lowcost = 0; /*初始化，U={u} */
    
        /*对 V-U 中的顶点 i，初始化 closedge[i]*/
        for (i = 0; i < gn.vexnum; i++){
            if ( i!= k) { 
                closedge[i].adjvex = u;
                closedge[i].lowcost = gn.arcs[k][i].adj;
            }
        }
    
        /*找 n-1 条边(n= gn.vexnum) */
        for (e = 1; e <= gn.vexnum-1; e++) {
            k0 = Minium(closedge); /* closedge[k0]中存有当前最小边（u0,v0）的信息*/
            u0 = closedge[k0].adjvex; /* u0∈U*/
            v0 = gn.vertex[k0] /* v0∈V-U*/
            printf(u0, v0); /*输出生成树的当前最小边（u0,v0）*/
            closedge[k0].lowcost = 0; /*将顶点 v0 纳入 U 集合*/
    
            /*在顶点 v0 并入 U 之后，更新 closedge[i]*/
            for (i = 0 ; i < vexnum; i++) {
                if ( gn.arcs[k0][i].adj < closedge[i].lowcost) { 
                    closedge[i].lowcost = gn.arcs[k0][i].adj;
                    closedge[i].adjvex = v0;
                }
            }
        }
     }

##### 7.4.2.3 Kruskar算法 #####

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

例：用Kruskar算法求最小生成树。

![Kruskar][]

// 邻接矩阵
    typedef struct _graph {
        char vexs[MAX];       // 顶点集合
        int vexnum;           // 顶点数
        int edgnum;           // 边数
        int matrix[MAX][MAX]; // 邻接矩阵
    }Graph, *PGraph;
    
    // 边的结构体
    typedef struct _EdgeData {
        char start; // 边的起点
        char end;   // 边的终点
        int weight; // 边的权重
    }EData;
    
    void kruskal(Graph G) {
        int i,m,n,p1,p2;
        int length;
        int index = 0;          // rets数组的索引
        int vends[MAX]={
       0};     // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
        EData rets[MAX];        // 结果数组，保存kruskal最小生成树的边
        EData *edges;           // 图对应的所有边
    
        // 获取"图中所有的边"
        edges = get_edges(G);
        // 将边按照"权"的大小进行排序(从小到大)
        sorted_edges(edges, G.edgnum);
    
        for (i=0; i<G.edgnum; i++) {
            p1 = get_position(G, edges[i].start);   // 获取第i条边的"起点"的序号
            p2 = get_position(G, edges[i].end);     // 获取第i条边的"终点"的序号
    
            m = get_end(vends, p1);                 // 获取p1在"已有的最小生成树"中的终点
            n = get_end(vends, p2);                 // 获取p2在"已有的最小生成树"中的终点
    
            // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
            if (m != n) {
                vends[m] = n;                       // 设置m在"已有的最小生成树"中的终点为n
                rets[index++] = edges[i];           // 保存结果
            }
        }
    
        free(edges);
    
        // 统计并打印"kruskal最小生成树"的信息
        length = 0;
    
        for (i = 0; i < index; i++)
            length += rets[i].weight;
        printf("Kruskal=%d: ", length);
    
        for (i = 0; i < index; i++)
            printf("(%c,%c) ", rets[i].start, rets[i].end);
        printf("\n");
    }

### 7.5 最短路径 ###

如果将交通网络画成带权图，结点代表地点，边代表城镇间的路，边权表示路的长度，则经常会遇到如下问题：两给定地点间是否有通路？如果有多条通路，哪条路最短？

还可以根据实际情况给各个边赋以不同含义的值。例如，对司机来说，里程和速度是他们最感兴趣的信息；而对于旅客来说，可能更关心交通费用。有时，还需要考虑交通图的有向性，如航行时，顺水和逆水的情况。

带权图的`最短路径`是指**两点间的路径中边权和最小的路径**。

#### 7.5.1 Dijkstra算法 ####

给定一个出发点(单源点)和一个有向网`G=(V, E)`, 求出源点到其它各顶点之间的最短路径。

##### 7.5.1.1 算法思想 #####

（1）把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是`V-S`(令W=V-S)，其中V为网中所有顶点集合。

（2）按**最短路径长度递增**的顺序逐个把W中的顶点加到S中，直到S中包含全部顶点，而W为空。

（3）在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到W中任何顶点的最短路径长度。

（4）此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，W中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

##### 7.5.1.2 实现步骤 #####

（1）初始时，**S只包含源点**，S=\{v\}，v的距离为0。**U包含除v外的其他顶点**，U中顶点的距离为顶点的权或∞ 。

（2）从U中选取一个**距离最小**的顶点k，把k加入到S中。

（3）以k 作为新考虑的中间点，**修改** U中各顶点的距离。

（4）重复步骤（1）、（2）直到所有顶点都包含在S中。

##### 7.5.1.3 例题 #####

求v0到其它各点的最短路径：

![7.5.1.3题目][7.5.1.3]

![7.5.1.3答案][7.5.1.3 1]

所以最短路径为（V0,V2,V4,V3,V5）。

##### 7.5.1.4 算法实现 #####

#define INFINITY 32768 /*表示极大值，即∞ */
    
    typedef unsigned int WeightType;
    typedef WeightType AdjType;
    typedef SeqList VertexSet;
    
    /* path[i]中存放顶点 i 的当前最短路径。dist[i]中存放顶点 i 的当前最短路径长度*/
    ShortestPath_DJS(AdjMatrix g, int v0,WeightType dist[MAX_VERTEX_NUM], VertexSet path[MAX_VERTEX_NUM] ) { 
        VertexSet s; /* s为已找到最短路径的终点集合 */
    
        /* 初始化 dist[i]和 path [i] */
        for ( i =0;i<g.vexnum ;i++) {
            InitList(&path[i]);
            dist[i]=g.arcs[v0][i].adj;
            if ( dist[i] < INFINITY) {
                AddTail(&path[i], g.vertex[v0]); /* AddTail 是表尾添加操作*/
                AddTail(&path[i], g.vertex[i]);
            }
        }
    
        InitList(&s);
        AddTail(&s, g.vertex[v0]); /* 将 v0 看成第一个已找到最短路径的终点*/
    
        /*求 v0 到其余 n-1 个顶点的最短路径(n= g.vexnum )*/
        for ( t = 1; t<=g.vexnum-1; t++) {
            min= INFINITY;
            for ( i =0; i<g.vexnum;i++) {
                if (! Member(g.vertex[i], s) && dist[i]<min ) {
                    k =i; min=dist[i];
                }
    
            }
    
            AddTail(&s, g.vertex[k]);
    
            /*修正 dist[i], i∈V-S */
            for ( i =0; i<g.vexnum;i++) {
                if (!Member(g.vertex [i], s) && g.arcs[k][i].adj!= INFINITY && (dist[k]+ g.arcs [k][i].adj<dist[i])) {
                    dist[i]=dist[k]+ g.arcs [k][i].adj;
                    path[i]=path[k];
                    AddTail(&path[i], g.vertex [i]); /* path[i]=path[k]∪{Vi} */
                }
            }
        }
    }

#### 7.5.2 Floyd算法 ####

Dijkstra算法只能求出源点到其它顶点的最短路径，欲求任意一对顶点间的最短路径，可以  
用每一顶点作为源点，重复调用狄杰斯特拉算法 n 次，其时间复杂度为 O(n3)。

下面介绍一种形式更简洁的方法，即`Floyd算法`，其时间复杂度也是 O(n3)。

##### 7.5.2.1 算法思想 #####

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释。

从任意节点i到任意节点j的最短路径不外乎两种可能，一是直接从i到j，二是从i经过若干个节点k到j。

所以，我们假设`Dis(i,j)`为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查`Dis(i,k) + Dis(k,j) < Dis(i,j)`是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设`Dis(i,j) = Dis(i,k) + Dis(k,j)`，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

##### 7.5.2.2 实现步骤 #####

（1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

（2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

##### 7.5.2.3 算法实现 #####

typedef SeqList VertexSet;
    
    /* g 为带权有向图的邻接矩阵表示法， path [i][j]为 vi到 vj的当前最短路径，dist[i][j]为 vi到vj的当前最短路径长度*/
    ShortestPath_Floyd(AdjMatrix g, WeightType dist [MAX_VERTEX_NUM] [MAX_VERTEX_NUM], VertexSet path[MAX_VERTEX_NUM] [MAX_VERTEX_NUM] ) {
         /* 初始化 dist[i][j]和 path[i][j] */
        for (i=0; i<g.vexnumn; i++)
            for (j =0;j<g.vexnum; j++) {
                InitList(&path[i][j]);
                dist[i][j]=g.arcs[i][j].adj;
    
                if (dist[i][j]<INFINITY) {
                    AddTail(&path[i][j], g.vertex[i]);
                    AddTail(&path[i][j], g.vertex[j]);
                }
            }
    
        for (k =0;k<g.vexnum;k++)
            for (i =0;i<g.vexnum;i++)
                for (j=0;j<g.vexnum;j++)
                    if (dist[i][k]+dist[k][j]<dist[i][j]) {
                        dist[i][j]=dist[i][k]+dist[k][j];
                        paht[i][j]=JoinList(paht[i][k], paht[k][j]);
                    } /* JoinList 是合并线性表操作 */
    }

### 7.6 拓扑结构与AOV网 ###

#### 7.6.1 AOV网 ####

在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，则称该有向图叫做**顶点活动网(Activity On Vertex network)**，简称为`AOV网`。

在AOV网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的`前驱`，或者称顶点j是顶点i的`后继`。

若< i,j >∈G(E)，则称顶点i是顶点j的`直接前驱`，顶点j是顶点i的`直接后继`。

#### 7.6.2 拓扑排序 ####

给出有向图G=(V,E)，对于V中的顶点的线性序列(vi1,vi2,…,vin)，如果满足如下条件：若在G中从顶点 vi到vj有一条路经，则在序列中顶点vi必在顶点 vj之前；则称该序列为 G的一个`拓扑序列`(Topological order)。

构造有向图的一个拓扑序列的过程称为`拓扑排序`(Topological sort)。

拓扑排序实现步骤如下：

（1）从AOV网中选一个入度为0的顶点v且输出之；

（2）从AOV网中删除此顶点v及所有出边；

（3）重复（1）、（2）两步，直到AOV网中**不存在无前驱的顶点**为止。

#### 7.6.3 说明 ####

（1）AOV网不一定都有拓扑序列。

（2）AOV网中不能出现有向回路(或称有向环)。

判断AOV网是否有有向环的方法是对该AOV网进行`拓扑排序`，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环；否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。

#### 7.6.4 例题 ####

求下图所示的拓扑序列

![7.6.4][]

拓扑序列：

> C1–C2–C3–C4–C5–C7–C9–C10–C11–C6–C12–C8
> 
> C9–C10–C11–C6–C1–C12–C4–C2–C3–C5–C7–C8

**注：一个AOV网的拓扑序列不是唯一的。**

### 7.7 关键路径与AOE网 ###

#### 7.7.1 AOE网 ####

在带权的有向图中，以顶点表示`事件`，弧表示`活动`，权表示`活动的开销`，则称此带权的有向图为用边表示活动的网络，简称`AOE网`。

在一个表示工程的AOE网中：**不存在回路**。网中仅存在一个**入度为0的顶点**，称作`源点`，它表示了整个工程的开始；网中仅存在一个**出度为0的顶点**，称为`汇点`，它表示整个工程的结束。

从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做`关键路径`。关键路径上的活动叫做`关键活动`。

#### 7.7.2 关键路径 ####

把**从源点到汇点的最长路径**称为`关键路径`，关键路径上的活动称为`关键活动`。

在一个AOE网中，可以有不止一条的关键路径。

例：求出下图的关键路径：

![关键路径][20170924024026315]

上方右图为计算过程，关键路径为：

> V1→ V2 →V5 →V7 →V9
> 
> V1→ V2 →V5→ V8 →V9

注：从源点到汇点时，选择较大的权值。从汇点到源点时，选择较小的权值。来回均相同的路径就是关键路径。

### 7.8 例题 ###

#### 7.8.1 例1 ####

有8个结点的无向图最多有【 】条边，最少有【 】条边。

> 28 ; 7

（注：无向图最多需要n(n-1)/2条边，最少需要n-1条边。有向图最多n(n-1)条边。）

#### 7.8.2 例2 ####

深度优先遍历类似于二叉树的【 】，广度优先遍历类似于二叉树的【 】。

> 先序遍历 ; 层次遍历

#### 7.8.3 例3 ####

任何一个无向连通图的最小生成树【 】。

> 不止一棵

#### 7.8.4 例4 ####

求稀疏图的最小生成树，用【 】算法来求解较好。求稠密图的最小生成树，用【 】算法来求解较好。

> Kruskar ; Prim

#### 7.8.5 例5 ####

在有向图的邻接矩阵上，第i行中的非零且非无穷元素个数是第i个结点的【 】。

> 出度

#### 7.8.6 例6 ####

已知下图所示的有向图，请给出该图的:  
（1）每个顶点的入/出度；  
（2）邻接矩阵；  
（3）邻接表；  
（4）逆邻接表。

![7.8.6题目][7.8.6]

![7.8.6答案][7.8.6 1]

#### 7.8.7 例7 ####

已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

![7.8.7][]

#### 7.8.8 例8 ####

试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。

![7.8.8题目][7.8.8]

> 解：最短路径为：（a,c,f,e,d,g,b）。

![7.8.8答案][7.8.8 1]

#### 7.8.9 例9 ####

给定网G：  
（1） 试着找出网G的最小生成树，画出其逻辑结构图。  
（2） 用两种不同的表示法画出网G的存储结构图。

![7.8.9题目][7.8.9]

解：  
（1）最小生成树如下图所示。

![7.8.9答案1][7.8.9_1]

（2）邻接矩阵表示和邻接表表示。

![7.8.9答案2][7.8.9_2]

--------------------

[Link 1]: http://blog.csdn.net/yuanlaijike/article/details/69442950
[Link 2]: http://blog.csdn.net/yuanlaijike/article/details/69451381
[Link 3]: http://blog.csdn.net/yuanlaijike/article/details/69472125
[Link 4]: http://blog.csdn.net/yuanlaijike/article/details/69480358
[Link 5]: http://blog.csdn.net/yuanlaijike/article/details/69486729
[Link 6]: http://blog.csdn.net/yuanlaijike/article/details/78070403
[Link 7]: http://blog.csdn.net/yuanlaijike/article/details/78074765
[Link 8]: http://blog.csdn.net/yuanlaijike/article/details/78078434
[Link 9]: http://blog.csdn.net/yuanlaijike/article/details/78078788
[20171107164935361]: /images/20220608/99627c1d267d4a6980ca1231273e5dc0.png
[7.1.4.1]: /images/20220608/8eeeb65bd45549ddb7b388ba6e534de4.png
[7.1.4.2]: /images/20220608/577dd67f15b94762a022e6927bac6229.png
[tmp]: /images/20220608/6ae7530144a147f9a8b6910e141cd6f1.png
[20171107165302919]: /images/20220608/aa62f326aa654cb99ad0285dbd8259dc.png
[20171107170257188]: /images/20220608/020fa38b30ad41e2b364dc750f19f543.png
[20170924014155942]: /images/20220608/b1ca3bb87db542ea9a2307ffafa946b4.png
[20170924014409918]: /images/20220608/34afd3f58487478681c7914ee577cf54.png
[20170924014423883]: /images/20220608/fe9609180f4445d49c45220650a65f5f.png
[20170924015009710]: /images/20220608/7e4585c879114761937242c6d8c69940.png
[20171107172022971]: /images/20220608/77eadd4aa7b94d3187ddddb052f29e3a.png
[20170924015107845]: /images/20220608/1a800381beff4be18d0e0315a674e04e.png
[20171107172119683]: /images/20220608/6e1fe6c1d2984415909a413f68436d5f.png
[20170924015616266]: /images/20220608/43ee89a34a6a4598ba7da3967a4987be.png
[20170924015647300]: /images/20220608/16648590286d4baf874b4d00b8cd17d4.png
[DFS]: /images/20220608/d4e141b6e25f4cf58dcb4e551da1eb9c.png
[DFS 1]: /images/20220608/76e053f775594e0e8071f67b775c01ec.png
[BFS]: /images/20220608/23bb62768716448e930615e431795cb3.png
[BFS 1]: /images/20220608/cac0c1cd234f406bab62dcfc8eec140c.png
[1]: /images/20220608/93a8086158144895b706a709d32ef63e.png
[1 1]: /images/20220608/45475ada3b3946a798c379b8d00b5162.png
[2]: /images/20220608/31116c119c974b9db5e9bb53494a2520.png
[2 1]: /images/20220608/5c92f1c62e9443a6aa5ea76b44a3f10f.png
[Prim]: /images/20220608/25ad4cf4a0814e15ab3597ca6089e4f0.png
[Kruskar]: /images/20220608/58a002402061446293bcedc5e1294cea.png
[7.5.1.3]: /images/20220608/c74fc25b122c491494a684710c3bdcd9.png
[7.5.1.3 1]: /images/20220608/5ece302f46d144d9bce9f8f517b30f4e.png
[7.6.4]: /images/20220608/7c82218173ef45c69ba1cc1a186cb6c2.png
[20170924024026315]: /images/20220608/c1a3a4147b29472281f63afc23ce1322.png
[7.8.6]: /images/20220608/99701554909d405da1f0fd88c504b1f8.png
[7.8.6 1]: /images/20220608/a2bf719f2e4f4239969f463e9a8244a5.png
[7.8.7]: /images/20220608/b7494ab452f44c1d997b6c34d0a76448.png
[7.8.8]: /images/20220608/342db010c56d47dbac5a3e5b2623d6ff.png
[7.8.8 1]: /images/20220608/6a10d2c045734f65a6ba07f6e05ff4b5.png
[7.8.9]: /images/20220608/8eafb71178004dcabd3af565d7eaf316.png
[7.8.9_1]: /images/20220608/f230655eda5447919558dcdd3b8f06f3.png
[7.8.9_2]: /images/20220608/801f322a13be447aad33deb4cc6a01bb.png