第七章：图

这是一个关于第七章：图的思维导图，涵盖了图的基本概念、存储结构、遍历、最小生成树、拓扑排序以及图的基本操作等重要知识点，适合用于课程学习、复习备考等场景。

第七章图

• 大题 题型一:图的存储结构 ①画出邻接矩阵。 ②画出邻接表。 题型二:图的遍历 ①深度优先生成树及深度优先遍历序列。 ②广度优先生成树及广度优先遍历序列。 题型三:最小生成树。 ①画出普里姆算法下的最小生成树。 ②画出克鲁斯卡尔算法下的最小生成树。 题型四:最短路径。 ①用迪杰斯特拉算法求单源最短路径。 题型五:拓扑排序。 ①写出拓扑有序序列。
• 图的基本操作
  • 1、构造图操作
    • 形式
      • CreateGraph（&G，V，R）
    • 条件
      • V是图的顶点集，R是图的弧集
    • 结果
      • 根据顶点集和弧集构造图G
  • 2、求顶点位置操作
    • 形式
      • LocateVex（G，V）
    • 条件
      • 图G已经存在
    • 结果
      • 给出顶点V在图G中的位置
  • 3、求首个邻接点操作
    • 形式
      • FirstdjVex（G，V）
    • 条件
      • 图G已经存在，V是G中某个顶点
    • 结果
      • 在图G中求顶点V的第一个邻接点
        • ①若图中没有v这个顶点则返回-1
        • ②若v没有邻接点则返回-1
  • 4、求下一个邻接点操作
    • 形式
      • NextdjVex（G，V，W）
    • 条件
      • 图G已经存在，V是G中某个顶点，w是v的邻接点
    • 结果
      • 求顶点V在W之后的下一个邻接点
        • 若w是v最后一个邻接点则返回-1
  • 5、深度优先遍历操作
    • 形式
      • DFSTraverse（G）
    • 条件
      • 图G已经存在
    • 结果
      • 按深度优先策略访问G中所有的顶点
  • 6、广度优先遍历操作
    • 形式
      • BFSTraverse（G）
    • 条件
      • 图G已经存在
    • 结果
      • 按广度优先策略访问G中所有的顶点
