阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

一、图

  • 图是一种数学结构,数学里有‘图论’,研究这种拓扑结构
  • 数据结构课程把图看成一类复杂数据结构,用于表示具有各种复杂关系的数据集合。
  • 重点算法
    • 图的深度优先搜索与广度优先搜索
    • 最小生成树的Prim
    • 求单源最短路径的Dijkstra算法
    • 求所有顶点对之间最短路径的Floyd算法
    • 拓扑排序
    • 关键路径

1.基本概念

  • 一个图是一个二元组G=(V,E),其中:
    • V是顶点的非空有穷集合(也可以有空图的概念,但用处不大)
    • E是顶点偶对(称为边)的集合,E⊆VxV
    • V中顶点也称为图G的顶点,E中的边也称为图G的边
  • 有向图&无向图
    • 有向图:有向图中的边有方向,边是顶点的有序对
      有序对用尖括号表示。< vi , vj >表示从vi到vj的有向边,vi称为边的始点,vj是边的终点。< vi , vj >和< vj , vi >是不同的两条有向边
    • 无向图:无向图中的边没有方向,是顶点的无序对
      无序对用圆括号表示,(vi,vj)和(vj,vi)表示同一条无向边
a.概念与性质
  • 如果G里有边< vi , vj >⊆E(或(vi,vj)⊆E)
    • 顶点vj称为vi的邻接顶点(对无向图,邻接点事双向的)
    • 这种边称为与顶点vi相关联的边或vi的邻接边
  • 图可用图形自然表示(圆圈表示顶点,线段或箭头表示边)
    • 不考虑顶点到自身的边
    • 顶点间没有重复出现的边
  • 完全图:任意两顶点之间都有边的图。显然:
    • n个顶点的无向完全图有n*(n-1)/2条边
    • n个顶点的有向完全图有n*(n-1)条边
  • 注意一个重要事实:|E|≤|V|2,也即|E|=O(V|2)
    也就是说,边的条数可能达到顶点数的平方
  • 度(顶点的度)
    与一个顶点邻接的边的条数。对有向图,度数还进一步分为入度和出度,分别表示以该顶点为始点或者终点的边的条数
  • 顶点数n,边数e和度数满足如下关系:
    边数等于各顶点度数之和的一半
  • 路径
    对于图G=(V,E),如果存在顶点序列vi0,vi1...vim,使得(vi0,vi1),(vi1,vi2)...(vi(m-1),vim)都在E中(都是G的边,对于有向图是< vi0,vi1 >,< vi1,vi2 >...< vi(m-1),vim >都在E中)
    • 则说从顶点vi0到vim存在一条路径
    • < vi0,vi1...vim >称为是从vi0到vim的路径
  • 路径长度
    路径上边的条数
  • 回路(环)
    起点和终点相同的路径。如果除起点和终点外的其他顶点均不相同,则称为简单回路
  • 简单路径
    内部不包含回路的路径,即路径上的顶点除起点和终点可能相同外,其它顶点均不相同,简单回路也是简单路径
  • 子图
    对图G=(V,E)和G'=(V',E'),如果V'⊆V且E'⊆E,就称G'是G的子图。特别低,G是自身的子图
  • 有根图
    有向图G里存在一个顶点v,从v到图G中其它每个顶点均有路径,则称G为一个有根图,称v为图G的一个根。有根图中的根可能不唯一
  • 连通性
    如果无向图G中有从vi到vj的路径,则称它们是连通的(顶点到自身默认连通)
    • 无向图G的连通性:
      • 连通图:若G中任意两不同顶点之间都连通,则称G为一个连通图
      • G的极大连通子图(连通分量)G'是G的连通子图,且G中没有包含G'的连通子图。若G不连通,则其连通分量多于一个
      • G的连通分量形成了G的一个划分
    • 有向图G的连通性:
      • 强连通图:若G中任意两不同顶点之间都有路径,则称G为一个强连通图
      • 强连通分量:G的极大强连通子图
      • G的连通分量形成其顶点的一个划分
  • 带权图
    图中的每条边都被赋予一个权值
    • 权值可用于表示实际应用中与顶点关联有关的某些信息
    • 带权的连通无向图称为网络

2.图的基本操作

  • 创建图,创建空图,或基于顶点和边的数据创建图
  • 顶点的个数(vertex_num)和边的条数
  • 所有顶点的集合vertices,所有边的集合edges
  • 增加一条边<v1,v2>或(v1,v2),是否存在边<v1,v2>或(v1,v2),get_edge(g,v1,v2)
  • 顶点v的入度和出度(结果用二元序列表示),vdegree(v)
  • 找出顶点v相邻边(集合或表),如出边out_edges(v)
