通知
此博客运行在jpress系统上,如果你喜欢此博客模板,请加QQ群:1061691290(whimurmur模板/jpress插件),免费下载使用

第四章 图

4291人浏览 / 0人评论 | 作者:whisper  | 分类: 数据结构  | 标签: 数据结构  | 

作者:whisper

链接:http://proprogrammar.com:443/article/88

声明:请尊重原作者的劳动,如需转载请注明出处


    说明:本章主要讲了图(基本概念,存储),遍历(深度优先搜索,广度优先搜索),图的四种应用(最小生成树,最短路径,拓扑排序,关键路径),对四种应用并没有给出相应的算法(对算法的考查重点在二叉树)

    图的定义与基本术语

    (一)图的定义

    图(Graph)是一种网状数据结构,形式化定义如下:

        Graph=(V, R)
        V={x|x ∈ DataObject}
        R={VR}, VR={<x, y>|P(x, y)∧(x, y ∈ V)}

     集合 DataObject 中的所有元素具有相同的特性。 V 中的数据元素通常称为顶点(vertex), VR 是两个顶点之间关系的集合, P(x,y)表示 x 和 y 之间有特定的关联属性 P。

     若<x, y> ∈ VR,则<x, y>表示从顶点 x 到顶点 y 的一条弧(arc),并称 x 为弧尾(tail)或起始点,称 y 为弧头(head)或终端点,此时图中的边是有方向的,称这样的图为有向图。

     若<x, y> ∈ VR,且有<y, x> ∈ VR,即 VR 是对称关系,这时以无序对(x, y)来代替两个有序对,表示 x 和 y 之间的一条边(edge),此时的图称为无向图。

     ADT Graph{
        数据对象 V: V 是具有相同特性的数据元素的集合, 称为顶点集。
        数据关系 R:
            R={VR}, VR={<x, y>|P(x, y)∧(x, y ∈ V)}
        基本操作 P:
            CreateGraph(&G,V,VR);
            初始条件: V 是图的顶点集, VR 是图中弧的集合。
            操作结果:按 V 和 VR 的定义构造图 G。
            DestroyGraph(&G);
            初始条件:图 G 存在。
            操作结果:销毁图 G。
            LocateVex(G,u);
            初始条件:图 G 存在, u 和 G 中顶点有相同特征。
            操作结果:若 G 中存在顶点 u, 则返回该顶点在图中位置; 否则返回其它信息。
            GetVex(G,v);
            初始条件:图 G 存在, v 是 G 中某个顶点。
            操作结果:返回 v 的值。
            PutVex(&G,v,value);
            初始条件:图 G 存在, v 是 G 中某个顶点。
            操作结果:对 v 赋值 value。
            FirstAdjVex(G,v);
            初始条件:图 G 存在, v 是 G 中某个顶点。
            操作结果:返回 v 的第一个邻接顶点。若顶点在 G 中没有邻接顶点,则返回“空”。
            NextAdjVex(G,v,w);
            初始条件:图 G 存在,v 是 G 中某个顶点,w 是 v 的邻接顶点。
            操作结果:返回 v 的(相对于 w 的)下一个邻接顶点。若 w 是 v 的最后一个邻接点,则返回“空”。
            InsertVex(&G,v);
            初始条件:图 G 存在, v 和图中顶点有相同特征。
            操作结果:在图 G 中增添新顶点 v。
            DeleteVex(&G,v);
            初始条件:图 G 存在, v 是 G 中某个顶点。
            操作结果:删除 G 中顶点 v 及其相关的弧。
            InsertAcr(&G,v,w);
            初始条件:图 G 存在, v 和 w 是 G 中两个顶点。
            操作结果:在 G 中增添弧<v,w>,若 G 是无向的,则还增添对称弧<w,v>。
            DeleteArc(&G,v,w);
            初始条件:图 G 存在, v 和 w 是 G 中两个顶点。
            操作结果:在 G 中删除弧<v,w>,若 G 是无向的,则还删除对称弧<w,v>。
            DFSTraverser(G,Visit());
            初始条件:图 G 存在, v 是 G 中某个顶点, Visit 是顶点的应用函数。
            操作结果:深度优先遍历图 G,并对每个顶点调用函数 Visit 一次。一旦 Visit()失败,则操作失败。
            BFSTRaverse(G,Visit());
            初始条件:图 G 存在, Visit 是顶点的应用函数。
            操作结果:广度优先遍历图 G,并对每个顶点调用函数 Visit 一次。 一旦 Visit()失败,则操作失败。
    }ADT Graph

     (二)基本术语

     1. 完全图稀疏图稠密图

     设 n 表示图中顶点个数,用 e 表示图中边或弧的数目, 且不考虑图中每个顶点到其自身的边或弧。

     对于无向图而言,其边数 e 的取值范围是 0~n(n-1)/2。我们称有 n(n-1)/2 条边(即图中每个顶点和其余 n-1 个顶点都有边相连)的无向图无向完全图

     对于有向图而言,其边数 e 的取值范围是 0~n(n-1)。我们称有 n(n-1)条弧(即图中每个顶点和其余 n-1 个顶点都有弧相连)的有向图有向完全图

     对于有很少条边的图(e<nlogn)称为稀疏图反之称为稠密图。

     2. 子图

     设图 G=(V,{VR}) 和图 G′=(V′,{VR′}),且 V′⊆V, VR′⊆VR,则称 G′ 为 G 的子图。

     3. 邻接点

     对于无向图 G=(V, {E}),如果边(v, v’)∈E,则称顶点 v, v’互为邻接点,即v, v’相邻接。边(v, v’)依附于顶点 v 和 v’,或者说边(v, v’)与顶点 v 和 v’相关联

     对于有向图 G=(V, {A}),如果弧<v, v’>∈A,则称顶点 v 邻接到顶点 v’,顶点 v’邻接自顶点 v,或者说弧<v, v’>与顶点 v 和 v’相关联

     4. 入度出度

    对于无向图而言,顶点 v 的度是指和 v 相关联的边的数目,记作(v)。

     在有向图中,顶点 v 的度有出度和入度两部分,其中以顶点 v 为弧头的弧的数目成为该顶点的入度,记作 ID(v),以顶点 v 为弧尾的弧的数目称为该顶点的出度,记作OD(v),则顶点 v 的度为 TD(v)=ID(v)+OD(v)。

     一般地,若图 G 中有 n 个顶点, e 条边或弧,则图中顶点的边与度的关系为:

                                     

     5.

     在一个图中,每条边上可以标上具有某种含义的数值,此数值称为该边的权,通常权为非负实数,可以表示从一个顶点到另一个顶点的距离或耗费等信息。边上带有权的图称为带权图,也常称作网。

    6. 路径回路

     无向图 G=(V, {E})中从顶点 v 到 v’的路径是一个顶点序列(v=vi0, vi1, vi2,…,vin=v’),其中(vij-1, vij) ∈E, 1≤j≤n。如果图 G 是有向图,则路径也是有向的,顶点序列应满足<vij-1, vij>∈E, 1≤j≤n。

     路径的长度是指路径上经过的弧或边的数目。在一个路径中,若其第一个顶点和最后一个顶点是相同的,即 v=v’,则称该路径为回路或环。若表示路径的顶点序列中的顶点各不相同,则称这样的路径简单路径。除了第一个和最后一个顶点外,其余各顶点均不重复出现的回路简单回路

    7. 连通图(针对无向图)

     在无向图 G=(V, {E})中,若从 vi到 vj有路径相通,则称顶点 vi与 vj是连通的。如果对于图中的任意两个顶点 vi、 vj ∈V, vi, vj都是连通的,则称该无向图 G 为连通图。

    无向图中的极大连通子图称为该无向图的连通分量

    注意:

    任何连通图的连通分量只有一个,即其自身(如无向图 G)。

    非连通的无向图有多个连通分量(如无向图 G3)。

    在有向图 G=(V, {A})中,若对于每对顶点 vi, vj ∈ V 且 vi≠vj,从 vi到 vj和 vj到vi都有路径,则称该有向图为强连通图(针对有向图)。

    有向图的极大强连通子图称为 G 的强连通分量

    注意:

    强连通图只有一个强连通分量,即是其自身。

    非强连通的有向图有多个强连通分量。

    8. 生成树

     一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但是只有足以构成一棵树的 n-1 条边,如下图。

    如果在一棵生成树上添加一条边,必定构成一个环。

     如果一个图有 n 个顶点和小于 n-1 条边,则是非连通图,如果多于 n-1 条边则一定有环。

    图的存储结构

     (一)数组表示法(或邻接矩阵表示法)

     用两个数组分别存储数据元素(顶点)的信息和数据元素(顶点)之间关系的信息。

    若图 G 是一个具有 n 个顶点的无权图, G 的邻接矩阵是具有如下性质的 n×n 矩阵A:

     若图 G 是一个有 n 个顶点的网,则它的邻接矩阵是具有如下性质的 n×n 矩阵 A:

    邻接矩阵存储结构的形式化说明如下:

#define INFINITY INY_MAX //最大值∞
#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef enum {DG, DN, UDG, UDN} GraphKind;  //{有向图,有向网,无向图,无向网}

typedef struct ArcCell {
    VRType adj; // VRType 是顶点关系类型,对无权图,用 1 或 0 表示是否相邻;对带权图,则为权值类型。
    InfoType *info; //该弧相关信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs; //邻接矩阵
    int vernum, arcnum; //图的当前顶点数和弧数
    GraphKind kind; //图的种类标志
}MGraph;

    图的数组表示法的特点如下:

    存储空间:对于无向图而言,它的邻接矩阵是对称矩阵,可采用压缩存储法,即只存储其下三角元素即可,这样,一个具有 n 个顶点的无向图 G,它的邻接矩阵需要n(n-1)/2 个存储空间即可。

    但对于有向图而言,其中的弧是有方向的,因此有向图的邻接矩阵不一定是对称矩阵,对于有向图的邻接矩阵的存储则需要 n²个存储空间。

    便于运算:采用邻接矩阵,便于判定图中任意两个顶点之间是否有边相连。另外还便于求得各个顶点的度,对于无向图而言,其邻接矩阵第 i 行元素之和就是图中第 i 个顶点的度:

                                               

    对于有向图而言,其邻接矩阵第 i 行元素之和就是图中第 i 个顶点的出度:

                                               

    其邻接矩阵第 i 列元素之和就是图中第 i 个顶点的入度:

                                               

     采用数组法表示图,便于实现图的一些基本操作,如实现访问图 G 中 v 顶点第一个邻接点的函数 FirstAdjVex(G, v)可按如下步骤实现:

     1.首先由 LocateVex(G, v)找到 v 在图中的位置,即 v 在一维数组 vexs 中的序号i。

     2.二维数组 arcs 中第 i 行上第一个 adj 域非零的分量所在的列号 j,便是 v 的第一个邻接点在图 G 中的位置。

     3.取出一维数组 vexs[j]中的数据信息,即与顶点 v 邻接的第一个邻接点的信息。

    (二)邻接表表示法

     图的数组表示法(即邻接矩阵表示法),虽然有其自身的优点,但对于稀疏图来讲,会造成存储空间的很大浪费。

     邻接表(Adjacency List) 表示法实际上是图的一种链式存储结构,它克服了邻接矩阵的弊病。在邻接表中,对图中的每个顶点建立一个带头结点的单链表,第 i 个单链表中的结点表示依附于顶点 vi的边(若是有向图,则表示以 vi为弧尾的弧)所关联的另一个顶点。每个单链表的头结点又构成一个表头结点表。

    图的邻接表表示由表头结点表与每个顶点的链表两部分构成。

     表头结点表:由所有表头结点以顺序结构的形式存储,以便随机访问任一顶点的链表。表头结点的结构如下图所示由两部分构成,其中数据域(data)用于存储顶点的名或其它有关信息,链域(firstarc)用于指向链表中第一个顶点(即与顶点 vi邻接的第一个邻接点)。

                                        

    顶点单链表的每个结点由 3 个域组成,其中邻接点域(adjvex)指示与顶点 vi邻接的点在图中的位置,链域(nextarc)指示下一条边或弧相关联的顶点,数据域(info)存储和边或弧相关的信息。

                           

    如果是网如何表示呢?

    邻接表存储结构的形式化说明如下:

#define MAX_VERTEX_NUM 20 //最多顶点个数

typedef struct ArcNode { //链表中的结点
    int adjvex; //该弧指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
    InfoType *info; //与该弧相关的信息
} ArcNode;

typedef struct VNode { //表头结点
    VertexType data; //顶点信息
    ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; //一维数组存放表头结点
    int vexnum, arcnum; //图的当前顶点数和弧数
    int kind; //图的种类标志
}ALGraph;

    存储空间的分析

    对于有 n 个顶点、 e 条边的无向图而言,若采取邻接表作为存储结构,则需要 n 个表头结点和 2e 个表结点。很显然在边很稀疏(即 e<<n(n-1)/2 时)的情况下,用邻接表存储所需的空间比邻接矩阵所需的空间 n(n-1)/2 要节省得多

    无向图的度

    在无向图的邻接表中,顶点 vi的度恰好就是第 i 个单链表上结点的个数。

     有向图的度

     在有向图中,第 i 个单链表上结点的个数是顶点 vi的出度,只需通过表头结点表找到第 i 个顶点的单链表的头指针,实现顺链查找即可。

     如要判定任意两个顶点(vi和 vj)之间是否有边或弧相连,或求得第 i 个顶点的入度,则需要搜索所有的单链表,这样比较麻烦。

     一种解决的方法是逆邻接表法,我们可以对每一顶点 vi再建立一个逆邻接表,即对每个顶点 vi建立一个所有以顶点 vi为弧头的弧的表,如下图所示。

     (三)有向图的十字链表(方便计算入度)

    (四)无向图的邻接多重表(消除了重复边)

    图的遍历

     从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶点仅被访问一次的过程。

     (一)深度优先搜索
     (二)广度优先搜索

     (一)深度优先搜索遍历

    连通图的深度优先搜索遍历

    从图中某个顶点 V0 出发,访问此顶点,然后依次从 V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和 V0有路径相通的顶点都被访问到。

     W1、 W2和 W3 均为 V 的邻接点, SG1、 SG2 和 SG3 分别为含顶点 W1、 W2和W3 的子图。

    访问顶点 V ;

    for (W1、 W2W3 )

    若该邻接点 W 未被访问,则从它出发进行深度优先搜索遍历。

    从上面的图解可见:

    1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历;
    2. 如何判别 V 的邻接点是否被访问?

    解决的办法是:为每个顶点设立一个 “访问标志 visited[w]” ;

