图
图的基本概念
图G，顶点集V，边集E
|V|：顶点个数，图G的阶
|E|：边的条数
线性表可以是空表，树可以是空树，但图不可是空图
图的顶点集V一定非空，边集可以为空
有向图<v,w> v→w
无向图(v,w)
完全图
- 无向图
边数 [0,n(n-1)/2] - 无向完全图
n(n-1)/2 任意两个顶点都存在边 - 有向图
边数 [0,n(n-1)] - 有向完全图
n(n-1) 任意两个顶点之间都存在方向相反的两条弧
并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。
有向图的边集的子集和顶点集的子集可构成原有向图的子图 ×
连通：无向图中，顶点v到w有路径存在，则称vw连通
连通图：图中任意两个顶点都是连通的
极大连通子图（连通分量）：（不能再大）从一个顶点开始作为一个子图，逐个添加和这个子图有边相连的顶点，直到所有相连的顶点都被纳入图中。
极大：连通子图包含其所有的边
极小：既要保持图连通，又要使得边数最少
若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图
若一个图有n个顶点，并且边数大于n-1，则此图一定有环
强连通：有向图中，v到w和w到v都有路径
强连通图、强连通分量只是针对有向图而言的
无向图中讨论连通性，有向图考虑强连通性
王道做题心得
6.1.2
理论题
- 路径的定义：由顶点和相邻顶点序偶构成的边所形成的序列 。
- 若有向图中存在拓扑序列，则该图不存在回路。
- 无向图的连通分量是指无向图中的极大连通子图
一个连通图的生成树是一个极小连通子图，是无环的。
如果图本来就是不连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。（16题） - 有向完全图一定是强连通有向图
图的遍历就是从图中某一顶点出发访遍图中其余顶点 ×
图的遍历要求每个结点只能被访问一次，且若图非连通，则从某一顶点出发无法访问到其他全部顶点。
计算题
- 无向图含有7个顶点，保证在任何情况都是连通的，则需要的边数最少是（）
7=6+1 6个顶点构成一个完全无向图，再加上一条边，第七个顶点必然和此完全无向图构成一个连通图。
- 对于一个有n个顶点的图，若是连通无向图，其边数至少是_____
若是强连通有向图，其边数至少是_____
连通无向图——生成树 n-1
强连通有向图——有向环 n
- 有n个顶点的有向图中，每个顶点的度最大是_____
一般讨论的是简单图，不能自己指向自己，2*（n-1）
- 具有n个顶点的图是一个环，则它有__n__棵生成树
n个顶点构成的环有n条边，去掉其中任意一条便是一颗生成树。
- 若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有___棵树
设森林中有s棵树，再用n-1条边就能把所有的树连接成一棵树，此时，边数+1=顶点数，即e+(x-1)+1=n => x=n-e
图的存储及基本操作
邻接矩阵表示法
- 对称矩阵、唯一、实际存储时只用存储上（下）三角矩阵的元素
- 无向图：第i行（列）非零元素的个数正好是第i个顶点的度
- 有向图：第i行非零元素的个数是第i个顶点的出度；第i列非零元素的个数是第i个顶点的入度
- 适合存储稠密图
邻接表法
- 适合存储稀疏图
- 不唯一，各边结点的链接次序可以是任意的
- 无向图，所需存储空间为O(|V|+2|E|);
有向图，所需存储空间为O(|V|+|E|) - 邻接表很容易找到它所有的邻边，邻接矩阵容易确定给定的两个顶点之间是否有边
- 有向图邻接表，求给定顶点的出度只需计算其邻接表中的结点个数。
入度需要遍历全部的邻接表
十字链表
- 有向图的链式存储结构
- 弧结点（5个域）+顶点结点（3个域）
- 顶点结点之间是顺序存储的
- 十字链表表示法是不唯一的，但一个十字链表表示确定一个图
邻接多重表
- 是无向图的另一种链式存储结构
- 相对于邻接表的优势：邻接表求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率低
- 所有依附于同一顶点的边串联在同一链表中，每个边界点同时链接在两个链表中
- 对于无向图，邻接多重表和邻接表的区别在于：同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点
图的遍历
从图的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。
分层的查找过程，不是一个递归的算法，需要借助一个辅助队列Q
最坏情况下，空间复杂度为O(|V|)
采用邻接表：
每个顶点均需搜索一次，O(|V|)
搜索任一顶点的邻接点时，每条边至少访问一次，O(|E|)
总的时间复杂度：O(|V|+|E|)
采用邻接矩阵：
查找每个顶点的邻接点所需的时间为O(|V|)
总的时间复杂度是O(|V^2|)
- 广度优先生成树
给定图的邻接矩阵存储表示是唯一的，其广度优先生成树也是唯一的
而邻接表存储表示不唯一，故其广度优先生成树不唯一
深度优先搜索树DFS
对于同一个图，基于邻接矩阵的遍历得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS和BFS是不唯一的
判断有向图中是否有回路，可以利用DFS或者拓扑排序
是递归算法，需要借助递归动作栈，空间复杂度O(|V|)
采用邻接矩阵
查找每个结点的邻接点所需的时间O(|V|)
总的时间复杂度O(|V^2|)
采用邻接表
查找所有顶点的邻接点所需的时间为O(|E|)
访问顶点所需的时间为O(|V|)
总的时间复杂度O(|V|+|E|)
深度优先的生成树和生成森林
对连通图调用DFS才能产生深度优先生成树，否则产生的是深度优先生成森林
基于邻接表存储的深度优先生成树不是唯一的
图的连通性
对无向图：
若无向图是连通的，从任意结点出发，仅需一次遍历就能够访问图中的所有顶点；
若无向图是不连通的，从某一个顶点出发，一次遍历只能够访问到该顶点所在连通分量的所有顶点，而对于其他连通分量的顶点，则无法通过这次遍历访问
对有向图：
若从初始顶点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
图的应用
- 最小生成树
包含图的所有顶点，只含尽可能少的边。
砍掉一条边，会使生成树变成连通图；增加一条边，会形成图中的一条回路。
性质：
- 最小生成树不是唯一的。当带权连通无向图中的各边权值互不相等时，最小生成树唯一
- 最小生成树的边的权值之和总是唯一的
- 最小生成树的边数为顶点数减1
最小生成树算法
- prim（从顶点开始扩展最小生成树）
时间复杂度：O(|v^2|)
适合求解边稠密的图的最小生成树 - kruskal（按权值的递增次序选择合适的边构造）
时间复杂度O(|E|log|E|)
适合边稀疏而顶点较多的图
最短路径：带权路径最短的那条路径
性质：两点之间的最短路径也包含了路径上其他顶点间的最短路径
带权有向图的最短路径问题
- 单源最短路径：图中某一顶点到其他各顶点的最短路径，dijkstra
- 每对顶点间的最短路径：floyd
dijkstra
基于贪心策略
邻接表、邻接矩阵表示的时间复杂度都是O(|V^2|)
可以用单源最短路径算法求解每对顶点之间的最短路径问题
有向无环图描述表达式 DAG图
对相同子式共享，节省存储空间。
拓扑排序
AOV网：顶点表示活动
一个有向无环图顶点序列，当且仅当满足下列条件，有拓扑序列：
- 每个顶点出现且只出现一次
- 若顶点A在序列中排在顶点B前，则图中不存在顶点B到A的路径
每个AOV网都有一个或多个拓扑排序序列
- 时间复杂度：O(|V|+|E|) (输出顶点还要删除边)
使用深度优先遍历也可实现拓扑排序
- 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一
- 若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的
- 邻接矩阵是三角矩阵，则存在拓扑序列。存在拓扑序列的图，邻接矩阵不一定是三角矩阵。
关键路径
AOE网：顶点表示事件，边表示活动，边上的权值表示完成该活动所需时间。
AOV和AOE的异同：
相同：都是有向无环图
不同：他们的边和顶点所代表的含义不同，AOE网中的边有权值，AOV边无权值。
性质：
- 只在某顶点所表示的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
- 只有在进入某顶点的各有向边所代表的活动都结束时，该顶点所代表的事件才能发生
关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径
关键活动：关键路径上的活动
关键路径的长度：完成整个工程的最短时间就是关键路径的长度
- 关键路径上的所有活动都是关键活动，因此可以通过加快关键活动来缩短整个工程的工期。但不能任意缩短关键活动，可能会变成非关键活动
- 关键路径不唯一，只提高一条关键路径上的关键活动速度不能缩短整个工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
王道做题心得
6.4.6
无向连通图最小生成树必定存在；存在权值相同的多条边时，最小生成树可能是不唯一的
只要无向连通图中没有权值相同的边，则其最小生成树唯一
有权值相同的边，也可能唯一（图本身就是一棵树，最小生成树是他自己）
- 用prim和kruskal构造图的最小生成树，可能相同可能不同
无向连通图的最小生成树不一定唯一，所以用不同算法生成的最小生成树可能不同；但当最小生成树唯一时，不同算法生成的最小生成树一定相同
- 使用prim算法从不同顶点开始得到的最小生成树一定相同
n个顶点构成环，n-1条边权值相等，则从不同的顶点开始prim算法会得到n-1种不同的最小生成树
- 最短路径一定是简单路径
- dijkstra算法适合求解有回路的带权图的最短路径，也可以求任意两个顶点的最短路径，不适合求带负权值的最短路径问题
- floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。也适用于带权无向图，带权无向图可视为权值相同往返二重边的有向图
- 深度优先遍历、拓扑排序、求关键路径可以判断一个有向图是否有环
- 若一个有向图的顶点不能排在一个拓扑序列中，则可以判定该有向图：含有顶点数目大于1的强连通分量
不存在拓扑，则表示图中必定存在回路，该回路构成一个强连通分量
有向图存在环路，一定不存在拓扑
- 拓扑排序算法暂存入度为0的顶点，可以使用栈或者队列
若两个结点之间不存在祖先或子孙关系，则他们在拓扑序列中的关系是任意的，栈和队列都可以
- （错误）若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1 ×
- 若一个有向图具有有序的拓扑排序序列，则他的邻接矩阵必定为：三角
去掉拓扑，则填一般
|