a.遍历操作
  • 与树遍历的最重要差异是:
    • 需要防止再次进入已经遍历过的部分
    • 需要考虑图的连通性问题(若图不连通,遍历完一个连通分支,还要继续遍历其它连通分支)

3.图的表示

  • 图的结构比较复杂,任意两个顶点间都可能存在边
    • 需要表示顶点及顶点间的边,存在很多可能的方法
    • 应该根据具体应用和需要做的操作等选择图的表示方法
  • 图的最基本表示方法是邻接矩阵表示法。表示图中邻接关系的矩阵通常非常稀疏,空间浪费可能很大。很多图中边数与顶点数成线性关系,如中国铁路线路图。为降低空间代价,人们提出需要可看做邻接矩阵的’压缩‘b的方法:
    • 邻接表表示法
    • 邻接多重表表示法
    • 图的十字链表表示,等
a.邻接矩阵表示法
  • 邻接矩阵就是一个表示图中顶点间邻接关系的方阵,设G=(V,E)为n个顶点的图,其邻接矩阵如下矩阵A:
    $$ A[i,j] =
    \begin{cases}
    1, & {若(v_i,v_j)或<v_i,v_j>是图G的边} \
    o, & {若(v_i,v_j)或<v_i,v_j>不是图G的边}
    \end{cases}$$
  • 邻接矩阵只表示图中顶点个数和顶点间联系(边)
    • 每个顶点对应一个矩阵下标
    • 通过一对下标可以确定图中一条边的有无
  • 若顶点本身还有其他信息,就需要另外的方式表示顶点信息
    • 例如,可以考虑另外用一个顶点表
    • 可以用与矩阵同样下标引用同一顶点的表元素
  • 下面无向图G1的邻接矩阵,无向图的邻接矩阵总是对称矩阵

    v0------------ v3
    |   、     /
    |       、 
    |   /        、
    v1------------v4

    $$
    \begin{Bmatrix}
    0 & 1 & 1 & 1 \
    1 & 0 & 1 & 1 \
    1 & 1 & 0 & 0 \
    1 & 1 & 0 & 0 \
    \end{Bmatrix}
    $$

  • 带权图的边附带有用信息,用邻接矩阵表示时,可以把权信息记录在矩阵里。矩阵元素是边的权值,无边的情况另行表示。wij是边的权
    $$ A[i,j] =
    \begin{cases}
    w_{ij}, & {若(v_i,v_j)或<v_i,v_j>是图G的边} \
    o, & {若(v_i,v_j)或<v_i,v_j>不是图G的边}
    \end{cases}$$
b.邻接表表示法
  • 与树的'子表表示'类似
    • 一个顶点表用来表示图中顶点及其相关信息
    • 顶点表中每个顶点关联着一个邻接表,记录其邻接顶点
  • 无向图
    • 一个顶点表,每个顶点有一个邻接边的表
    • 边(vi,vj)在顶点vi,vj的边表各有一结点,在边表中存储两次
    • 顶点vi的边表中结点个数等于其度数
  • 有向图
    • 一个顶点表,每个顶点关联着一个边表
    • 顶点vi的边表里每个结点对应的是以vi为始点的一条边,因此可称为出边表
    • 顶点vi的边表中结点个数等于其出度

二、图的实现

  • 在python里实现图数据结构有很多方法
    • 例如用list的list(或tuple的tuple)直接实现邻接矩阵。使用方便,判邻接简单,但存储代价较大,不适合较大的图
    • 用字典从下标序对映射到邻接边的值。检索效率高,适合稀疏矩阵(邻接矩阵常如此)。字典实现复杂
    • 用python内置的Bytes字节向量类似或标准库的array类型。前者存储效率高,可能用于实现很大的图,编程复杂一些;后者可以表示整数或浮点权值的带权图,编程也标记复杂
    • 自定义类型实现邻接表表示,下面考虑两种简单技术
  • 下面假定有一个全局变量infinity表示无穷大,如果带权图中不同的两顶点间无边,就以infinity作为边的权值,infinity=float("inf")

1.邻接矩阵实现

  • 实现问题:
    • 矩阵元素可以是1或权值表示边,用一个特殊值表示“无联”
    • 假设用户提供一个unconn值,默认为0
    • 构造函数基于给定的矩阵参数建立一个图