• 基本概念
  • 1、图
    • 概念
      • ①图是图型结构的简称。②图是一种非线性数据结构。③在图中任意两个数据元素都可以相关。④与其他数据结构一样，图也是由数据对象和数据关系两部分构成。图通常记作G=（V，E）或G=（V，R）
        • 图：G（graph）
          • 图不能是空图
        • 顶点：V（vertex））
          • 概念
            • V是构成图的顶点的集合，简称顶点集。
          • 绝对值含义
            • ｜V｜表示图G中顶点的个数。
          • 是否可为空集
            • V是非空集，即至少有一个顶点。
        • 边：E（edge） 关系：R（relationship）
          • 概念
            • R描述了v中顶点之间的关系，简称关系集。
          • 绝对值含义
            • ｜E｜表示图G中边的个数。
          • 是否可为空集
            • E可以为空集，即可以一条边也没有。但是一条边的两头必须有顶点。
    • 分类
      • 1、无向图和边
        • 概念
          • 如果R是对称的，即如果有<v，w>∈R，则必然有<w，v>∈R，则称（v，w）是顶点v与顶点w之间的一条边。
        • 关系
          • （v，w）（v和w叫顶点，没有终点起点之分）
          • （w，v）（v和w叫顶点，没有终点起点之分）
        • 表示
      • 2、有向图和弧
        • 概念
          • 若<v，w>，则称<v，w>是顶点v到顶点w的一条弧。
        • 关系
          • v是顶点，也叫起点／弧尾。
          • w是顶点，称为终点／弧头。
        • 表示
  • 2、完全图
    • 概念
      • 图中某顶点除了和自身没有关系，和其他顶点都有关系，这样的图叫完全图。
      • 邻接矩阵中，主对角线上的元素全是零，其余元素全是一，这样的图是完全图。
    • 分类
      • ①无向完全图（也叫完全图）
        • 有n个顶点。
        • 有n（n-1）／2条边。
      • ②有向完全图
        • 有n个顶点。
        • 有n（n-1）条弧。
  • 3、权和网
    • 权（边／弧上的数字）
      • 在有些应用中，需要为图的边或弧附设一个有特定意义的实数，该实数称为边或弧的权
    • 网（带权的图）
      • 概念
        • 带权的图称为网。
      • 分类
        • 有向网
        • 无向网
  • 4、子图
    • 概念
      • 子图指的是原图的一部分，需要注意的是：要满足一条边的两头必须有顶点。
    • 分类
      • 有向子图
      • 无向子图
  • 5、邻接点
    • 无向图
      • 概念
        • 对于无向图G＝（V，E），若边（v，w）∈E，则v与w互为邻接点，并称边（v，w）与顶点v和w相关联。
      • 关系
        • v的邻接点是w
        • w的邻接点是v
        • 边（v，w）与顶点v和w相关联
      • 表示
    • 有向图
      • 概念
        • 对于有向图G＝（V，A），若弧<v，w>∈A，则称顶点v邻接到顶点w或顶点w邻接自顶点v，并称弧<v，w>与顶点v和w相关联。
      • 关系
        • v邻接到w
        • w邻接自v
        • 弧<v，w>与顶点v和w相关联
      • 表示
  • 6、顶点的度（degree）
    • 无向图中某顶点v
      • 计法
        • 与v相关联的边的数目称为顶点v的度，记作TD（v）［T→total］
      • 特点
        • 无向图中全部顶点的度的和等于边数的二倍。（总度数＝边数×2）
    • 有向图中某顶点v
      • 计法
        • 以v为终点的弧的数目称为顶点v的入度，记作ID（v）［I→in］
        • 以v为起点的弧的数目称为顶点v的出度，记作OD（v）［O→out］
        • 顶点v的入度与出度之和称为顶点v的度，记住TD（v）［T→total］
      • 特点
        • 有向图中的全部顶点的入度之和＝出度之和＝弧数
  • 7、路径，简单路径，环路（回路）
    • 路径
      • 在图中
        • 从一个顶点到另一个顶点的路径指的是一个顶点序列。
          • 有向图
            • 在有向图中，顶点之间的路径也是有向的。
          • 无向图
            • 顶点v到顶点w的路径也是顶点w到顶点v的路径。
      • 在网中
        • 路径的长度是路径上边或弧的权值之和
    • 简单路径
      • 在路径的顶点序列中无重复顶点，称为简单路径。
      • 有n个顶点的连通图中的任意一条简单路径，其长度不可能超过n-1
    • 环路
      • 第一个顶点与最后一个顶点相同的路径称为环路。
  • 8、连通，连通图，连通分量（针对无向图）
    • 连通
      • 一个顶点v到另一个顶点w有路径存在，则称v和w是连通的。
    • 连通图
      • 图中任意两个顶点都是连通的，则此图叫做连通图
    • 连通分量
      • ①有些无向图本身虽然不是连通图，但它的某些子图是连通图。 ②我们把其中的（非连通图的）极大连通子图（包含尽可能多的顶点和边）称为连通分量。
        • 含有一个顶点的子图是连通分量
  • 9、强连通，强连通图 强连通分量（针对有向图）
    • 强连通
      • 一个顶点v到另一个顶点w有路径存在，而且顶点w到顶点v也有路径存在，则称v和w是强连通的。
    • 强连通图
      • 图中任意两个顶点都是强连通的，则称此图为强连通图。
    • 强连通分量
      • ①有些有向图本身虽然不是强连通图，但它的某些子图是强连通图 ②我们把其中的极大连通子图（包含尽可能多的顶点和边）称为强连通分量。
        • 含有一个顶点的子图是强连通分量
  • 10、生成树
    • 概念
      • 一个连通图的含有全部顶点的极小连通子图（边尽可能的少，但要保持连通）称为该图的生成树。
    • 特点
      • ①生成树必须是连通的。
      • ②生成树必须包含全部顶点。
      • ③生成树的边要尽可能的少。
      • ④生成树不唯一。
    • 性质
      • ①有n个顶点的连通图：生成树有n个顶点。
      • ②有n个顶点的连通图：生成树有且仅有n- 1条边。
        • （也就是说：n个顶点的无向图，如果边数少于n-1，则肯定不是连通图）
      • ③有n个顶点的图：有n颗生成树。
      • ④生成树上不会有环路。
      • ⑤在生成树上再添加一条边就会构成环路。
      • ⑥在生成树上减少一条边，此图就连通了。
