图的基本概念
图的 定义
术语
有向图：
弧 ,其中 是弧尾， 是弧头.
极大强连通子图
如图：
其强连通分量有两个
不同于无向图，有向图不仅要求 到 有路径，还要求该路径可逆(即存在两个方向的路径)
显然 图6.3 中 没有路径指向 3 ，故 顶点3 独立为一个强连通分量
无向图：
表示一条连接 顶点 和 的边，无方向表示，
极大连通子图
看上面的 极大强连通子图的定义 反推。
生成树
后续会讲到一个图的最小生成树（MGT)的构造，这里需要理解其定义
生成树 作为一个树，其中的每个结点都是不重复的（图里的所有顶点）；此外根据树的定义，该生成树的边数 等于 .
官方定义: 连通图的生成树是一个包含所有顶点的 极小 连通子图(去掉任意一条边该图就不出连通的)
图的应用
最小生成树
城市基建铺设光缆
Prim
从任意一点开始 寻找到未知点的 最短路径 ，如果找到的顶点不在顶点集 则写入，并从新的 顶点集中的点 出发寻找到 下一个未知点 最短路径。
适合 边稠密 图
时间复杂度:
Kruskal
-
预处理： 先将有向图（利用邻接表存储）中所有 边 有序排列.
-
选取： 从小到大 依次选取，不成环 则纳入解，否则 排除.
-
结束条件： 选到 (点数量 - 1) 条边即停止.
适合 边稀疏 但 顶点较多 的图
时间复杂度:
适合什么图 看 时间复杂度 中的变量是谁
最短路径
Dijkstra
Floyd
拓扑排序 （本质就是 排序）
因为，在图中 每个顶点 代表的 活动 都有各自的路径可以走，有些甚至能够并行，不能够完全区分其中先后顺序，所以整了一个可以完成上述 排序 的算法；
总而言之，在每个活动开始时，需要保证其所有前驱活动都已完成，输出顺序看算法的结构，所以 拓扑排序的 结果 可能不唯一。
特点
拓扑排序 结果唯一 , 需满足每次寻找 入度为 0 的 顶点时，都恰好只有一个
AOV 网
有向无环图：通常描述的都是一个实际的工程，不能存在一个环是因为不能出现死循环。
DFS
bool visited {MVNUM};
void DFSTraverse(Graph G)
{
for v = 0; V < G.vexnum; ++ v)
visited[v] = false;
time = 0;
for(v = 0; v < G.vexnum; ++ v)
if(!visited[v]) DFS(G,v);
}
void DFS(Graph G, int v)
{
visited[v]=TRUE;
visit(v);
for(w=EirstNeighbar(G,v); w >= 0; w = NextNeighbar(G,V,w))
if (!visited[w]) DFS(G，w);
time = time + 1;
finishTime[v] = time;
}
常考点
- DFS 怎么做到拓扑排序
- 拓扑排序的 时间复杂度 (邻接表、邻接矩阵)
关键路径
AOE 图：只有 一个 源点 和 一个 汇点
求出 最短必要时间，即：求出源点到汇点的最长路径长度，因为该有向无环图中每一个活动都限制这下一个事项的发生，如果要在求出完成最后一个事项的时间必须求出所有活动中执行时间累加起来最长的路径也就是 最短必要时间。
注意: 这里的源点（始点）与 汇点（终点）有且仅有一个，但是关键路径可以有多条。
注意事项
余量计算：前一个事项开始时间 — 后一个事项开始时间 — 活动执行时间
疑难杂症：
存在回路 的充要条件
AOV AOE怎么利用邻接表 邻接矩阵 进行算法实现的
错题
