线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相

图

• 基本概念
  • 图G由顶点集V和边集E组成，记为G=(V，E)
    • V(G)表示图G中顶点的有限非空集。用|V|表示图G中顶点的个数，也称为图G的阶
      • 线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集
    • E(G)表示图G中顶点之间的关系（边）集合。用|E|表示图G中边的条数。
    • 分类
      • 有向图
        • 有向边（弧）的有限集合
          • 弧是顶点的有序对
          • 记为<v,w>,v是弧尾，w是弧头,<v, w> ≠ <w, v>
          • v邻接到w或w邻接自v
      • 无向图
        • 无向边的有限集合
          • 边是顶点的无序对
          • 记为（v,w)或(w,v)，（v,w）=(w,v)
          • w，v互为邻接点
  • 特殊图
    • 简单图
      • 1.不存在顶点到自身的边
      • 2.同一条边不重复出现
      • 数据结构仅探讨"简单图"
    • 多重图
      • 若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联
    • 子图与生成子图
    • 完全图
      • 无向完全图
        • 如果任意两个顶点之间都存在边
      • 有向完全图
        • 如果任意两个顶点之间都存在方向相反的两条弧
    • 根据边的数量分为稀疏图与稠密图
    • 树、森林
      • 不存在回路，且连通的无向图
      • n个顶点的树，必有n-1条边。
    • 有向树
      • 一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树
  • 度：以该顶点为一个端点的边数目
    • 无向图
      • 顶点V的度是指依附于该顶点的边的条数，记为TD(v)
      • 无向图的全部顶点的度的和等于边数的2倍
        • 所有顶点的度之和=2|E|
    • 有向图中
      • 顶点V的度分为出度和入度
      • 入度（ID）是以顶点v为终点的有向边的数目
      • 出度（OD）是以顶点V为起点的有向边的数目
      • 顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
      • 所有顶点的出度之和=入度之和=|E|
        • 所有顶点的度之和=2|E|
  • 权相关
    • 权
      • 图中每条边赋予一定意义的数值，这个数值叫做这条边的权
    • 网
      • 有权值的图称为带权图，也叫做网
    • 带权路径长度
      • 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
  • 顶点-顶点的关系描述
    • 路径相关
      • 路径
        • 顶点p到q之间的一条路径是指顶点序列，p,a,b,c,d,……q
      • 简单路径
        • 在路径序列中，顶点不重复出现的路径
      • 路径长度
        • 路径上边的数目
    • 回路相关
      • 回路
        • 第一个顶点和最后一个顶点相同的路径称为回路或环
      • 简单回路
        • 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
      • n个顶点的图，若 |E|>n-1，则一定有回路
    • 点到点的距离
      • 从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离
      • 若从u到v根本不存在路径，则记该距离为无穷
  • 图的局部
    • 连通相关
      • 连通
        • 顶点A到顶点B有路径，则称A与B之间是连通的
          • 无向图
      • 强连通
        • 顶点V到顶点W和顶点W到顶点V都有路径，则称这两个顶点是强连通的
          • 有向图
      • 连通图
        • 图中任意两个顶点都是连通的
        • 如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。
      • 强连通图
        • 图中任一对顶点都是强连通的
      • 连通分量
        • 无向图中的极大连通子图称为连通分量
        • 极大
          • 1.子图必需连通，顶点足够多
          • 2.极大连通子图包含这些依附这些顶点的所有边
          • 找连通分量的方法：从选取一个顶点开始，以这个顶点作为一个子图，然后逐个添加与这个子图相连的顶点和边直到所有相连的顶点都加入该子图
        • 结论1:如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。
      • 强连通分量
        • 有向图中的极大强连通子图称为有向图的强连通分量
        • 特点
          • 子图必须强连通
          • 同时保留尽可能多的边保留尽可能多的边
      • 连通图的生成树
        • 包含图中全部n个顶点，但是只有n-1条边的极小连通子图
        • 生成树去掉一条边则变成非连通图，加上一条边就会形成回路。
      • 非连通图的生成森林
        • 非连通图中，连通分量的生成树构成了非连通图的生成森林