• 图的存储结构（考大题）
  • 1、邻接矩阵法。
    • 定义
      • vexs与arcs中的顶点顺序要一致
      • 顶点的存储
        • 用一个一维数组vexs来存储顶点信息。
          • 一维数组
            • ①竖着写的数组。 ②没有下标，不用下标。
      • 边／弧的存储
        • 用一个二维数组arcs来存储邻接矩阵。
          • 二维数组 邻接矩阵
            • ①邻接矩阵是一个n阶方阵。 ②一个n行n列的二维数组。 ③以行序为主。
    • 表示对象特点
      • 图
        • 无向图
          • （1）边：邻接矩阵中0表示无边，1表示有边。
          • （2）点：第i行元素／第j列元素的和就是顶点Vi的度TD（Vi）
          • （3）1无向图的邻接矩阵是对称矩阵。 （3）2但对称矩阵可能是无向图，也可能是有向图（但这个有向不一定是完全有向图）
        • 有向图
          • （1）弧：邻接矩阵中0表示无弧，1表示有弧。
          • （2）点：第i行元素的和就是顶点Vi的出度OD（Vi） （2）点：第i列元素的和就是顶点Vi的入度ID（Vi）
          • （3）1有向图的邻接矩阵不一定是对称矩阵。完全有向图的邻接矩阵一定是对称矩阵。 （3）2但是对称矩阵可能无向，可能有向，（但这个有向不一定是完全有向图）
      • 网
        • 有向网
          • （1）邻接矩阵∞表示无弧，权值表示有弧。
        • 无向网
          • （1）邻接矩阵中∞表示无边，权值表示有边。
    • 性质
      • ①邻接矩阵表示法唯一。（顶点的位置确定以后，其相关联的边和邻接点都有了明确的顺序。）
      • ②邻接矩阵表示法适合稠密图（边比较多）
      • ③计算度／出度／入度必须遍历对应的行或列。
      • ④找相邻的边必须遍历对应的行或列。
    • 空间复杂度
    • 优缺点
      • 优点
        • ①邻接矩阵表示法直观，清楚，简单，好理解。 ②邻接矩阵表示法比较容易找到一个顶点的所有邻接点。 ③邻接矩阵表示法比较容易找到一个顶点的入度和出度。 ④邻接矩阵表示法比较容易检查一对顶点之间是否有边／有弧。
      • 缺点
        • ①邻接矩阵表示法在存储稀疏图时比较浪费空间。 ②删除和增加某个顶点的邻接点不方便。
  • 2、邻接表法。
    • 定义
      • 类似于树的孩子表示法
      • 顶点的存储
        • 用一个一维数组来存储顶点的信息。
          • 一维数组
            • ①竖着写的数组。 ②下标从零开始标注顶点的一个位置。 ③图中有n个顶点，则头结点数组的大小为n。
      • 边／弧的存储
        • ①与每个顶点Vi相关联的边／弧用一个单链表来存储。 ②并且把每个单链表的头指针存放在数组中对应存储Vi顶点的后面位置。
          • 单链表
            • 结点个数
              • ①一个顶点有几条相关联的边／弧，其对应的单链表就有几个结点。
            • 结点的域
              • 数据域
                • 某个顶点对应的单链表中某个结点的数据域：存放的是该顶点的邻接点在数组中的下标。
              • 指针域
                • 某个顶点对应的单链表中某个结点的指针域：存放的是该顶点的邻接顶点的指针。
            • 空
              • 空表
                • 一个顶点没有与之相关联的边，则这个顶点的单链表为空表。
              • 空指针
                • 某顶点的单链表中，某个顶点的下一个没有邻接点的话，指针域为空。
    • 表示对象特点
      • 无向图
        • 度
          • 第i个链表中结点的个数就是顶点VI的度。TD（Vi）
        • 顶点和边
          • 无向图中顶点数＝邻接表的数组中顶点数。
          • 邻接表中所有单链表的结点的总个数＝无向图中边的2倍
      • 有向图
        • 入度和出度
          • 邻接表
            • 第i个链表中结点的个数就就是顶点Vi的出度OD（Vi）
          • 逆邻接表
            • 第i个链表中结点的个数就就是顶点Vi的入度ID（Vi）
        • 顶点和弧
          • 有向图中顶点数＝邻接表的数组中顶点数。
          • 邻接表中所有单链表的结点的总个数＝有向图中总弧数
    • 性质
      • ①邻接表表示法不唯一。（因为边与边之间没有先后顺序，所以一个顶点的单链表中的结点可以有不同的次序）
      • ②邻接矩阵表示法适合稀疏图（点多边少）
      • ③计算有向图的度和入度不方便，需要画出逆邻接表。
      • ④寻找有向图的入边不方便，寻找其余的比较方便。
    • 空间复杂度
      • 无向图
      • 有向图
    • 优缺点
      • 优点
        • ①邻接表表示法比较容易找到一个顶点的所有邻接点。 ③邻接表表示法比较容易找到一个顶点的出度。 ④邻接表表示法在描述稀疏图时比较节约空间。
      • 缺点
        • ①邻接表表示法不方便找到一个顶点的入度。 ②邻接表表示法不方便检查任意一对顶点之间是否有边。
  • 3、十字链表法。
  • 4、邻接多重表法。