a.程序实现:
class Graph(object):
    def __init__(self, mat, unconn = 0):
        vnum1 = len(mat)
        for x in vnum1:
            if len(x) != vnum1:
                raise ValueError("Argument for 'GraphA' is bad.")
        self.mat = [mat[i][:] for i in range(vnum1)]
        self.unconn = unconn
        self.vnum = vnum1

    def vertex_num(self):
        return self.vnum
    def add_edge(self, vi, vj, val = 1):
        assert 0 <= vi <= self.vnum and 0 <= vj <= self.vnum
        self.mat[vi][vj] = val
    # 不支持增加顶点,若要支持,还需每行增加元素,比较麻烦
    def add_vertex(self):
        raise AdjGraphError("Adjacent Matrix does not support 'add_vertex'")
    def get_edge(self, vi, vj):
        assert 0 <= vi <= self.vnum and 0 <= vj <= self.vnum
        return self.mat[vi][vj]

    def out_edges(self,vi):
        assert 0 <= vi <= self.vnum
        return self._out_edges(self.mat, vi, self.unconn)

    # 定义为静态方法,可能在其他地方使用    
    @staticmethod
    def _out_edges(mat, vi, unconn):
        edges = [], row = mat[vi]
        for i in len(row):
            if row[i] != unconn:
                edges.append((i,row[i]))
        return edges

    # 内置函数str()调用它生产Graph对象的字符串表示,用于存入文件或输出
    def __str__(self):
        return "[\n" + "\n".join(map(str, self.mat)) + "\n]\n"\
            + "Unconnected:" + str(self.unconn)

2.压缩的邻接矩阵(邻接表)实现

  • 邻接矩阵表示的缺点是空间复杂性与结点数的平方成正比,有时矩阵中大部分元素是infinity(或者0)
  • 考虑一种'压缩'表示形式:
    • 每个顶点的邻接边用一个list表示,元素形式为(wj,w),wj是边的终点,w是边的信息
    • 整个图就是这种list的list,每个元素对应一个顶点
    • 很容易添加顶点
    • 可以采用与前面Graph同样的接口,定义同样名字的方法,
    • 内部表示采用新的一套,一些方法可以继承
a.程序实现:
class GraphA(Graph):
    def __init__(self, mat, unconn = 0):
        vnum1 = len(mat)
        for x in mat:
            if len(x) != vnum1:
                raise ValueError("Argument for 'GraphA' is bad.")
        self.mat = [Graph._out_edges(mat, i, unconn) for i in range(vnum1)]
        self.vnum = vnum1
        self.unconn = unconn

    def add_vertex(self):
        self.mat.append([])
        self.vnum += 1
        return self.vnum -1

    def add_edge(self, vi, vj, val = 1):
        assert 0 <= vi <= self.vnum and 0 <= vj <= self.vnum
        row = self.mat[vi]
        for i in range(len(row)):
            if row[i][0] == vj:
                self.mat[vi][vj] = (vj, val)
                return
            if row[i][0] > vj:
                break
        else:
            i += 1
        self.mat[vi].insert(i, (vj, val))
    # 这里用顺序检索插入/访问,结点的出度很小时操作的效率不是问题。如果结点出度很大,可以考虑用二分检索,或为每个结点关联一个dict,以支持快速插入和访问

    def get_edge(self, vi, vj):
        assert 0 <= vi <= self.vnum and 0 <= vj <= self.vnum
        for i , val in mat[vi]:
            if i == vj:
                return val
        return self.unconn

    def out_egdes(self, vi):
        assert 0 <= vi <= self.vnum
        return self.mat[vi]

三、图算法

  • 很多实际问题可以归结为图和图上的计算
    • 网络路由
    • 集成电路的设计和布线
    • 运输和物流中的各种规划安排问题
    • 工程项目的计划安排
    • 许多社会问题计算,如金融监管
  • 一旦从应用中抽象出'图',应用问题的解决就可能变成图算法问题

1.图的遍历

  • 遍历:按某种方式系统访问图中所有顶点且每个顶点仅访问一次的过程,也称为图的周游。前面讨论的状态空间中的状态和相邻关系就形成了一个图,图的遍历对应于一次穷尽的状态空间搜索
  • 遍历的基本部分是访问以顶点所在连通分支的全部顶点。如果图不连通,还要考虑对其他部分的访问
    • 基本的图遍历方法同样是深度优先遍历和宽度优先遍历