• 存储结构
  • 邻接矩阵（顺序存储）
    • 普通图
      • 无向图
        • • 第i个结点的度 = 第i行（或第i列）的非零元素个数
      • 有向图
        • • 第i个结点的出度 = 第i行的非零元素个数
          • 第i个结点的入度 = 第i列的非零元素个数
          • 第i个结点的度 = 第i行、第i列的非零元素个数之和
    • 带权图（网）
    • 分析
      • 邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)
      • 适合用于存储稠密图
      • 只要确定了顶点编号，图的邻接矩阵表示方式唯一
      • 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）
  • 邻接表（顺序+链式存储）
    • 分析
      • 可对比树的孩子表示法
        • 孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针
      • 图的邻接表表示方式并不唯一
      • 无向图边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)
      • 有向图边结点的数量是|E|，整体空间复杂度为O(|V| + |E|)
  • 邻接表与邻接矩阵对比
  • 邻接多重表（无向图）
    • 结构
    • 代码
    • 分析
      • 空间复杂度：O(|V|+|E|)
      • 删除边、删除节点等操作很方便
      • 邻接多重表只适用于存储无向图
  • 十字链表（有向图）
    • 邻接表、邻接矩阵存储有向图
    • 结构
    • 代码
    • 分析
      • 空间复杂度：O(|V|+|E|)
      • 如何找到指定顶点的所有出边？——顺着绿色线路找
      • 如何找到指定顶点的所有入边？——顺着橙色线路找
      • 十字链表只用于存储有向图
  • 总对比
• 基本操作
  • 在邻接矩阵或邻接表结构下
  • Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)。
  • Neighbors(G,x)：列出图G中与结点x邻接的边
  • InsertVertex(G,x)：在图G中插入顶点x
  • DeleteVertex(G,x)：从图G中删除顶点x。
  • AddEdge(G,x,y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
  • RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
  • FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
  • NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
  • Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。
  • Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。
• 图的遍历
  • 深度优先遍历
    • 深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法
    • 代码
      • • • 连通图
        • • 非连通图
    • 分析
      • 空间复杂度
        • 由于DFS是一个递归算法，递归是需要一个工作栈来辅助工作，最多需要图中所有顶点进栈，所以时间复杂度为O(|V|)
      • 时间复杂度
        • 1)邻接表：遍历过程的主要操作是对顶点遍历它的邻接点，由于通过访问边表来查找邻接点，所以时间复杂度为O(|E|),访问顶点时间为O(|V|),所以总的时间复杂度为O(|V|+|E|)
        • 2)邻接矩阵：查找每个顶点的邻接点时间复杂度为O(|V|),对每个顶点都进行查找，所以总的时间复杂度为O(|V|^2)
      • 对⽆向图进⾏BFS/DFS遍历，调⽤BFS/DFS函数的次数=连通分量数
      • 遍历序列可变性
        • 同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀
        • 同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀
    • 深度优先生成树
      • 由深度优先遍历确定的树
      • 邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一
      • 遍历非连通图可得深度优先生成森林
  • 广度优先遍历
    • 广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法
    • 代码
      • • • 连通图
        • • 非连通图
    • 分析
      • 如果是⾮连通图，则一次BFS⽆法遍历完所有结点
      • 对于⽆向图，调⽤BFS函数的次数=连通分量数
      • 空间复杂度
        • BFS需要借助一个队列，n个顶点均需要入队一次，所以最坏情况下n个顶点在队列，那么则需要O(|V|)的空间复杂度。
      • 时间复杂度
        • 1)邻接表：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，就需要访问这个顶点的所有边，所以时间复杂度为O(|E|)。所以总的时间复杂度为O(|V|+|E|)
        • 2)邻接矩阵：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，需要遍历一遍矩阵的一行，所以时间复杂度为O(|V|),所以总的时间复杂度为O(|V|^2)
      • 遍历序列可变性
        • 同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀
        • 同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀
    • 广度优先生成树
      • 由广度优先遍历确定的树
      • 邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一
      • 遍历非连通图可得广度优先生成森林
  • 扩展
    • 对于连通图，只需调⽤1次 BFS/DFS
    • 对于强连通图，从任⼀结点出发都只需调⽤1次 BFS/DFS
    • 对⽆向图进⾏BFS/DFS遍历，调⽤BFS/DFS函数的次数=连通分量数
    • 对有向图进⾏BFS/DFS遍历，调⽤BFS/DFS函数的次数要具体问题具体分析