• 图的遍历（考大题）
  • 概念
    • 图的遍历就是从图的任意某一顶点出发，按照一定的路径访问图中其他顶点，并且每个顶点只被访问一次。
  • 措施
    • 设置标志数组visited
      • 操作：当某个顶点被访问时，将标志数组中元素的初值由0至1。
      • 作用：记录某一顶点是否被访问，避免一个顶点被多次访问。
  • 方法
    • 广度优先搜索遍历（BFS）
      • 类似于树的层序遍历，借助队列
      • 考试题型
        • ①广度优先遍历序列
        • ②广度优先生成树
      • 做题步骤
        • 针对：（有向／无向）连通图的邻接矩阵／邻接表
          • 生成树形态
            • 一棵树
          • 生成树点和边
            • n个顶点的图→广度优先生成树有n个顶点。
            • n个顶点的图→广度优先生成树有n-1条边。
          • 写出遍历序列步骤
            • （1）（摆顶点）将所有的顶点摆在同一行上。
            • （2）（按层邻接点，画树划点）从任意顶点按层从上到下从左往右访问点的邻接点并画出生成树，每经过一个将第一行摆出的顶点划掉一个。
            • （3）（层序遍历树）按照层序遍历从上到下从左往右的规则遍历生成树得到遍历序列。
        • 针对：（有向／无向）非连通图的邻接矩阵／邻接表
          • 生成树形态
            • 森林
          • 生成树点和边
            • n个顶点的图→广度优先生成树有n个顶点。
            • n个顶点的图→广度优先生成树有n-1条边。
          • 写出遍历序列步骤
            • （1）（摆顶点）将所有的顶点摆在同一行上。
            • （2）（按层访点，画树划点）①从任意顶点按层从上到下从左往右访问点的邻接点。②并画出生成树③每经过一个点将第一行摆出的顶点划掉一个。
            • （3）（层序遍历树）按照层序遍历从上到下从左往右的规则遍历生成树得到遍历序列。
            • （4）从未被访问的顶点中选取一个顶点作为出发点，重新开始前三步，直到图中所有的顶点都被访问最后得到了BFS这样一个非连通图的顶点访问序列。
        • 针对：给了边集或图
          • 注意：遍历的顺序一般是abcdefg，1234567，但是这个顺序不是固定的
      • 时间复杂度
        • 邻接矩阵
        • 邻接表
    • 深度优先搜索遍历（DFS）
      • 类似于树的先序遍历，借助栈
      • 考试题型
        • ①深度优先遍历序列
        • ②深度优先生成树
      • 做题步骤
        • （1）（摆顶点）将所有的顶点摆在同一行上。
        • （2）（一站到底，画树划点）①从任意顶点开始正向访问其邻接点，每访问一个邻接点，则一站到底尽最大可能访问完这个邻接点的邻接点。②并且伴随着要画出相应的生成树。③每访问一个顶点则在第一行摆出的顶点中划掉这个顶点。
        • （3）（倒着复盘完善树）尽最大可能从正方向访问完邻接点以后，倒着复盘，看还有没有没被访问到的顶点，需要再次访问一下。
        • （4）（先序遍历树）按照先序遍历根左右的规则遍历生成树得到遍历序列。
      • 时间复杂度
        • 邻接矩阵
        • 邻接表