void DFS(Graph G, int v) {
    // 从顶点 v 出发,深度优先搜索遍历连通图 G
    visited[v] = TRUE; VisitFunc(v);

    for(w=FirstAdjVex(G, v);w!=0; w=NextAdjVex(G,v,w))
       // 对 v 的尚未访问的邻接顶点 w
       // 递归调用 DFS
       if (!visited[w]) DFS(G, w);
} // DFS

    非连通图的深度优先搜索遍历

    首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点,如果未被访问,则以该顶点为起始点,进行深度优先搜索遍历,否则继续检查下一顶点。

void DFSTraverse(Graph G, Status (*Visit)(int v)) {
    // 对图 G 作深度优先遍历。
    VisitFunc = Visit;
    for (v=0; v<G.vexnum; ++v)
        visited[v] = FALSE; // 访问标志数组初始化

    for (v=0; v<G.vexnum; ++v)
        if (!visited[v]) DFS(G, v);     // 对尚未访问的顶点调用 DFS
}

     (二)广度优先搜索遍历

     对连通图,从起始点 V 到其余各顶点必定存在路径。

     其中, V->w1, V->w2, V->w8的路径长度为 1; V->w7, V->w3, V->w5的路径长度为 2;V->w6, V->w4的路径长度为 3。

     从图中的某个顶点 V0出发,并在访问此顶点之后依次访问 V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有 和 V0有路径相通的顶点都被访问到。

     若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