2.深度优先遍历

  • 按照深度优先搜索(Depth—First Search)的方式遍历,做法是:
    • 从指定顶点v出发,先访问v(并将其标记为已访问)
    • 从v的未访问过的邻接顶点出发进行深度优先搜索(邻接顶点可能排一种顺序),直到与v连通的所有顶点都已访问(递归)
    • 如果图中还有未访问的顶点,则选出一个,由它出发,重复上述过程,直至图中所有顶点访问完
  • 通过深度优先遍历顺序得到的顶点序列称为该图的深度优先搜索序列,简称DFS序列
    • 对邻接点的不同访问顺序就得到不同的DFS序列(不唯一)
    • 如果规定了图中各顶点的邻接点顺序,就确定了DFS序列

3.广度优先遍历

  • 通过广度优先搜索(Breadth-First Search)方式遍历,做法是:
    • 从指定顶点v出发,先访问v(并将其标记为已访问)
      *依次访问v的所有邻接顶点v1,v2...vm(可按顺序),再依次访问与v1,v2...vm邻接的所有未访问顶点,直到所有顶点都访问完
    • 如果图中还有未访问的顶点,则选出一个,由它出发,重复上述过程,直至图中所有顶点访问完
  • 通过广度优先搜索遍历得到的顶点序列称为该图的广度优先搜索序列,简称为BFS序列
    • 如果规定了图中各顶点的邻接点顺序,BFS序列就确定了

4.非递归深度优先遍历

a.程序实现
def DFS_graph(graph, v0):
    vnum = graph.vertex.num
    visited = [0]*vnum
    visited[v0] = 1
    DFS_seq = [v0]
    st = SStack()
    st.push((0, graph._out_egdes(vo)))
    while not st.is_empty:
        i, edges = st.pop()
        if i < len(edges):
            v, e = edges[i]
            st.push((i+1, edges))
            if not visited[v]:
                DFS_seq.append(v)
                visited[v] = 1
                st.push((0, graph._out_edges(v)))
    return DFS_seq
b.X复杂性分析

四.X遍历和生成树

五、最小生成树

  • 网络G(带权连通无向图)的每条边带有给定的权值,它的一棵生成树中各条边的权值之和称为该生成树的权
  • 网络G可能有很多棵生成树,其权值可能不同。其中权值最小的生成树称为G的最小生成树(Minimum Spanning Tree,MST)
    • 显然,网络必有最小生成树,但可能不唯一
  • 最小生成树有很多实际应用:
    • 顶点看作城市,边的权看作城市之间的通讯成本,根据最小生成树建立的是城市间成本最低的通讯网
    • 可以考虑成本最低的公路网;输电网;城市配送中心与线路规划;集成电路或印刷电路板的地线、供电线路等等
  • 表示这类应用的带权图中各结点到自身的权应取0,到其他结点有边时有具体的权值,无边时取无穷大infinity。下面的算法均如此假定

1.Kruskal算法

  • 设G=(V,E)是一个网络,算法过程如下:
    • 初始时只取包含G中n个顶点而无边的孤立点子图T=(V,{}),T中每个顶点自成一个连通分量。下面考虑T的扩充
    • 将E中的边按权的递增顺序排序
    • 构造中每步按从小到大的顺序选一条两端点位于T中不同连通分量的边e,把e加入T。由于e将两顶点连接,因此两个不同连通分量合成一个(每次操作减少一个连通分量)
    • 不断重复加入新边,直到T中所有顶点都包含在一个连通分量,该连通分量就是G的一棵最小生成树
    • 若上述操作最终得不到一个包含G中所有顶点的连通分量,则原图不连通,无最小生成树。算法做出的是G的最小连通树林
a.算法分析
  • 关键是连通分量的判定,可建立一个表来记录与维护每个顶点的连通分量,初始时各顶点的连通分量为顶点自身为代表
b.程序实现
def Kruskal(graph):
    vnum = graph.vertex_num()
    reps = [i for i in range(vnum)]
    mst, edges = [], []
    for vi in range(vnum):
        for v, w in graph._out_edges(vi):
            edges.append((w, (vi, v)))
    edges.sort()
    for w, e in edges:
        if reps[e[0]] != reps[e[1]]:
            mst.append((e, w))
            if len(mst) == vnum-1
                break
            rep, orep = resp[e[0]], reps[e[1]]

            for i in range(vnum):
            # 把顶点v所在连通分量上各顶点的连通分量属性设置为顶点vi的连通分量属性,可互换
                if reps[i] == orep:
                    resp[i] = rep
    return mst
c.X复杂性分析

