导图社区 《数据结构》第六章-图
《数据结构》第六章-图，这张思维导图讲所有涉及到的内容做了整理，无论是预习还是复习都可以用。
《操作系统》第五章-输入输出（IO）管理学习笔记，包括I/O管理概述、设备独立性软件以及磁盘和固态硬盘三部分内容。
计算机操作系统文件管理思维导图，包括文件和文件系统、文件的逻辑结构、文件目录三部分内容，需要的自取~
计算机组成 第五章-中央处理器学习笔记，包括CPU的功能和基本结构、指令执行过程、数据通路的功能和基本结构、多处理器的基本概念等等。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
图

图的基本概念
图的定义
G=(V,E)
顶点集V(G)：表示图G中顶点的有限非空集
边集E(G)：表示图G中顶点之间的关系（边）集合
有向图
无向图
简单图、多重图
不存在重复边
不存在顶点到自身的边
完全图（简单完全图）
无向图：任意两个顶点间都存在边，|E|=n(n-1)/2
有向图：任意两个顶点间存在方向相反的两条弧，|E|=n(n-1)
子图
设G=(V,E),G'=(V',E')，若V'、E'是V、E的子集，则G'是G的子图
若V(G)=V'(G')，则G'是G的生成子图
连通、连通图和连通分量
 答：要使任意含7个顶点的图连通，可先使6个顶点完全连通，即含有n*（n-1）/2=15条边。 此时，再引入一条边连接第七个结点，则满足任意情况下都连通的条件，故答案为16
