图
-
图的==深==度优先遍历相当于树的==前序==遍历。
- 强连通分量是==有向图==的极大强连通子图。连通分量指的是==无向图==中的极大连通子图。
- 一个有向图能被拓扑排序的充要条件就是它是一个==有向无环图==。
- 一个事件==的最早开始时间==和以该事件为尾的弧的活动最早开始时间相同。一个事件的==最迟开始时间==为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的和。
- 位示图法可以在==离散存储方式==中，有效地表示相同大小的固定数据块(例如页面，磁盘的盘块)在存储空间的状态，并用于存储空间的分配和回收。
- ==深度优先搜索和前序二叉遍历==都类似图的深度遍历，都借助==栈==的数据结构；
==广度优先==相关的借助了==队列==的数据结构，类似图的层序遍历。 - 在一个无向图中，==所有顶点的度数之和等于所有边数的2倍==。
- 欧拉回路问题：
==无向图==: 图连通，所有点都是偶数度，或者只有两个点是奇数度。当所有点是偶数度时欧拉路起点可以是任意点；当有两个奇数度点时起点必须是奇数度点。
==有向图==: 图连通，所有点出度=入度，或者有一个点入度-出度=1，有一个点出度-入度=1。同样，当所有点出度=入度时任意点可作为起点；而后者必须以出度-入度=1的点做起点，入度-出度=1的点做终点。 - 当==各边上的权值相等==时,BFS算法可用来解决==单源最短路径==问题。
- 若无向图G = （V.E）中含n个顶点，则保证图G在任何情况下都是连通的，则需要的最少边数为（n-1）×（n-2）/2+1