void BFSTraverse(Graph G, Status (*Visit)(int v)){
    for (v=0; v<G.vexnum; ++v)
        visited[v] = FALSE; //初始化访问标志

    InitQueue(Q); // 置空的辅助队列 Q

    for ( v=0; v<G.vexnum; ++v )
        if ( !visited[v]) { // v 尚未访问
            visited[v] = TRUE; 
            Visit(v); // 访问 u
            EnQueue(Q, v); // v 入队列

            while (!QueueEmpty(Q)) {
                DeQueue(Q, u);
                // 队头元素出队并置为 u
                for(w=FirstAdjVex(G, u); w!=0;w=NextAdjVex(G,u,w))
                    if ( ! visited[w]) {
                        visited[w]=TRUE; Visit(w);
                        EnQueue(Q, w); // 访问的顶点 w 入队列
                    } // if
            } // while
        }
} // BFSTraverse

     对于 n 个顶点 e 条边的图来说,深度、广度优先遍历算法时间复杂度是一样的:
    1.邻接矩阵由于是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,因此需要 O(n2)的时间。
    2.邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。

    归纳总结

    1.深度优先搜索一般利用递归实现(要用到访问标志);广度优先搜索不是一个递归的过程(要用到访问标志和队列);
    2.一个给定的图的邻接矩阵是唯一的,但对于邻接表来说,如果边的输入先后次序不同,生成的邻接表表示也不同。因此,对于同样一个图,基于邻接矩阵表示的遍历所得到的 DFS 序列或 BFS 序列是唯一的,基于邻接表表示的遍历所得到的 DFS 序列或 BFS 序列可以是不唯一的。

     (连通网的) 最小生成树

     问题:

     假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1 条线路,如何在最节省经费的前提下建立这个通讯网?

     该问题等价于:

     构造网的一棵最小生成树,即:在 e 条带权的边中选取 n-1 条边(不构成回路),使“权值之和”为最小。

     算法一:(普里姆算法)(插点法)

    算法二:(克鲁斯卡尔算法)(插边法)

     1.普里姆算法的基本思想:

     取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点 v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n 个顶点为止。

    所得生成树权值和= 14+8+3+5+16+21 = 67

    一般情况下所添加的顶点应满足下列条件:

    在生成树的构造过程中,图中 n 个顶点分属两个集合:已落在生成树上的顶点集U 和尚未落在生成树上的顶点集 V-U ,则应在所有连通 U 中顶点和 V-U 中顶点的边中选取权值最小的边。

    2.克鲁斯卡尔算法的基本思想:

    考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。

    具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使 SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止。

     算法描述:
    构造非连通图 ST=( V,{ } );
    k = i = 0; // k 计选中的边数
    while (k<n-1) {
        ++i;
        检查边集 E 中第 i 条权值最小的边(u,v);
        若(u,v)加入 ST 后不使 ST 中产生回路,
        则 输出边(u,v); 且 k++;
   }

    比较两种算法

算法名 普里姆算法 克鲁斯卡尔算法
时间复杂度 O(n2) O(eloge)
适应范围 稠密图 稀疏图

    归纳总结:

    如果连通带权图中各边上的权重互不相等,构造出来的最小生成树是唯一的;如果存在权值相等的边,由于选择的次序不同,构造出来的最小生成树是不唯一的,不过它们总的权值之和应相同。

     拓扑排序

      问题:

     假设以有向图表示一个工程的施工图或程序的数据流图,则图中不允许出现回路。

    检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。(还可以对顶点进行深度优先搜索,如果搜索到第一个顶点,那么说明有环)

     何谓“拓扑排序”?

     对有向图进行如下操作:按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列.

     例如:对于下列有向图

    可求得拓扑有序序列: A B C D 或 A C B D

    反之,对于下列有向图不能求得它的拓扑有序序列。

     因为图中存在一个回路 {B, C, D}

     如何进行拓扑排序?

     一、从有向图中选取一个没有前驱的顶点,并输出之;
     二、从有向图中删去此顶点以及所有以它为尾的弧;

    重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。

     在算法中需要用定量的描述替代定性的概念

    没有前驱的顶点 ≡≡ 入度为零的顶点

    删除顶点及以它为尾的弧 ≡≡ 弧头顶点的入度减 1

    为避免每次都要搜索入度为零的顶点,在算法中设置一个“栈”,以保存“入度为零”的顶点。

    归纳总结:

    如果一个结点有多个直接后继,则拓扑排序的结果通常不唯一;但如果各个顶点已经排在一个线性有序的序列中,每个顶点都有唯一的前趋后继关系,则再做拓扑排序,排序的结果是唯一的。

    关键路径

     假设以有向网表示一个施工流图,弧上的权值表示完成该项子工程所需时间。

     问:哪些子工程项是“关键工程”?

    即:哪些子工程项将影响整个工程的完成期限的。

    整个工程完成的时间为:从有向图的源点汇点最长路径

     “关键活动”指的是:该弧上的权值增加将使有向图上的最长路径的长度增加。如何求关键活动?

     什么是“关键活动” ?

    该活动的最早开始时间=该活动的最迟开始时间

     “事件(顶点)” 的 最早发生时间 ve(j)

                            ve(j) = 从源点到顶点 j 的最长路径长度;

    “事件(顶点)” 的 最迟发生时间 vl(k)

                            vl(k) = 从顶点 k 到汇点的最短路径长度;

    假设第 i 条弧为 <j, k>
    则 对第 i 项活动
    “活动(弧)”的 最早开始时间 ee(i)
    ee(i) = ve(j);
    “活动(弧)”的 最迟开始时间 el(i)
    el(i) = vl(k) – dut(<j,k>);
    事件发生时间的计算公式:
    ve(源点) = 0;
    ve(k) = Max{ve(j) + dut(<j, k>)}
    vl(汇点) = ve(汇点);
    vl(j) = Min{vl(k) – dut(<j, k>)}

  a b c d e f g h k
