复习篇——数据结构之图
Some concepts
- 弧尾是起始点（箭头的开端），弧头是终结点（箭头的终端）
- 无向完全图：顶点与其他n-1个顶点都有边相连接的无项图「有n（n-1）/2条边」
- 有向完全图：每个顶点与其余n-1条顶点都有弧相连的有向图「有n（n-1）条边」
- 稀疏图：图的边数e<nlogn；稠密图：图的边数e>=nlogn
- 度：顶点v的度是指与顶点v相关联的数目；
- 入度：以顶点v为弧头的弧的数目；出度：以顶点v为弧尾的弧的数目
- 顶点的度=顶点的入度+顶点的出度；
- 顶点的度与边的关系：顶点的边=n个顶点累积的度除以2
- 权：每一条边都有与它相关的数（这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息）
- 网或赋权图：带权的图
- 路径的长度：路径上经过的弧或边的数目（有向图的路径也是有向的）
- 回路或环：该路径的第一个顶点与最后一个顶点是相同的
- 简单路径：路径顶点序列中顶点不重复出现
- 简单回路：除了第一个和最后一个顶点外，其余顶点均不重复出现的回路
- 连通图：对于图中任意两个顶点，它们都是连通的，则称其为连通图（若从顶点a到顶点b有路径相通，则称该顶点a与b是连通的）
-
连通分量：无向图中的极大连通子图
- 强连通图：强连通图针对的是有向图，对于任意一对顶点a、b，从a到b和从b到a都有路径
-
强连通分量：有向图的极大强连通子图
-
极小连通子图：含有图中的全部顶点，但只有足以连通n个点的n-1条边（即一个连通图的生成树）
- 生成树：一个连通图的生成树是指一个极小连通子图（n个顶点，n-1条边）；如果在生成树上再添加一条边，必定构成一个环（即回路）；一颗有n个顶点的生成树有且仅有n-1条边，如果它多于n-1条边，则一定有回路，小于n-1条边一定为非连通图；有n-1条边的图并非一定连通，不一定存在生成树
-
生成森林：各个连通分量的生成树集合为该非连通图的生成森林
- 生成树是对应连通图来说，而生成森林是对应非连通图来说的
- 最小生成树：在一个连通图中所有生成树中，各边的代价之和最小的那颗生成树称为该连通网的最小生成树
图的存储结构
-
邻接矩阵表示法（数组表示法，对称矩阵）
使用二维数组来表示，一个用于存储邻点信息，另一个用于存储图中顶点的关联 -
邻接表
-
十字链表
图的遍历
图的深度优先遍历
图的广度优先遍历
图的最小生成树（两种算法）
普利姆算法（从点开始）
克鲁斯卡尔算法（从边开始）
顶点表示活动的网（AOV网）
可以进行拓扑排序，用顶点表示活动，弧表示活动间的优先关系，下图的一个拓扑排序为C1,C2,C3,C4,C5,C8,C9,C7,C6（拓扑排序不是唯一的）
求有向无环图的拓扑排序的步骤（可以判断是否有回路）
①从有向图中选择一个无前驱的结点输出
②将此结点和以它为起点的边删除
③重复①、②，直到不存在无前驱的结点
④若此时输出的结点数小于有向图中的结点数。则说明有向图中存在回路；否则输出的顶点的顺序即为一个拓扑排序
边表示活动的网（AOE网）
关键路径：从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，将此路径称为关键路径
其他资料参考（很全）：https://blog.****.net/qq_38071429/article/details/80407544
最短路径
迪杰斯特拉算法
https://blog.****.net/bjweimengshu/article/details/89090053
弗洛伊德算法