• 图的应用
  • 最小生成树
    • 生成树
      • 连通图的生成树是包含图中全部顶点的一个极小连通子图
      • 例子
        • 深度优先⽣成树
        • ⼴度优先⽣成树
      • 最小生成树最小代价树
        • 对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最⼩的⽣成树，则T称为G的最⼩⽣成树（Minimum-Spanning-Tree, MST）
        • 特点
          • 最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的
          • 最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路
          • 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身
          • 只有连通图才有⽣成树，⾮连通图只有⽣成森林
        • 求最小生成树
          • Prim算法
            • 从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。
          • Kruskal算法
            • 每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
    • 普利姆（Prim）
      • 算法思想
        • ①从图中找第一个起始顶点v0，作为生成树的第一个顶点，然后从这个顶点到其他顶点的所有边中选一条权值最小的边。然后把这条边的另一个顶点v和这条边加入到生成树中。
        • ②对剩下的其他所有顶点，分别检查这些顶点与顶点v的权值是否比这些顶点在lowcost数组中对应的权值小，如果更小，则用较小的权值更新lowcost数组。
        • ③从更新后的lowcost数组中继续挑选权值最小而且不在生成树中的边，然后加入到生成树。
        • ④反复执行②③直到所有所有顶点都加入到生成树中。
      • 代码
      • 分析
        • 双重循环，外层循环次数为n-1，内层并列的两个循环次数都是n。故普利姆算法时间复杂度为O(n^2)，而且时间复杂度只和n有关，所以适合稠密图
    • 克鲁斯卡尔（Kruskal）
      • 算法思想
        • 将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。
      • 代码
      • 分析
        • 克鲁斯卡尔算法操作分为对边的权值排序部分和一个单重for循环，它们是并列关系，由于排序耗费时间大于单重循环，所以克鲁斯卡尔算法的主要时间耗费在排序上。排序和图中边的数量有关系，所以适合稀疏图
  • 最短路径
    • 概念
      • 非带权图
        • 两点之间经过边数最少的路径
      • 带权图
        • 两点之间经过的边上权值之和最小的路径
    • 一个源点到其余顶点的最短路径
      • 广度优先遍历算法BFS
        • 算法思想
          • 就是对BFS的⼩修改，在visit⼀个顶点时，修改其最短路径⻓度 d[ ] 并在 path[ ] 记录前驱结点
            • • 2到8的最短路径⻓度 = d[8] = 3
              • 通过path数组可知，2到8的最短路径为：8 <— 7 <— 6 <— 2
        • 代码
        • 分析
          • 局限性
            • BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图
            • 不适用带权图
      • 迪杰斯特拉算法Dijkstra
        • 算法思想
          • 初始
            • 若从V0开始，令 final[0]=ture; dist[0]=0; path[0]=-1
            • 其余顶点final[k]=false; dist[k]=arcs[0][k]; path[k]= (arcs[0][k]==∞) ? -1 : 0
          • n-1轮处理
            • 循环遍历所有顶点，找到还没确定最短路径，且dist 最⼩的顶点Vi，令final[i]=ture。并检查所有邻接⾃Vi 的顶点，对于邻接⾃Vi 的顶点 Vj ，若 final[j]==false 且 dist[i]+arcs[i][j] < dist[j]，则令 dist[j]=dist[i]+arcs[i][j]; path[j]=i。（注：arcs[i][j]表示Vi 到Vj 的弧的权值
        • 代码
        • 分析
          • Dijkstra 算法不适⽤于有负权值的带权图这种图有可能没有最短路径
          • 也可⽤ Dijkstra 算法求所有顶点间的最短路径，重复 |V| 次即可，总的时间复杂度也是O(|V|^3)
          • 可对比普利姆算法
    • 所有顶点到所有顶点的最短路径
      • 弗洛伊德算法Floyd
        • 算法思想
          • 利用了动态规划思想
          • • 初始：不允许在其他顶点中转，最短路径是？
              • -1表示没有中转点
            • 若允许在 V0 中转，最短路径是？
            • 若允许在 V0、V1中转，最短路径是？
            • 若允许在 V0、V1、V2 中转，最短路径是？
        • 代码
        • 分析
          • 可以用于负权值带权图
          • 不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径
    • 对比
  • 有向无环图
    • 概念
      • 若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图（Directed Acyclic Graph）
    • DAG描述表达式
      • 步骤
        • Step 1：把各个操作数不重复地排成⼀排
        • Step 2：标出各个运算符的⽣效顺序（先后顺序有点出⼊⽆所谓）
        • Step 3：按顺序加⼊运算符，注意“分层”
        • Step 4：从底向上逐层检查同层的运算符是否可以合体
      • 分析
        • 同一个算术表达式所得到的有向无环图是不唯一的
  • 拓扑排序
    • AOV(Activity On Vertex)
      • 如果我们把每个环节看成图中一个顶点，在这样一个有向无环图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网
    • 拓扑排序
      • 在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：① 每个顶点出现且只出现⼀次。② 若顶点A在序列中排在顶点B的前⾯，则在图中不存在从顶点B到顶点A的路径。
      • 拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后⾯
      • 拓扑排序就是对一个有向图构造拓扑序列的过程，构造会有两种结果：如果此图全部顶点都被输出了，说明它是不存在回路的AOV网；如果没有输出全部顶点，则说明这个图存在回路，不是AOV网。
      • 每个AOV⽹都有⼀个或多个拓扑排序序列。
      • 拓扑排序：找到做事的先后顺序
    • 拓扑排序算法
      • 实现步骤
        • ① 从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。
        • ② 从⽹中删除该顶点和所有以它为起点的有向边。
        • ③ 重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。
      • 代码
      • 分析
        • 邻接表
        • 邻接矩阵
    • 逆拓扑排序算法
      • 实现步骤
        • ① 从AOV⽹中选择⼀个没有后继（出度为0）的顶点并输出。
        • ② 从⽹中删除该顶点和所有以它为终点的有向边。
        • ③ 重复①和②直到当前的AOV⽹为空。
      • 代码
    • DFS算法实现拓扑、逆拓扑排序
      • 拓扑排序
      • 逆拓扑排序
        • 代码
    • 性质
      • 拓扑排序、逆拓扑排序序列可能不唯一
      • 若图中有环，则不存在拓扑排序序列/逆拓扑排序序列
  • 关键路径
    • AOE(Activity On Edge)
      • 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹
      • 概念
        • 仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始；
        • 仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。
      • 性质
        • 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
        • 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。另外，有些活动是可以并⾏进⾏的
    • 关键路径与关键活动
      • 概念
        • 从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径
        • 把关键路径上的活动称为关键活动
        • 事件vk的最早发⽣时间ve(k)——决定了所有从vk开始的活动能够开⼯的最早时间
        • 活动ai的最早开始时间e(i)——指该活动弧的起点所表⽰的事件的最早发⽣时间
        • 活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差
        • 活动ai的时间余量d(i)=l(i)-e(i)，表⽰在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间
        • 若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动
        • 由关键活动组成的路径就是关键路径
      • 性质
        • 完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个⼯程的完成时间就会延⻓
        • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
        • 若关键活动耗时增加，则整个工程的工期将增长
        • 缩短关键活动的时间，可以缩短整个工程的工期
        • 当缩短到一定程度时，关键活动可能会变成非关键活动
      • 求解方法
        • ①求所有事件的最早发生时间ve（）
        • ②求所有事件的最迟发生时间vI（）
        • ③求所有活动的最早发生时间e（）
        • ④求所有活动的最迟发生时间I（）
        • ⑤求所有活动的时间余量d（）
          • d（i）=0的活动就是关键活动，由关键活动可得关键路径