• 最小（考大题）
  • 最小生成树
    • 概念
      • 边的权值之和最小（不是边最少）的生成树叫做最小生成树。
    • 特点
      • 最小生成树不唯一。
        • 如果一个连通图中每个边上权值均不同，则得到的最小生成树唯一。
    • 求最小生成树的算法（大题必须写过程）
      • 普里姆（Prim）算法
        • 时间复杂度
        • 注意
          • 适合边稠密图
          • 与网中边数无关
        • 操作步骤
          • ①（任意点开始）从任意顶点开始构建生成树。
          • ②（纳小点）（在连通的基础上纳）每次将代价最小的新顶点纳入生成树。
          • ③（点全纳入为止）直到所有顶点都纳入为止。
      • 克鲁斯卡尔（Kruskal）算法
        • 时间复杂度
        • 注意
          • 适合边稀疏图
          • 与网中边数有关
        • 操作步骤
          • ①（选小边）每次选择一条权值最小的边。
          • ②（两头通）使这条边的两头连通（原本已连通的不选）。
          • ③（点全连通为止）直到所有的结点都连通为止。
  • 最短路径
    • 概念
      • 路径上边或弧的权值之和最短的路径。
    • 分类
      • ①单源最短路径⭐️（写完整过程，注意s集的完整）
        • 概念
          • 求从某个顶点（源点）到图中其他各顶点的最短路径。（在对问题求解时，总是做出在当前看来最好的选择。）
        • 别名
          • 迪杰斯特拉（dijkstra）算法／贪心算法
        • 步骤
          • ①（每轮找最短）每一轮都会确定一条v0到某个顶点的最短路径。
          • ②（确定最短则点加入S）如果v0到某顶点的最短路径已经确定下来了，则把确定好的这个顶点加入集合s中。
          • ③（更正／保留最短）下一轮则按照上一轮中加入s的顶点为起点找到v0到某个顶点的最短。
            • （1）有更短则更正。 （2）有更长则保留原路径。 （3）没有路径则保留原路径。
          • ④直到v0到所有顶点的最短路径都确定下来则结束。
        • 图示
      • ②每一对顶点间的最短路径（了解，不考）
        • 弗洛伊德算法（floyd）
• 拓扑排序（考大题）
  • 概念
    • 有向无环图（DAG）
      • 无环路的有向图
    • AOV网（顶点活动网）
      • 顶点
        • 有向图的顶点表示活动
      • 弧
        • 有像图的弧表示活动之间的时间先后次序。
    • 拓扑排序
      • ①拓扑排序一定是有向无环图。 ②拓扑排序就是将AOV网中的顶点按照它们之间的优先关系排列成一个线性序列，该序列称为拓扑有序序列。 ③拓扑排序，简单来说就是找到做事的先后顺序。
  • 步骤
    • 1、（选入度0输出）在有向图中选取一个入度为零（没有前驱）的顶点输出。
    • 2、（删点删边）在图中删除该顶点和所有以它为起点的有向边。
    • 3、（全点输出止／出现环止）重复12，直到全部顶点均已输出或直到图中剩余部分无入度为零的顶点为止（此时说明有向图中存在环）。
  • 性质
    • （1）、一个有向图的拓扑有序序列不唯一。
    • （2）、一个表示实际问题的AOV网中不应该有环。
    • （3）、可用拓扑排序来判断有向图中是否存在环。