[TOC]

第六章图

线性：线性表 栈 队列

数组： 广义表（11）

树结构：树，二叉树 （1多）

图结构 ：图（多对多）

图

由V和E 组成，记G=(V,E)

V 是顶点有穷非空集，E是V中顶点边的有穷集合

V 是顶点结合 E 是边的集合

有向图 ：

G，若边集E是有向的

无向图

G 若边集E是无向的

<img src="https://i.loli.net/2020/05/22/U8fZmCybDzo7O9G.png" alt="image-20200423110450381" style="zoom:50%;" />

定义

子图：V 点 E 边 V'包含包含于V且 E'包含于E

<img src="https://i.loli.net/2020/05/22/eUE24kXj9vOTWcd.png" alt="image-20200423112654597" style="zoom:50%;" />

无向完全图

有n个顶点 n(n-1)/2 条边 1+2+3+..+n-1 边

有向完全图

n个顶点，n（n-1）个边 来回的 弧

稀疏图

E< nlog_2_n

反之

稠密图

权和网

权：每条边或弧可以标具有含义的数值， 数值表示权

网：带权的图就是网

邻接点：

• 对于无向图存在(V，V') 属于E ,V和V'位邻接点

入度和出度

入度：

• 顶点V 为头的弧度的数目

出度：

• 顶点V为尾部的弧度的数目

有向图的度：

• 入度+出度

路径和路径长度

• （A,C）路径长度为1

• （A,C,B） 路径长度为2

回路或环

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

简单路径

• 路径中序列中顶点没有重复出现

简单回路：

• 除第一个顶点和最后一个顶点重复外没有重复出现

连通

• 在无向图中，从顶点V到V'有路径，它是连通的

连通图

• 图中任意两个顶点是连通的，称为连通图

连通分量

• 无向图中极大的连通子图

强连通图

• 在有向图中，每一对顶点却存在路径，称为强连通图。

强连通分量

• 在有向图中的极大连通子图

连通图生成树

一个极小的连通子图，它包含了途中所有的顶点，只有构成树的n-1 条边，这样的连通子图称为连通图生成树。

用最少边将其连接（n-1）

有向树和生成森林

有一个顶点的入度为0，其余顶点入度为1的有向图称为有向树

若干个有向树组成-生成森林

图的存储结构

顺序存储

• 邻接矩阵

[有向图邻接矩阵]<img src="https://i.loli.net/2020/05/22/DWmfKeMhZpc4glX.png" alt="image-20200423153107545" style="zoom:50%;" /> 行出度 列入度

[无向图邻接矩阵]

[网邻接矩阵] 数据填邻接权值，或者无穷oo

优点

1. 易于判断顶点和顶点之间是否为边和弧

2. 易于计算顶点的度（行或者列 有几个1 度就为几）

缺点

1. 不便于增加行或删除顶点
2. 统计边数不容易O(n^2)
3. 空间复杂度高

• 链式存储

邻接表

分为 表头结点表 和边表

<img src="https://i.loli.net/2020/05/22/HI8WU2c17vaE9YR.png" alt="image-20200423163500549" style="zoom:44%;" />

逆邻接表 是本来计算出度，逆邻接表计算入度

邻接表 可以求出度 逆邻接表可以求入度

优点

1. 便于增加和删除结点
2. 便于统计边的数目 O(n+e)
3. 空间效率高

缺点

1. 不容易判断顶点直接是否有边
2. 不容易计算结点的度

链表

邻接多重表

图的遍历

深度优先： （图遍历序列不唯一）

1. 从图中某个顶点V 出发，访问V
2. 找出刚访问过顶点的第一个未被访问的顶点（重复此步骤）
3. 直到找到没有被访问的邻接点
4. 返回前一个访问过的且仍有未被访问的邻接点
5. 重复2 3 步 。知道图中所有结点全部被访问

image-20200423182437291

图的应用

最小生成树

• 在一个连通网的所有生成树中，各边的代价之和和最小的那颗生成树，称为连通网的最小生成树。

普利姆算法求最小生成树

找最小的点

时间复杂度（O(n^2)）

适用于稠密网

p168

克鲁斯卡尔算法

• 选最小的边 不能有回路

时间复杂度O(e*log_2_e)

最短路径算法

迪杰斯特拉算法

• 从某个点到其余各顶点的最短路径
• 时间复杂度 O(n^2)
• 空间复杂度O(n^2)

<img src="https://i.loli.net/2020/05/22/KxunRPOohJaI87Y.png" alt="image-20200430102547804" style="zoom: 80%;" />

弗洛伊德算法

• 每一对顶点之间最短路径

• 时间复杂度（O(n^3)）

• 邻接矩阵求法

1. 先写出邻接矩阵
2. 一行一列 留下，填充里面数据 ，原数据比r+c 小 数据不变，否则变为r+c
3. 2行2列
4. 3行3列
5. 一次论退

<img src="https://i.loli.net/2020/05/22/GCEST8BVvQzD9Io.png" alt="image-20200430113208938" style="zoom:33%;" />

拓扑排序

DAG图：有向无环图

AOV网：用弧表示活动间的优先关系

通过AOV网拓扑排序出来，（送分题）

• 选没有前驱的（入度为0的顶点）
• 有环就没有拓扑排序

关键路径

AOE-网：表示边 表示活动的网，带权有向图（无环），顶点表示事件，弧表示活动

带权路径长度：一条路径各弧的权路径之和。

关键路径：就是要估算整个工程完成的最短时间。 从开始结点到最终结点带权路径长度最长的一条路径

1. 各项点时间最早发生时间（从前到后取最大）Ve(1)
2. 各顶点时间最迟发生时间，（从后往前取最小）Vl(1)
3. 活动的最早开始时间（就是各顶点最早发生的时间前一项）（e(a1)=Ve(0)）
4. 活动的最迟开始时间（从后到前计算差）（l(a8)=Vl(n)-m）
5. 关键活动 3题=4题 活动 关键路径 就是关键活动和到一块

<img src="https://i.loli.net/2020/05/22/bzBXqsaF8gUNQ7A.png" alt="image-20200430152633086" style="zoom: 80%;" />

<img src="https://i.loli.net/2020/05/22/hbEqU5ixTg2ky9f.png" alt="image-20200430152903822" style="zoom:33%;" />