2.MST性质

  • 设G=(V,E)是网络,U是V的任一真子集,e=(u,v)∈E且u∈U,v∈V-U,而且e在G中所有一个端点在U另一端点在V-U的边中权值最小,那么:G必有一棵包含边e的最小生成树

3.Prim算法

  • 基本思想:从一个顶点出发,利用MST性质选最短连接边扩充已连接的顶点集,直至该集合包含了所有顶点或最终确定不是连通图
  • 算法细节:
    • 从图G的顶点集V中任选取一顶点V0放入集合U中,此时U={V0},边集合TE={},T=(U,TE)是一棵树
    • 检查所有一个顶点在集合U里另一个顶点在集合V-U的边,找出权值最小边e=(u,v)(u∈U,v∈V-U),将顶点v加入到集合U,并将
      e加入到TE,T依然是一棵树。
    • 重复上面步骤直至U=V。此时TE有n-1条边,T就是G的一棵最小生成树
  • 生成树用类似构造DFS生成树的数据表示,用vnum个元素的表mst保存最小生成树的边,mst[1]=((1,3),10)表示顶点1到3的边在mst且权值为10,mst[i] = None表示i不属于U。
  • 用一个优先队列cands记录候选的最短边,元素形式为(w,i,j),表示从顶点i到j的边为候选,其权值为w
a.算法过程
  • 初始把(0,0,0)放入优先队列,表示从顶点0到自身的长0的边
  • 循环的第一次迭代将把顶点0记入最小生成树顶点集U,方法是设mst[0] = (0,0)。同时把顶点0到其余顶点的边按权值存入优先队列cands,表示待考察的候选边集合
  • 执行中反复选择cands里记录的最短边(u,v)。如确定它是连接U中顶点与V-U中顶点的边,就把这条边及其权记入must[v],并把v的出边存入cands,否则直接丢掉
  • 结束时mst是最小生成树的n条边(包括(0,0)边以方便实现)
b.程序实现
def Prim(graph):
    vnum = graph.vertex_num()
    mst = [None]*vnum
    cands = PriQueue([(0, 0, 0)])
    count = 0
    while count < vnum and not cands.is_empty:
        w, v, vmin = cands.dequeue()
        if mst[vmin]:
            contunue # 回到循环开始处
        count += 1
        mst[vmin] = ((vmin, v), w)
        for edge in graph.out_edges(vmin):
            v, w = edge
            if not mst[v]:
                cands.enqueue(w, vmin, v)
    return mst
c.X复杂性分析
d.prim算法改进
  • 若新加入顶点的邻接边对应的顶点v的权值w比已存入堆中包含v顶点邻接边的权值小则将堆中顶点v的邻接边替换为新的更小的并重排堆
  • 若顶点还没确定邻接边,则其邻接边权值为infinity无穷大,表示无邻接边
e.X改进后程序实现

4.最小生成树问题的复杂性

  • 最小生成树是一个非常重要的问题,人们对它做了很多进一步的研究,取得了许多成果
    • 有一个证明了复杂度为O(|E|)的随机算法
    • 有一个证明了复杂度为O(|E|@(|E|,|V|))的已知最优算法,其中的@是Ackermman(m,n)的逆函数
    • 并行算法方面的工作
    • ...
  • 最小生成树研究还没结束。研究已经确定该问题的时间复杂度下界为O(|E|),但还没找到这样的算法,也没找到更高的下界

