基本数据结构复习之图的总结

简介

  • 概念:
    • 由顶点的有穷非空集合和顶点之间边的集合组成, 通常表示为: G(V,E), 其中, G表示一个图, V是图G中顶点的集合, E是图G中边的集合
  • 异同:
    • 线性表中把数据元素叫做元素, 树中将数据元素叫结点, 在图中数据元素叫做顶点(Vertex)
    • 线性表中可以没有数据元素,称为空表; 树中可以没有结点,叫做空树; 图中不允许没有顶点,若V是顶点的集合, 则集合V有穷且非空
    • 线性表中, 相邻的数据元素具有线性关系; 树结构中, 相邻两层的结点具有层次关系; 图中, 任意两个顶点之间都可能有关系, 顶点之间的逻辑关系用边来表示, 边集可以是空

相关定义

  • 无向边:
    • 若顶点vi, vj之间的边没有方向, 则称这条边为无向边, 用无序偶对(vi,vj)来表示
  • 无向图:
    • 如果图中任意两个顶点之间的边都是无向边, 则称该图为无向图
  • 无向完全图:
    • 在无向图中, 如果任意两个顶点之间都存在边, 则称该图为无向完全图
  • 有向边:
    • 若从顶点vi到vj之间的边有方向, 则称这条边为有向边, 也称为弧(Arc), 用有序偶<vi,vj>来表示, vi称为狐尾(Tail), vj称为弧头(Head)
  • 有向图(Directed graphs):
    • 如果图中任意两个顶点之间的边都是有向边, 则称该图为有向图
  • 有向完全图:
    • 在有向图中, 如果任意两个顶点之间都存在方向互为相反的两条弧, 则称该图为有向完全图
  • 简单图:
    • 在图中, 若不存在顶点到其自身的边, 且同一条边不重复出现, 则称这样的图为简单图
  • 权(Weight): 与图的边或弧相关的数
  • 网(NetWork): 带权的图
  • 子图:
    • 假设有两个图G=(V,{E}), G'=(V',{E'}), 如果V'包含于V, 且E'包含于E, 则称G'为G的子图

图的顶点与边间关系

  • 对于无向图G=(V,{E}), 如果边(v,v')属于E, 则称顶点v和v'互为邻接点(Adjacent), 即v与v'相邻接。边(v,v')依附于顶点v和v', 或者说(v,v')与顶点v和v'相关联。顶点v的度是和v相关联的边的数目, 记为TD(v)
    • $e=\frac{1}{2}\sum_{i=1}^nTD(v_i)$
  • 对于有向图G=(V,{E}), 如果边<v,v'>属于E, 则称顶点v邻接到v', 顶点v'邻接自v。弧<v,v'>和顶点v, v'相关联。以顶点v为头的弧的数目, 称为v的入度(InDegree), 记为ID(v); 以v为尾的弧的数目, 称为v的出度(OutDegree), 记为OD(v); 顶点v的度为TD(v) = ID(v) + OD(v)
    • $e=\sum_{i=1}^nID(v_i)=\sum_{i=1}^nOD(v_i)$
  • 回路或环(Cycle):
    • 第一个顶点到最后一个顶点相同的路径
  • 简单路径: 序列中顶点不重复出现的路径
  • 简单回路或简单环: 除了第一个顶点和最后一个顶点之外, 其余顶点不重复出现的回路

连通图

  • 连通图:
    • 在无向图G中, 如果从顶点v到顶点v'有路径, 则称v和v'是连通的。
    • 如果对于图中任意两个顶点vi, vj 属于E, vi和vj都是连通的, 则称G是连通图
  • 连通分量: 无向图中的极大连通子图
    • 要是子图
    • 子图要是连通的
    • 连通子图含有极大顶点数
    • 具有极大顶点数的连通子图包含依附于这些顶点的所有边
  • 强连通图:
    • 在有向图G中, 如果对于每一对vi、vj属于V, vi不等于vj, 从vi到vj和从vj到vi都存在路径, 则称G是强连通图
  • 强连通分量: 有向图中的极大强连通子图
  • 连通图的生成树: 是一个极小的连通子图, 它含有图中全部的n个顶点, 但只有足以构成一棵树的n-1条边
  • 有向树: 如果一个有向图恰有一个顶点的入度为0, 其余顶点的入度为1, 则是一棵有向树

图的抽象数据类型

ADT 图(Graph)
Data
    顶点的有穷非空集合和边的集合
