关于数据结构:图及其应用

1. 图的概念

（1）简略图：无反复边且没有顶点到本身的边（数据结构都是简略图）
（2）度：无向图为附丽该点的边数，有向图为出度和入度的和
（3）简略门路：两头顶点不反复的门路
（4）对于无向图，为连通和连通图；对于有向图，为强连通和强连通图
（5）对于 n 个顶点的图：为无向图，为连通则起码 n - 1 条边，不为连通最多 Cn-1(2) 条边

                为有向图，为强连通，则起码 n 条边

（6）极大连通子图：（1）为无向图中，子图必须连通且蕴含尽可能多的点和边

（2）为有向图中，子图必须强连通且蕴含尽可能多的点和边

（7）连通重量和强连通重量：无向图的极大连通子图和有向图的极大连通子图
（8）无向连通图的生成树：为蕴含所有点的极小连通子图（即蕴含所有点且边尽可能少）（n 个点则有 n - 1 条边）
（9）无向 / 有向齐全图：任意两个点有边 / 任意两个点存在方向相同的两条弧

2. 图的存储

（1）邻接矩阵法：
无向图：第 i 个节点的度：某行（列）的非零元素的个数
有向图：第 i 节点的出度：第 i 行的非零元素的个数
求度，出度，入度的工夫复杂度：O(v) 工夫复杂度：O(v*2)
适宜存储浓密图

性质：

(2)邻接表法

性质：街坊表法示意不惟一，但矩阵是惟一的，适宜存储稠密图

（3）十字链表法（只存储有向图）

（4）邻接多重表

总结：

3. 图的利用

（1）最小生成树：带权连通图的权值之和最小的生成树

Prim 算法：不停的加顶点（O(v 平方), 适宜边稠图）
Krusal 算法：不停选最小的边，使边两边的点连通（O(elog2e), 适宜边疏图）

（2）最短门路

（3）有向无环图

（4）拓扑排序

性质:(1)拓扑和逆拓扑可能不惟一

（2）拓扑和逆拓扑内不能有环

（5）要害门路（性质，办法可突击）