Graph.md

图

结构

图是由一个顶点集 V 和一个弧集 VR构成的数据结构 G = (V , VR )

无向图

网

弧或边带权的图分别称为网

术语

1. 完全图 ；n 个顶点有$n(n-1)/2$条边
2. 有向完全图 ：n 个顶点有$n(n-1)$条边
3. 稀疏图 ：$ e<nlogn$
4. 稠密图
5. 连通图 : 任意两个点都相通
6. 联通分量 ： 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量
7. 强连通图 ： 对有向图来说，若任意两个顶点之间都存在一条有向路径
8. 强连通分量：否则，其各个强连通子图称作它的强连通分量。
9. 弱连通图：对有向图来说，不考虑弧的方向时，若任意两个顶点之间都存在一条无向路径

存储

邻接矩阵
邻接表
十字链表

搜索策略

深搜
广搜

都需要 visited[]数组

生成树

最小生成树算法 ：prim && kruskal

最短路

dijkstra && floyed

拓扑排序

用顶点表示活动，用弧表示活动间优先关系的有向图称为AOV-网。

关键路径

概念 ： 从源点到汇点路径最长的路径
用顶点表示事件，弧表示活动，弧上权值表示活动持续时间的带权有向无环图称为AOE-网。