Operation
    CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G
    DestroyGraph(*G): 图G存在则销毁
    LocateVex(G, u): 若图G中存在顶点u, 则返回图中的位置
    GetVex(G, v): 返回图G中顶点v的值
    PutVex(G, v, value): 将图G中顶点v赋值value
    FirstAdjVex(G, *v): 返回顶点v的一个邻接顶点, 若顶点在G中无邻接顶点返回空
    NextAdjVex(G, v, *w): 返回顶点v相对于顶点w的下一个邻接顶点, 若w是v的最后一个邻接点, 则返回空
    InsertVex(*G): 在图G中增添新顶点v
    DeleteVex(*G, v): 删除图G中顶点v及相关的弧
    InsertArc(*G, v, w): 在图G中增填弧<v,w>, 若G是无向图, 还需要添加对称弧<w,v>
    DFSTraverse(G): 对图G中进行深度优先遍历, 在遍历过程对每个顶点调用
    HFSTraverse(G): 对图G中进行广度有限遍历, 在遍历过程对每个顶点调用
endADT

存储结构

邻接矩阵(Adjacency Matrix)

  • 用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。设图G有n个顶点, 则邻接矩阵是一个n*n的方阵, 定义为 $$arc[i][j] = \begin{cases} 1, \quad 若(v_i,v_j)\in E或\left\langle v_i,v_j \right\rangle\in E\\ 0, \quad 反之 \end{cases} $$
  • 特性:
    • 无向图的边数是一个对称矩阵
    • 有向图中, 入度为列之和, 出度为行之和

网图表示

  • 定义:
    • 设图G是网图, 有n个顶点, 则邻接矩阵是一个n*n的方阵, 定义为: $$ arc[i][j] = \begin{cases} W_{ij}, \quad 若(v_i,v_j)\in E或\left\langle v_i,v_j \right\rangle\in E\\ 0, \quad 若i=j\\ \infty, \quad 反之 \end{cases} $$
  • 说明:
    • $W_{ij}$表示$(v_i,v_j)$或$\left\langle v_i,v_j \right\rangle$上的权值
    • $\infty$表示一个计算机允许的、大于所有边上的权值的值,也就是一个不可能的极限值

邻接表(Adjacency List)

  • 数组与链表相结合的存储方法称为邻接表
  • 有向图的逆邻接表: 对每个顶点vi都建立一个链接为vi为弧头的表

十字链表

  • 将邻接表和逆邻接表结合起来
    • 顶点表结构: data|firstin|firstout
      • firstin: 入边表头指针, 指向该顶点的入边表中第一个结点
      • firstout: 表示出边表头指针, 指向该顶点的出边表中的第一个结点
    • 边表结点结构: tailvex|headvex|headlink|taillink, 如果是网, 还可以增加一个weight域来存储权值
      • tailvex: 弧起点在顶点表的下标
      • headvex: 弧终点在顶点表的下标
      • headlink: 入边表指针域, 指向终点相同的下一条边
      • taillink: 指向边表指针域, 指向起点相同的下一条边

邻接多重表

  • 重新定义边表结构: ivex|ilink|jvex|jlink
    • ivex和jvex是与某条边依附的两个顶点在顶点表中的下标
    • ilink指向依附顶点ivex的下一条边
    • jlink指向依附顶点jvex的下一条边

边集数组

  • 由两个一维数组构成, 一个存储顶点的信息, 另一个存储边的信息。边数组的每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成

图的遍历(Traversing Graph)

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

深度优先遍历(Depth_First_Search)

  • 定义:
    • 从图中某个顶点v出发, 访问此顶点, 然后从v的未访问邻接点出发深度优先遍历图, 直至图中所有和v有路径相通的顶点都被访问到, 若图中尚有顶点未被访问到, 则另选图中一个未曾被访问到的顶点作为起点, 重复上述过程, 直至图中所有顶点都被访问到为止
  • 特征: 类似树的前序遍历
  • 不同存储结构比较: 对于n个顶点e条边的图
    • 邻接矩阵: O(n^2)
    • 邻接表: O(n+e)

广度优先遍历(Breadth_First_Search)

  • 定义:
    • 类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点
  • 特征: 类似树的层序遍历

异同

  • 同: 时间复杂度一样
  • 异:
    • 对顶点的访问顺序不同
    • 深度优先更适合目标比较明确, 以找到目标为主要目的的情况
    • 广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

最小生成树(Minimum Cost Spanning Tree)

  • 定义: 构造连通网的最小代价生成树

普里姆(Prim)算法

  • 定义:
    • 假设N = (P,{E})是连通网, TE是N上最小生成树中边的集合。算法从U = {u0}(u0属于V),TE={}开始。重复执行下述操作:在所有u属于U, v属于V-U的边(u,v)属于E中找一条代价最小的边(u0,v0)并入集合TE, 同时v0并入U, 直至U=V为止。此时TE中必有n-1条边, T=(V,{TE})为N的最小生成树。
  • 时间复杂度: O(n^2)
  • 证明: 反证法

