保研复习数据结构-图（10）

一.图的定义和基本术语

1.什么是图？

图(Graph)是由顶点的有穷非空集合V(G)和顶点之间边的集合E(G)组成，通常表示为:G=(V,E)，其中，G表示图，V是图G中顶点的集合，E是图G中边的集合。

2.什么是完全图（Completed graph）？

对于有n个顶点的无向图，边e的数目为 0 ~ n(n-1)/2，对于无向完全图，共有n(n-1)/2条边。对于有向图，边的数目是0 ~ n(n-1)，有向完全图的边数为n(n-1)。有很少条边或弧的图称为稀疏图（Sparse graph），反之称为稠密图（Dense graph）。

3.什么是网（Network）？

带权的图，权是指边或弧上带有相应的数字。

4.什么是子图（Subgraph）？

图的顶点集的子集and图的边集的子集

5.一个图的所有顶点的度数的和的一半等于边数：

$e=\frac{1}{2}\Sigma ^n_{i=1}ID(v_i)$

6.什么是图中的回路或环（Cycle）？

第一个顶点和最后一个顶点相同的路径称为回路或者环。

7.什么是连通图（Connected Graph）？

如果对于图中任意两个顶点Vi和Vj都有路径，那么说明这个图是连通图。

8.什么是连通分量（Connected component）？

指的是无向图中的极大连通子图=子图and连通图

9.什么是强连通图？什么是强连通子图？

对于有向图中的连通图，和有向图中的连通分量。

10.什么是生成树（Spanning Tree）？

生成树是一个连通图的极小连通子图，它包含树所需的全部顶点。顶点数为n的生成树一定含有n-1条边。如果一个含有n个顶点的图的边数小于n-1，那么这个图一定是非连通图；如果边数大于n-1，那么一定包含环。

11.什么是生成森林？

对应于非连通图，是由多个生成树组成的包含图中所顶点的森林。

二.最小生成树（Minimum Cost Spanning Tree）

1.什么是最小生成树？

所有边代价和最小的生成树称为最小生成树

2.Prim算法和Kruskal算法利用的是最小生成树的什么性质？

MST性质：假设N=(V , { E })是一个连通网，如果U是顶点集V的一个非空子集，如果存在一条权重（代价）最小的边 $(u,v)$ 使得 $u \in U, v \in V-U$ ，那么必然存在一棵包含 $(u,v)$ 的最小生成树。

3.Prim算法是什么？

Prim算法基于贪心对于连通加权无向图来选择最小生成树的算法，每次选出一条距离已有最小生成树最短的边加入到集合中，最终实现最小生成树

具体流程：

用两个集合A{}和集合B{}分别表示找到的点集和未找到的点集。
对于元素a属于A，元素b属于B，选择一条最小的边（a，b）加入最小生成树
直到A=V，B为空

4.Kruskal算法是什么？

Prim算法是基于点，Kruskal算法是基于边。

先将边从小到大排列，从小到大添加不构成环路的边，由于要排序，所以复杂度为O(nlogn)

将边按照权重从小到大排列
枚举第一个边，加入MST里，判断是否成环
如果成环则跳过，否则确定这条边为MST里的
继续枚举下一条边，直到所有的边都枚举完

三.拓扑排序（Topological Sort）

1.什么是拓扑排序？

针对于有向无环图，只有有向无环图才存在拓扑排序。拓扑排序是针对有向无环图的拓扑序列，这个序列满足：（1）每个顶点出现且仅出现一次（2）如果存在一条从A到B的路径，那么A一定在B的前面

2.拓扑排序的过程？

选择一个没有前驱（入度为0）的顶点
删除这个顶点和所有以它为起点的边
重复操作12，直到整个图为空或者剩余结点，后一种状况说明图存在环路。

四.关键路径（Critical Path）

1.什么是关键路径？

关键路径是针对于AOE（Activity on edge）来说的，AOE中边表示活动，权重表示活动持续的时间，顶点表示事件。所有有最早开始时间和最晚开始时间相同的事件组成的路径为关键路径。

2.关键路径的求解步骤？

绘制项目网络图，标志个活动的持续时间和活动之间的逻辑关系。
计算每个活动的最早开始时间(ES)和最晚开始时间(LS)，以及最早完成时间(EF)和最晚完成时间(LF) 。
计算每个活动的浮动时间，即LS-ES或LF-EF。
找出浮动时间为零的活动，这些活动所构成的路径就是关键路径。

五.最短路径（Minimum Path）

1.迪杰斯特拉算法（单源最短路径）

从所有未访问的点中，找出当前距离最小的，设为u，并将其标记为已访问的。
调整u的所有边（若是有向图则为出边）连接的并且未被访问过的点：若weight[u->v] + dist[u] < dist[v], 则将dist[v]更新为dist[u]+weight[u->v]。
重复1和2步骤，直到所有点都被标记为已访问的，则dist[i]即s到i的最短距离。如果只想求从s到某一点的最短距离，那么当该点被标记为访问过之后可直接退出。
补充：如果除了最短距离之外还想求出具体的路径，只需建立一个pre数组，在步骤2后添加操作：pre[v] = u（前提是dist[v]被更新）。

2.弗洛伊德算法（多源最短路径）

弗洛伊德算法可以给出图中任意两个结点之间的最短路径，比迪杰斯特拉更一般。

Foyd算法的思想是将n个节点的网络表示为n行n列的矩阵，而矩阵中的元素(i,j)表示从节点i到节点j的距离 $d_{ij}$ ，如果两点直接没有边相连，则相应的元素就是无穷( $\infty$ ).

邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.
从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。
重复上述直到最后插点试探完成。