ve 0 6 4 5 7 7 15 14 18
vl 0 6 6 8 7 10 16 14 18

    拓扑有序序列: a - d - f - c - b - e - h - g - k

  ab ac ad be ce df eg eh fh gk Hk
6 4 5 1 1 2 8 7 4 2 4
e 0 0 0 6 4 6 7 7 7 15 14
l 0 2 3 6 6 8 8 7 10 16 14
               

    算法的实现要点:

     显然,求 ve 的顺序应该是按拓扑有序的次序; 而求 vl 的顺序应该是按拓扑逆序的次序; 因为拓扑逆序序列即为拓扑有序序列的逆序列,因此应该在拓扑排序的过程中,另设一个“栈”记下拓扑有序序列。

    归纳总结:

     如果在关键路径上的任一关键活动出现时间延误。然而,如果同时存在几条关键路径,任一关键活动加速,不一定能加速整个工程的进度。只有“桥”(及某一处于所有关键路径上的关键活动)的情况例外。

    最短路径

    1.求从某个源点到其余各点的最短路径
    2.每一对顶点之间的最短路径

    1.求从源点到其余各点的最短路径的算法的基本思想:

     依最短路径的长度递增的次序求得各条路径。其中,从源点到顶点 v 的最短路径是所有最短路径中长度最短者。

     (1)路径长度最短的最短路径的特点:
    在这条路径上,必定只含一条弧,并且这条弧的权值最小。
    (2)下一条路径长度次短的最短路径的特点:
    它只可能有两种情况:或者是直接从源点到该点(只含一条弧); 或者是,从源点经过顶点 v1,再到达该顶点(由两条弧组成)。
    (3)再下一条路径长度次短的最短路径的特点:
     它可能有三种情况:或者是,直接从源点到该点(只含一条弧); 或者是,从源点经过顶点 v1,再到达该顶点(由两条弧组成);或者是,从源点经过顶点 v2,再到达该顶点。
    (4)其余最短路径的特点:
    它或者是直接从源点到该点(只含一条弧); 或者是,从源点经过已求得最短路径的顶点,再到达该顶点。

    求最短路径的迪杰斯特拉算法:

     设置辅助数组 Dist,其中每个分量 Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。

     一般情况下, Dist[k] = <源点到顶点 k 的弧上的权值>或者 = <源点到其它顶点的路径长度>+ <其它顶点到顶点 k 的弧上的权值>

     迪杰斯特拉算法的应用演示

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

     弗洛伊德算法的基本思想是:从 vi到 vj的所有可能存在的路径中,选出一条长度最短的路径。

    算法演示:

     本章学习重点


    1. 熟悉图的各种存储结构及其构造算法,了解实际问题的求解效率与采用何种存储结构和算法有密切联系。
    2. 熟练掌握图的两种搜索路径的遍历:遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。
    3. 理解各种图的应用算法。

 


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!