连通：在无向图中，若从顶点v到w有路径存在，则称v和w是连通的；若图G中任意两点都是连通的，则称G为连通图
连通分量：无向图中的极大连通子图（相对于有多个连通分量的无向图来说）
强连通图、强连通分量
强连通：在有向图中，若顶点v和w之间，v→w和w→v间都有路径，则称v和w是强连通的
一个强连通分量中的每对顶点都互相可达
生成树、生成森林
生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图（若图的顶点数为n，则生成树含n-1条边）
注意：区分极大连通子图和极小连通子图。极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边（故连通图的极大连通子图就是它本身，非连通图可以有多个连通分量，仅最大那个是极大连通子图）；极小连通子图是既要保持图连通又要使得边数最少的子图
砍去生成树的一条边，会使其变为非连通图
增加一条边，会形成图中的一条回路
生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林
顶点的度、入度和出度
顶点v的度是指依附于顶点v的边的条数，记为TD(b)
无向图的全部顶点的度之和=边数*2
顶点v的度分为入度和出度
入度是以v为终点的有向边数目，记为ID(v)
出度是以顶点v为起点的有向边数目，记为OD(v)
入度之和=出度之和=边数
边的权和网
稠密图、稀疏图
路径、路径长度和回路
若一个图有n个顶点，且边数>n-1，则此图一定有环（回路）
简单路径、简单回路
中间顶点不重复的路径/回路
距离
有向树
一个顶点的入度为0，其余顶点入度均为1的有向图
图的存储及基本操作
邻接矩阵法
注意: ①在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。 ②邻接矩阵表示法的空间复杂度为O(n^2),其中n为图的项点数 ③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
用一个一维数组存储图中顶点的信息，用一个二维数组（邻接矩阵）存储图中边的信息
带权图
特点
①无向图的邻接矩阵一定是一个对称矩阵(并且唯一 )。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
②对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是顶点 i的度TD(v).。
③对于有向图，邻接矩阵的第i行非零元素(或非∞元素)的个数正好是顶点i的出度OD(v)；第i列非零元素(或非∞元素)的个数正好是顶点i的入度ID(v)。
④用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边,则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
⑤稠密图适合使用邻接矩阵的存储表示。
⑥设图G的邻接矩阵为A, A"的元素A"[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
邻接表法
为每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于vi的边，该链表称为vi的边表（对于有向图称为出边表）
十字链表
有向图的一种链式存储结构，对应图中的每条弧有个弧结点，对应每个顶点有一个顶点结点
弧结点
尾域（tailvex）：指示弧尾顶点在图中的位置
头域（headvex）：指示弧头顶点在途中的位置
链域（hlink）：指向弧头相同的下一条弧
链域（tlink）：指向弧尾相同的下一条弧
info域：指向弧的相关信息
顶点结点
data域：存放顶点相关的数据信息，如顶点名称
firstin：指向以该顶点为弧头的第一个弧结点
firstout：指向以该顶点为弧尾的第一个弧结点
在十字链表中，既容易找到Vi为尾的弧，又容易找到Vi为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的， 但一个十字链表表示确定一个图。
适用于存储稀疏矩阵（可视作邻接矩阵表示的图）
邻接多重表
在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边时，需要分别在两个顶点的边表中遍历，效率较低，因此出现邻接多重表
无向图的一种链式存储结构
边结点
其中，mark为标志域，可用以标记该条边是否被搜索过；ivex 和jvex为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点ivex的边；jlink 指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。
其中，data域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边
图的基本操作
图的遍历
广度优先搜索
基本思想
首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1, w2,……, wi，然后依次访问w1, w2,……, wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现代码
性能分析
空间复杂度：O(|V|)
时间复杂度
邻接表存储：每个顶点均需搜索一次；在搜索任意顶点的邻接点时，每条边至少访问一次
O(|V|+|E|)
邻接矩阵存储：查找每个顶点所需的为O(|V|)
O(|V^2|)
BFS算法求解单源最短路径问题
广度优先生成树
一给定图的邻接矩阵存储表示是唯一的， 故其广度优先生成树（BFS序列）也是唯一的， 但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。对于DFS，同理
深度优先搜索
首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点 .....重复上述过程。当不能再继续 向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
深度优先的生成树和生成森林
图的遍历与图的连通性
图的BFS和DFS算法可用来判断图的连通性
对无向图，对某节点的BFS()或DFS()可得到其连通分量；
对有向图，一次BFS()或DFS()可以得到强连通分量，但不能判断非强连通分量
DFS算法可以判断图中是否存在回路
图的应用
 
最小生成树
定义：带权连通无向图G的所有生成树中各边权值之和最小的生成树；最小生成树不一定唯一，但权值和唯一
Prim算法
Prim算法得到的最小生成树可能不唯一
每次选择距离现有顶点集最近的顶点加入集合，至顶点集满为止
选取的顶点应在现有顶点集外
算法过程
时间复杂度：O(|V|^2)
与|E|无关，故适合用于求解边稠密图的最小生成树
Kruskal算法
按权值递增的次序选择合适的边来构造最小生成树
若该边的两端顶点已经连通（即加入该边后形成回路），则舍弃该边
时间复杂度：O(|E|log|E|)
利用堆来存放边的集合，每次选边只需O(log|E|)的时间
采用并查集来描述T
Kruskal算法适合于边稀疏而顶点较多的图
最短路径
Dijkstra算法求单源最短路径问题
从初始点开始，每次选取距离当前点集最近的顶点加入点集
每次加入新结点，更新外部结点距顶点集距离以及最近结点位置
1)初始化: 集合S初始为{0}, dist [ ]的初始值dist[i]=arcs [0][i],i=1,2,…,n-1.2） （arcs[i][j]为邻接矩阵元素，表示有向边<i,j>的权值）
2)从顶点集合V-S中选出 vj，满足dist[j]=Min{dist[i] | vi∈V-S}，v,就是当前求得的一条从v0出发的最短路径的终点，令S=S∪{j}
3)修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度: 若dist[j]+arcs[j][k]< dist[k]，则更新dist[k]=dist[j]+ares[j][k]
4) 重复2)~3）操作共n-1次，直到所有的顶点都包含在S中。
性质
基于贪心策略
时间复杂度: O(|V|^2)
不适用于带有负权值的图
也可以用单源最短路径算法求解各顶点间的最短路径问题，对每个顶点调用Dijkstra算法，时间复杂度为O(|V|^3)
Floyd算法求各顶点间最短路径问题
从邻接矩阵开始，循环0~n-1轮，第k轮时将vk结点纳入考虑，求结点i，j间最短路径，且中间结果的序号不大于k
时间复杂度：O(|V|^3)
适用于带负权值边的图和带权无向图，但不允许有包含带负权值边组成的回路
有向无环图描述表达式
有向无环图可用于描述含有公共子式的表达式；相比起二叉树，可实现对公共子式的共享，从而节省存储空间
拓扑排序
AOV网
若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi, Vj>, 表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为 AOV网。在AOV网中，活动Vi是活动Vj的直接前驱，活动Vj是活动Vi的直接后继，这种前驱和后继关系具有传递性，且任何活动Vi不能以它自己作为自己的前驱或后继。
AOV网和拓扑排序
定义
拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个 AOV网都有一个或多个拓扑排序序列。
若图的邻接矩阵为三角型，即图中无环，则存在拓扑排序，但不一定唯一
对AOV网进行拓扑排序的算法
利用深度优先遍历算法也可以实现拓扑排序
①从AOV网中选择一个没有前驱的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
邻接表：O(|V|+|E|)
邻接：O(|V|+|E|)
逆拓扑排序
①从AOV 网中选择一个没有后继（出度为0）的顶点并输出。
②从网中删除该顶点和所有以它为终点的有向边。
③重复①和②直到当前的AOV网为空。
AOE网和关键路径
AOE网络
类似于AOV网，但AOE中的边有权值，以顶点表示事件，以有向边表示活动，边的权值表示完成活动的开销
只有在某顶点代表的事件发生后，从该顶点出发的各有向边所代表活动才能开始
只有在进入某顶点的各有向边代表的活动都完成后，该顶点代表的事件才能开始
关键路径
AOE网中的活动可以并行进行，把从源点（唯一入度为0的顶点）到汇点（唯一出度为0的顶点）的最长路径称为关键路径，其上的活动称为关键活动，它决定了工程完成的最短时间
关键路径可能有多条，只有同时加快所有关键路径上的的活动才能缩短工期；也可能存在一种称为“桥”的特殊关键活动，它位于所有关键路径上，可以加快周期
参量
事件vk的最早发生时间ve(k)
指从源点v1到顶点vk的最长路径长度，决定了从vk开始的活动能够开工的最早时间
递推式
ve(源点)=0
ve(k)=Max{ve(j)+Weight(vj,vk)}，vk为vj的任意后继
取max是因为，某顶点的事件想要开始，必须保证其所有入边的活动都已经完成
事件vk的最迟发生时间v(k)
指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
vl(汇点)=ve(汇点)
vl(k)=Min{vl(j)-Weight(vk,vj)}，vk为vj的任意前驱
活动ai的最早开始时间e(i)
指该活动弧的的起点所表示的事件的最早发生时间，即e(i)=ve(k)
活动ai的最迟开始时间l(i)
指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差，即l(i)=vl(i)-Weight(vk,vj)
一个活动ai的最迟开始时间和最早开始时间的差额d(i)=l(i)-e(i)
指该活动完成的时间余量，可以拖延的时间
求解算法
1)从源点出发，令ve(源点)=0，按拓扑有序求其余顶点的最早发生时间ve()
2)从汇点出发，令vl(汇点)=ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl()
3)根据各顶点的ve()值求所有弧的最早开始时间e()
4)根据各顶点的ve()值求所有弧的最迟开始时间l()
5)求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。
求解过程
