图

• 定义

  • Graph=(V,E)

    • V: 顶点(数据元素)的有穷非空集合

    • E: 边的有穷集合

  • 图属于逻辑结构

    • 多对多的关系

  • 类型

    • 无向图

      • 边集为无向边的集合

    • 有向图

      • 边集为有向边的集合

• 基本术语

  • 子图

    •  $V^{′} \subseteq V且 E^{′} \subseteq E$ $V^{′} \subseteq V且 E^{′} \subseteq E$  

  • 无向完全图和有向完全图

    • ​任意两个点都有一条边相连

    • ​有向完全图

      • ​ $n(n-1)$ 个边

    • ​无向完全图

      • ​ $n(n-1)/2$ 个边

  • 稀疏图和稠密图

    • ​稀疏图

      • ​边数量很少的图( $e<nlog x_{2} n$ )

    • ​稠密图

      • ​与稀疏图相反

  • 权和网

    • ​权

      • ​边上某种意义的数值

    • ​网

      • ​带权的图称为网

  • 邻接点

    • ​边(v,v′)∈E,则称顶点v和v′互为邻接点

    • ​边(v,v′)与顶点v和v′相关联

  • 度、入度和出度

    • ​度

      • ​与v相关联的边的数目

    • ​有向图顶点的度

      • ​出度

        • ​以v为头的弧数目

      • ​入度

        • ​以v为尾的弧数目

    • ​根据度算边数目

      • ​ $e = \frac{1}{2} {\displaystyle \sum_{i=1}^{n}{TD( v_{i} )} } (e是边数,n是顶点数,TD(v)是顶点对应的度)$ 

  • 路径和路径长度

  • 回路或环

    • ​第一个顶点和最后一个顶点相同

  • 简单路径、 简单回路或简单环

    • ​简单路径: 除路径起点和终点可以相同外，其余顶点均不相同的路径。

    • ​简单环: 起点和终点相同的简单路径

  • 连通、(强)连通图和(强)连通分量

    • ​在无（有）向图G=（V，{E}）中，若对任何两个顶点ⅴ、u都存在从v到u的路径，则称G是连通图（强连通图）

    • ​(强)连通分量: 指的是(有)无向图中的极大(强)连通子图

  • 有向树和生成森林

    • ​顶点入度为0,其余顶点的入度为1的有向图为有向树

    • ​一个有向树的生成森林由若干棵有向树组成

• 存储结构

  • ​顺序存储结构

    • 邻接矩阵

      • 邻接矩阵表示法

        • 定义:用一维数组记录顶点信息,一个二维数组记录邻接矩阵(表示顶点之间相邻关系)

        • ​邻接矩阵公式

          • ​图

            •  $A[i][j]= \begin{cases} 1 &\text{若 }<v_{i} , v_{j}>或(v_{i} , v_{j}) \in E \\ 0 &\text{ }反之 \end{cases}$ 

          • ​网

            • ​ $A[i][j]= \begin{cases} w_{i,j} &\text{若 }<v_{i} , v_{j}>或(v_{i} , v_{j}) \in E \\ \infty &\text{ }反之 \end{cases}$ 

        • 存储表示

          • 

      • 创建无向网 （O(n²)）

        • ​输入总顶点数和总边数

        • ​依次输入点的信息存入顶点表中。

        • ​初始化邻接矩阵，使每个权值初始化为极大值。

        • ​构造邻接矩阵。

      • 优缺点

        • 优点

          • ​便于判断两个顶点之间是否有边

          • ​便于计算各个顶点之间的度

            • ​无向图: 度为第i行元素之和

            • ​有向图:出度为第i行元素之和, 入度为第i列元素之和

        • 缺点

          • ​不便于增加和删除顶点

          • ​不便于统计边的数目,时间复杂度为 $O( n^{2} )$ 

          • ​空间复杂度高 有向图存储 $n^{2}$ 个单元,有向图对称,压缩需存储n(n-1)/2个单元,但空间复杂度都是 $O(n^{2})$ 

  • ​链式存储结构

    • 邻接表

      • 邻接表表示法

        • ​定义: 对每个顶点ⅵ建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；每个单链表有一个头结点（设为2个域），存vi信息；

        • 表头结点表

          • ​顺序结构存储

          • ​数据域

          • ​链域

        • 边表

          • ​邻接点域

          • ​数据域

          • ​链域

        • 存储表示

          • ​

      • 创建无向图（O(n+e)）

        • ​输入总顶点数和总边数。

        • ​依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL.

        • ​创建邻接表

      • 优缺点

        • 优点

          • ​便于增加和删除顶点

          • ​便于统计边的数目  $O(n+e)$ 

          • ​空间效率高  $O(n+e)$ 

            • ​无向图: ​n个顶点表结点,2e个边表结点

            • ​​有向图: n个顶点表结点,e个边表结点

        • 缺点

          • ​不易判断顶点之间是否有边 O(n)

          • ​不便于计算各个顶点的度

  • 邻接矩阵和邻接表的比较

    • ​联系 邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

    • ​区别

      • ​①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）.

        ②邻接矩阵的空间复杂度为 $O(n^{2} )$ 而邻接表的空间复杂度为O（n+e）

    • ​用途

      • ​邻接矩阵多用于稠密图；而邻接表多用于稀疏图

• 遍历

  • ​避免重复访问

    • ​设置辅助数组 visited[n]，用来标记每个被访问过的顶点。

  • 深度优先搜索 dfs

    • ​仿树的先序遍历过程。

    • 算法实现

      • 邻接矩阵表示法遍历 O(n²)

      • 邻接表表示法遍历 O(n + e)

    • 算法步骤

      • ​访问起始点v

      • ​若v的第1个邻接点没访问过，深度遍历此邻接点

      • ​若当前邻接点已访问过，再找v的第2个邻接点重新遍历。

  • 广度优先搜索 bfs

    • ​仿树的层次遍历

    • 算法实现

      • ​与dfs时间复杂度相同,两种不同仅仅在于访问顺序不同

    • 算法步骤

      • ​在访问了起始点ν之后，依次访问v的邻接点

      • ​然后再依次访问这些顶点中未被访问过的邻接点

      • ​直到所有顶点都被访问过为止。

• 应用

  • 最小生成树

    • ​各边代价之和最小的生成树成为该连通网的最小生成树

    • ​多数构造最小生成树算法利用MST性质

    • 普里姆算法 O(n²)

      • ​归并顶点，与边数无关，适于稠密网。

      • ​算法过程

        • ​从某顶点u0出发，选择与它关联的具有最小权值的边（u0，v），将其顶点加入到生成树的顶点集合U中

        • ​每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边（u，v），把它的顶点加入到U中

        • ​直到所有顶点都加入到生成树顶点集合U中为止

    • 克鲁斯卡尔算法  O(elog2e）

      • ​归并边，适于稀疏网。

      • ​算法过程

        • ​构造一个只有n个顶点，没有边的非连通图T每个顶点自成一个连通分量

        • ​在E中选最小权值的边，若该边的两个顶点落在不同的连通分量上，则加入T中；否则舍去，重新选择

        • ​重复下去，直到所有顶点在同一连通分量上为止。

  • 最短路径

    • 从某个源点到其余各顶点(迪杰斯特拉算法) O(n²)

    • 每一对顶点之间(弗洛伊德算法) O(n³)

  • 拓扑排序 O(n+e)

    • AOV—网

  • 关键路径 O(n+e)

    • AOE—网

  • *六度空间理论 O(n+e)