一些术语
阿Q仅列出 术语，不进行详细解释
- G = (V，E)； |V| != 0 （图不存在 空图，至少得有一个顶点）
- 有向图 弧<u,v> & 无向图 边(u,v)
- 简单图 & 多重图 （数据结构中仅讨论简单图）
- 完全图 （边数：无向图 C(n,2) = n(n-1)/2； 有向图 A(n,2)=n(n-1)）
- 子图 （一个错误说法：图的边集的子集和顶点集的子集都构成其子图 ×）
- 连通 – 无向图 & 强连通 – 有向图
- 生成树 – 极小连通子图
- 度 （无向图）& 入度、出度 （有向图）
- 权、带权图 – 网
- 稠密图 & 稀疏图 （判断依据：|E| < |V|*log|V|，稀疏图）
- 路径、路径长度、回路（环）
- 简单路径、简单回路
- 距离 （u->v不存在路径，则距离为 ∞）
- 有向树（与树在逻辑上的区别： 树的边无方向；有向树的边有方向 – 双亲指向孩子）
阿Q对图学习的理解
图有很多类型：①是无向图还是有向图，②是无权图还是带权图（网），③无向图是连通还是非连通 / 有向图是强连通的还是非连通的 ④图有环还是无环 – 要注意有向图的环的概念（如：非连通的无向网、有向无环图）
图的概念较多，在学相关算法时要弄清当前是在处理什么类型的图（还是说都适用），比如：
- 有向无环图 – AOV网（括扑排序）/ AOE网（关键路径）
- 求单源最短路径问题 – 无权图 – BFS算法 / 网 – Dijsktra算法
- 连通的无向网 – 最小生成树
因此图的算法学习应该要依次弄清：
- 当前算法处理的什么类型的图
- 算法处理的是什么问题
- 算法过程
- 算法实现
- 该算法对其他类型的图适不适用
题目
1、① 一个非连通的无向图有 n 个顶点，最多有多少条边？ ② 一个强连通的有向图有n个顶点，最少需要多少条边？ ③ 一个连通的无向图有n个顶点，最少需要多少条边？ ④ 一个非连通的有向图有n个顶点，最多有多少条边？⑤ 无向图有 n 个顶点，要保证图在任何情况下都连通，则最少需要多少条边？
① n-1个顶点组成完全图（无向），再加一个孤零零的顶点，最多有 C(n-1，2) = (n-1)(n-2)/2 条边
② 类似于循环链表的结构， n个顶点组成环，最少需要 n 条边
③ 类似顺序结构，平铺且首尾不相连，因此最少需要 n-1条边
④ n-1个顶点组成完全图（有向），再加一个 单边顶点，最多有 A(n-1，2) + 1 = (n-1)(n-2) + 1 条边
⑤ n-1个顶点组成完全图（无向），再加上带边的顶点，最少需要 C(n-1，2) + 1 = (n-1)(n-2)/2 + 1 条边
阿Q总结：|V| = n
对于无向图：
- |E| < n – 1 ； G一定非连通
- n – 1 <= |E| <= C(n-1，2) ； G可能连通也可能非连通
- |E| > C(n-1，2）； G一定连通
对于有向图：
- |E| < n ； G一定非连通
- n <= |E| <= A(n-1，2) + 1； G可能连通也可能非连通
- |E| > A(n-1，2) + 1； G一定连通
2、对于无向图G=(V,E)，下列正确的是（）
A、当|V| > |E|，G一定是连通的
B、当|V| < |E|，G一定是连通的
C、当|V| = |E| – 1，G一定非连通
D、当|V| > |E| + 1，G一定非连通
|E| < |V| – 1 ； G一定非连通 ，D✔
3、如何对有向无环图中的顶点号重新安排使得该图的邻接矩阵中的所有的1都集中到对角线以上？
分析：1、处理的图类型 – 有向无环图； 2、要求：重新排号使得 该图的邻接矩阵中的所有的1都在上三角（说明：u 到 v 的弧 <u,v> 只有排号靠前的指向排号靠后的，换句话就是说：u是v的先决条件）
在分析完后自然想到 通过括扑排序并依次编号解决 （详情见：括扑排序）
除此之外暴力点的编号方式是：先按各顶点的出度进行排序，再进行调整，排序靠后的元素若存在弧指向排序靠前的，则将该元素移到排序靠前的编号前，如图：