克鲁斯卡尔(Kruskal)算法

  • 定义:
    • 假设N = (V,{E})是连通网, 则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}}, 图中每个顶点自成一个连通分量。在E中选择代价最小的边, 若该边依附的顶点落在T中不同的连通分量上, 则将此边加入到T中, 否则舍去此边而选择选择下一条代价最小的边。依次类推, 直至T中所有的顶点都在同一连通分量上为止。
  • 时间复杂度:O(eloge)
  • 证明: 归纳法

使用场景

  • 普里姆算法对于稠密图, 即边数非常多的情况更好些
  • 克鲁斯卡尔算法主要针对边来展开, 边数少时效率会非常高, 对于稀疏图有很大优势

最短路径

  • 非网图: 由于边上没有权值, 最短路径指两顶点之间经过的边数最少的路径
  • 网图: 两顶点之间经过的边上权值之和最少的路径, 称路径上第一个顶点是源点, 最后一个顶点是终点。

迪杰斯特拉(Dijkstra)算法

  • 定义概述:
    • 典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径,主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
  • 时间复杂度: O(n^2)

弗洛伊德(Floyd)算法

  • 定义概述:
    • 解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。
  • 时间复杂度: O(n^3)
  • 空间复杂度: O(n^2)

拓扑排序

  • 无环: 图中没有回路

介绍

  • AOV网(Activity On Vertex NetWork):
    • 在一个表示工程的有向图中, 用顶点表示活动, 用弧表示活动之间的优先关系, 这样的有向图为顶点表示活动的网。
  • 拓扑序列:
    • 设G=(V,E)是一个具有n个顶点的有向图, V中的顶点序列v1,v2,...,vn, 满足若从顶点vi到vj有一条路径, 则在顶点序列中顶点vi必须在vj之前。
  • 拓扑排序:
    • 对一个有向图构造拓扑序列的过程

拓扑排序算法

  • 解决问题: 工程能否顺利的进行
  • 基本思路:从AOV网中选择一个入度为0的顶点输出, 然后删去此顶点, 并删除以此顶点为尾的弧, 继续重复此步骤, 直到输出全部顶点或者AOV网中不存在入度为0的顶点为止
  • 时间复杂度: O(n+e)

关键路径

  • 解决问题: 工程完成需要的最短时间

介绍

  • AOE网:
    • 在一个表示工程的带权有向图中, 用顶点表示事件, 用有向边表示活动, 用边上的权值表示活动的持续时间, 这种有向图的边表示活动的网。
  • 路径长度:
    • 路径上各个活动所持续的时间之和
  • 关键路径:
    • 从源点到汇点具有最大长度的路径
  • 关键活动: 关键路径上的活动

算法描述

  • 准备两个数组
    • a:最早开始时间数组etv
    • b:最迟开始时间数组。(针对顶点即事件而言)

步骤:

  1. 从源点V0出发,令etv[0](源点)=0,按拓扑有序求其余各顶点的最早发生时间etv[i](1 ≤ i ≤ n-1)。同时按照上一章拓扑排序的方法检测是否有环存在。

    • 顶点Vk的最早发生时间etv[k]公式: $$ etv[k] = \begin{cases} 0, \quad 当 k = 0 时\\ max{etv[i] + len \left\langle v_i,v_j \right\rangle}, \quad 当k\neq0且\left\langle v_i,v_j \right\rangle\in P[k] \end{cases} $$
    • P[k]表示所有到达顶点Vk的弧的集合
    • $len \left\langle v_i,v_j \right\rangle为弧\left\langle v_i,v_j \right\rangle上的权值$
  2. 从汇点Vn出发,令ltv[n-1] = etv[n-1],按拓扑排序求各个其余各顶点的最迟发生时间ltv[i](n-2 ≥ i ≥ 2);

    • 顶点Vk的最晚发生时间ltv[k]公式: $$ ltv[k] = \begin{cases} etv[k], \quad 当 k = n-1 时\\ min{ltv[j] + len \left\langle v_i,v_j \right\rangle}, \quad 当k\lt n-1且\left\langle v_i,v_j \right\rangle\in S[k] \end{cases} $$
    • S[k]表示所有从顶点Vk出发的弧的集合
    • $len \left\langle v_i,v_j \right\rangle为弧\left\langle v_i,v_j \right\rangle上的权值$
    • 其实是把拓扑序列倒过来进行
  3. 根据各顶点的etv和ltv数组的值,求出弧(活动)的最早开工时间和最迟开工时间,求每条弧的最早开工时间和最迟开工时间是否相等,若相等,则是关键活动。
  • 注意:
    • 1,2 完成点(事件)的最早和最迟。
    • 3根据事件来计算活动最早和最迟,从而求的该弧(活动)是否为关键活动

参考

标签: none

添加新评论