六、最短路径

  • 定义:
    • 在网络或带权有向图里,从顶点v到v'的一条路径上各条边的长度之和称为该路径的长度
    • 从v到v'的所有路径中长度最短的路径就是最短路径,最短路径的长度为从v到v'的距离,记为dis(v,v')
  • 最短路径在实际应用中特别有价值
    • 运输
    • 加工或者工作流程
  • 单源点最短路径问题要求求出从一给定顶点到其他所有顶点的最短路径

1.Dijkstra算法

  • 要求所有边的权不小于0
  • 假设要找从V0到其他顶点的最短路径,执行过程:
    • 把图中顶点分为两个集合:当时已知最短路径的顶点集合U和尚不知道最短路径的顶点集合V-U
    • 算法逐步扩充已知最短路径的顶点集合,每次从V-U中找到下一个新顶点(它是当时已能确定最短路径的顶点)加入U
    • 反复这样做,直到找出V0到所有顶点的最短路径
  • 过程分析:
    • 初始:在集合U中放入顶点V0
      • V0到V0的距离为0
      • 对V-U里的顶点,如果(V0,V)∈E,则V的已知 最短路径长度为w(V0,V),否则令V的已知最短路径长为∞
    • 从V-U中选出当时已知最短路径长度最小的顶点Vmin加入U(此时到Vmin的已知最短路径长度cdis(V0,Vmin)就是V0到Vmin的距离)
    • 由于Vmin加入,V-U中某些顶点的已知最短路径长度可能改变:
      • 如果从V0经过Vmin到V'的路径长度比原已知的最短路径长度更短,这就是V'的新的已知最短路径长度,该路径经过Vmin到V'
      • 记录新的最短路径及距离,支持下面继续选择V-U的最近顶点
    • 反复选择顶点并记录新的最短路径信息,直到从V0可达的所有顶点都在集合U中为止。如果存在未加入U的顶点,说明图不连通
a.程序实现:
def dijkstra(graph, v0):
    vnum = graph.vertex_num()
    assert 0 <= v0 < vnum
    paths = [None]*vnum
    cands = PrioQueue([(0, v0, v0)])
    count = 0
    while count < vnum and not cands.is_empty():
        plen, u, vmin = cands.dequeue()
        if papths[vmin]: continue
        paths[vmin] = (u, plen)
        for v, w in graph.out_edges(vmin):
            if paths[v] is None:
                cands.enqueue((plen + w, vmin, v))
        count += 1
    return paths
b.X复杂性分析

2.各对顶点之间最短距离:Floyd算法

  • 可利用Dijkstra算法,依次把每个顶点作为起始点
  • Floyd(Floyd-Warshall)算法可以一次直接计算出各对顶点间的所有最短路径及长度
    • 该算法的基本想法来自Warshall的强连通子图算法(基于邻接矩阵),实际上是求可达性(有边相邻)的传递闭包
  • 基本思想:
    • 设图G=(V,E)有n个顶点,用邻接矩阵作为存储结构
    • 如果边(v,v')∈E,那么它就是这两顶点的路径,长度可直接得到,即A[v][v']。但这一路径未必是从v到v'的最短路径,可能有途径其它顶点的更短路径。
      • 问题就是要在v到v'的可能经过任何顶点的路径中找出最短路径
    • 开始:每对v到v'的途中不经过任何结点的路径长度为已知
      • 有边时为边的权,无边时认为是∞
    • k=0:对每对v和v',除已知直接路径外,从v到v‘途经顶点的下标不大于k(此时是不大于0)的路径可分为两段:
      • <v,v0>,<v0,v'>,如果没有,则认为为∞
      • 其长度是两段路径的长度和。将其与已知最短路径比较,可确定途经顶点下标不大于0的最短路径
    • k=1:对每对顶点v和v',从v到v'途经顶点的下标不大于k,即不大于1的新路径可分为两段:
      • <v,...,v1>,<v1,...,v'>
      • 这两段内部所经过的顶点下标都不大于0,<v,v0>,<v0,v'>已在前一步确定。
      • 用新路径与已知最短路径比较,即可确定v到v'的途经顶点下标不大于1的最短路径
    • 考虑k:每对v和v',途经顶点的下标不大于k(已知不大于k-1)的最短路径可分为两段:
      • <v,...,vk>,<vk,...,v'>
      • 这两段内部所经过的顶点下标都不大于k-1,< v, vk-1 >,< vk-1, v'>`在前一步已确定
      • 用新路径与已知最短路径比较,即可确定从v到v'的途经顶点下标不大于k的最短路径
    • 如此继续,直到做完k=n-1,也就对于每对v和v',确定了从v到v'的所有路径中的最短路径
a.Floyd算法实现
  • 这里假定结点的下标为0到n-1,实现该算法,需要迭代式地计算一系列方阵
  • 为此要生成一系列nXn方阵Ak(0<=k<=n),其中Ak[i][j]表示从vi到vj的途经顶点为v0,v1,...,vk-1的最短路径长度
    • A0就是图的邻接矩阵A,A0[i][j]表示从vi到vj不经过任何顶点的最短路径长度
    • An[i][j]是从vi到vj的最短路径长度
  • 矩阵系列A0,A1,...An可递推计算(0<=i<-n-1,0<=j<=n-1):
    • A0[i][j]=A[i][j],直接有邻接矩阵得到
    • Ak+1[i][j]=min{Ak[i][j],Ak[i][k]+Ak[k][j]},0<=k<=n-1,这时新考虑了途经顶点vk的路径,因此Ak+1[i][j]为vi到vj的途经顶点的下标不大于k的最短路径长度
    • An[i][j]为vi到vj的最短路径长度
b.Floyd程序实现及分析
路径表示
  • 实现算法时还需要设法做出所有路径的记录
  • 下面考虑另外安排一系列n阶方阵nvertexk,其中nvertexk[v][v']的值为在从v到v'的中间允许有顶点v0,v1,...,vk-1的最短路径上,顶点v的后继顶点v"的下标
  • 到最后v"到v'的最短路径也应已知,可以根据后继顶点追溯
  • 初始时,如果A0[i][j]=∞(没有边),则令nvertex0[i][j]=-1,否则令其为j,表示vj是vi的后继顶点
  • 在由Ak计算Ak+1时,Ak+1[i][j]被置为Ak[i][k]+Ak[k][j],那么就设nvertexk+1[i][j]=nvertexk[i][k],即从vi到vj的路径上vi的后继顶点就是原来vi到vk的路径上vi的后继顶点
  • 该轮计算完,nvertexk+1[i][j]就是vi到vj可以途经顶点v0,v1,...,vk的最短路径上vi的后继顶点
  • 计算完成后,nvertexn[i][j]就是从vi到vj的最短路径上vi的后继顶点。追溯这个矩阵,可得到任何一对结点之间的最短路径
距离表示
  • 算法从A0=A开始。递推生成一系列的矩阵A1,A2,...,An,后以矩阵可能与前一矩阵不同
  • 问题:是否真需要用一个新的二维矩阵表存放下一个矩阵?
  • 假设已经算出了Ak保存在矩阵A里,现考虑Ak+1的计算。Ak+1[i][j]=min{Ak[i][j],Ak[i][k]+Ak[k][j]}
  • 注意:所有新的Ak+1[i][j]或者就是Ak[i][j],或者是下面的一列和一行中的元素求和计算:
    Ak[0][k], Ak[1][k], ..., Ak[n-1][k]
    Ak[k][0], Ak[k][1], ..., Ak[k][n-1]
  • 注意:如果在计算Ak+1过程中可能修改矩阵第k行或第k列元素,在后面去元素[i][k]或[k][j]得到的将不是Ak的元素,就必须保留Ak。即如果计算中修改了后面要用的元素,就需要另外用一个新矩阵,否则就不需要,直接在矩阵里更改
  • 实际上Ak+1计算不会修改矩阵第k行或第k列的元素,因为:
    Ak+1[i][k]=min{Ak[i][k],Ak[i][k]+Ak[k][k]}
    Ak+1[k][j]=min{Ak[k][j],Ak[k][k]+Ak[k][j]}
    而上Ak-1的对角线元素上Ak-1[m][m]总是0(对所有m),所以
    Ak+1[i][k]=Ak[i][k]
    Ak+1[k][j]=Ak[k][j]
  • 因此计算过程可以用同一个A实现所有的Ak,矩阵的递推计算过程可以通过直接更新A里元素的方式实现
  • 计算Ak+1[i][j]=min{Ak[i][j],Ak[i][k]+Ak[k][j]},其中新矩阵元素的生成用赋值A[i][j]:=A[i][k]+A[k][j]实现
  • 计算所有顶点对之间最短路径的长度,只需要一个矩阵
c.程序实现
def all_shortest_paths(graph):
    vnum = graph.vertex_num()
    a = [[gragh.out_edtes(i,j) for j in range(vnum)]
            for i in range(vnum)]
    nvertex = [[-1 if a[i][j] == infinity else j for j in range(vnum)]
                for i in range(vnum)]
    for x in range(vnum):
        for i in range(vnum):
            for j in range(vnum):
                dis = a[i][x] + a[x][j]
                if dis < a[i][j]:
                    a[i][j] = dis
                    nvertex[i][j] = nvertex[i][k]
d.X复杂性分析

3.最短路径算法分析

  • Dijkstra算法基于类似于最小生成树的想法,或者说是一种“宽度优先搜索”。其中用到了类似MST的性质
    • 它逐个找出可以确定最短路径的顶点,同时也找到了到新确定最短路径的顶点的路径
    • 做完前一步后更新信息,保证记录的都是至今已知的最短路径
    • 这是典型的动态规划方法(在计算中保留一些信息支持动态决策)
  • Floyd算法基于完全不同的考虑,求解所有顶点间的最短路径
    • 其基本方法是为最终问题的解决逐步累积信息,根据已有的信息更新包含部分信息的解得雏形,最终得到问题的解
    • 这一算法也是一个典型的动态规划方法
    • 过程中求子结构(子问题)的最优解,最后得到原问题的最优解

七、AOV网

  • 考虑有向图的一类应用‘方式’,用图中的顶点表示某种‘工程’里的活动,图中的边表示活动之间的顺序关系。这样的有向图称为顶点活动网(Activity On Vertex network),或称AOV网
  • AOV网中的边常用语表示活动之间的制约关系
    • 要解决的一个问题就是根据图中制约关系作出有关活动的安排
    • 这样考虑,可以把AOV网络用于各种工程计划
  • 有一些问题,AOV网的顶点或边还可能带有权值。可以考虑
    • 最优安排问题
    • 最大或最小流问题

1.拓扑排序

  • 定义:对给定的AOV网N,如果N中的所有顶点能排成一个线性序列S=vi1,vi2,...,vin,满足:如果N中存在从顶点vi到vj的路径,那么S里vi排在vj之前。则S称为N的一个拓扑序列,构造拓扑序列的操作称为拓扑排序
  • AOV网未必有拓扑序列。不难证明,一个AOV网存在拓扑序列,当且仅当它不包含回路(存在回路,意味着某些活动的开始要以其自身的完成作为先决条件,这种现象称为活动之间的死锁)

2.性质

  • 如果一个AOV网有拓扑序列,其拓扑序列未必唯一
  • 将AOV网N的拓扑序列反向得到的序列,都是N的逆网的拓扑序列
  • 假设用AOV网表示一个工程的安排
    • 网中顶点代表工程的活动,顶点之间的有向边代表活动之间的制约关系
    • 如果在实际条件下各种活动只能串行进行,则那么该AOV网的一个拓扑序列就是整个工程得以顺利完成的一种可行方案
  • 任何无回路AOV网都可以做出拓扑序列,方法很简单:
    • 从AOV网中选出一个入度为0的顶点作为序列的下一个顶点
    • 从AOV网中删除此顶点及其所有的出边
      反复执行上面两步操作,直到输出了所有可输出顶点时拓扑排序结束,如果剩下入度非0顶点就说明该AOV网里存在回路,无拓扑序列

3.算法分析

  • 遍历所有顶点,统计各顶点的入边数
  • 从初始顶点出发,将该顶点所有出边对应的终点的入边数减一,将入边数变为0的顶点加入栈
  • 从栈中取出栈顶的顶点作为下一个出发顶点,重复第二步,直到栈变为空

4.程序实现(书写图片)

七、AOE网

  • AOE网(Activity On Edge network)是另一类常用带权有向图,这是一种重要PERT(Program Evaluation and Review Technique)模型
  • 抽象看,AOE网是一种无环的带权有向图
    • 顶点表示事件,有向边表示活动
    • 边上的权值通常表示活动的持续时间
    • 一个顶点表示的事件也就是它的入边所表示的活动都已完成,它的出边所表示的活动可以开始的状态(事件)
  • AOE网中活动可以并行进行
    • 只要一项活动的前提事件均已发生(该边的始点为终点的所有活动),这项活动就可以开始
    • 因此完成整个工程的最短时间是从开始顶点到完成顶点的最长路径长度(路径上各边权值之和)
  • 从开始顶点到完成顶点的最长路径称为关键路径。

1.重点理解

  • 一个事件vj的最早发生时间,必须保证vj的前驱事件均已发生,因此取最大值,也就是各活动以最早发生时间发生中,但却是最迟完成的,即各前驱事件的最早发生时间与活动持续时间之和的最大值
  • 一个事件vi的最迟发生时间,必须保证不延误vi的所有后驱事件的发生,因此取最小值,也就是各活动以最迟发生时间发生中,但却是最先开始的,即各后驱事件的最迟发生时间减去活动持续时间之差的最小值

2.算法分析

  • 生成拓扑序列
  • 最早发生时间计算:初始设置每个顶点的最早发生时间为0。按拓扑序列的顺序取出顶点,每取出一个顶点i,对于该顶点每条出边的终点j,若i的最早发生时间与该出边的权值之和大于j已知的最早发生时间,则更新j的最早发生时间为更大值
  • 最迟发生时间计算:初始设置每个顶点的最迟发生时间为最后顶点的最迟发生时间。按拓扑序列的逆序取出顶点,每取出一个顶点i,对于该顶点的每条出边的终点j,若j的最迟发生时间减去该出边的权值后小于i已知的最迟发生时间,则更新i的最迟发生时间为更小值

3.程序实现(书写图片)

最后由 oucb 编辑于2017年05月11日 14:10