一、常用概念
(0) 图（graph）
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)
G 表示一个图，V 是图 G 中的顶点的集合E 是图 G 中边的集合。
(1) 顶点（vertex）
图中的数据元素
(2) 边（edge）
顶点之间的逻辑关系用边来表示，边集可以是空的。
(3) 路径
从初始节点U到达某个终端节点V。
(4) 闭合路径
如果初始节点与终端节点相同，则将路径称为闭合路径。 如果V0 = VN，则路径将是闭合路径。
(5) 简单路径
如果图的所有节点都是异常的并且异常V0 = VN，那么这种路径P被称为闭合简单路径。
(6) 周期
周期可以定义为除了第一个和最后一个顶点之外没有重复边或顶点的路径。
(7) 连通图
连通图是在V中的每两个顶点(u，v)之间存在一些路径的图。连通图中没有孤立的节点。
(8) 完整图
完整图是每个节点与所有其他节点连接的图。 完整图包含 n(n-1/2）个边，其中n是图中节点的数量。
(9) 权重图
在权重图中，为每个边分配一些数据，例如长度或重量。 边 e 的权重可以给定为 w(e)，其必须是指示穿过边缘的成本的正(+)值。
(10) 循环
与类似端点相关联的边可以称为循环。
(11) 节点的度
无向图中，与顶点 V 相关联的边的数目。
有向图中：
入度表示指向自己的边的数目出度表示指向其他边的数目，该顶点的度等于入度与出度的和。
度为 0 的节点称为隔离节点。
(12) 权 (Weight)、网 (Network)
Weight：与图的边或弧相关的数。
Network：带权的图。
(13) 连通图
连通图图中任意两个顶点都是连通的。
(14) 连通分量（无向图）
连通分量指无向图的极大连通子图（特征如下）
极大顶点数：在增加一个顶点图将不连通极大边数：包含子图中所有顶点相连的所有边
子图三：缺少一条边，故不为连通图。
子图四：缺少一个顶点。
(15) 连通分量（有向图）
该有向图中，极大连通子图 (强连通分量) 有两个！
二、概念习题
1、 具有 N 个顶点的无向图至多有多少个连通分量？
A. 0 、B. 1 、C. N-1 、D. N
正确答案：D你错选为B
2、 如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是
A. 有回路的图 、B. 完全图 、C. 连通图 、D. 一棵树
正确答案：C你错选为A
3、 具有 N 个顶点的无向图至少有多少个连通分量？
A. 0 、B. 1 、C. N-1 、D. N
正确答案：B你选对了
三、图的表示
(1) 邻接矩阵 (二维数组)
表示： 用两个数组，一个数组保存顶点集，一个数组保存边集。
说明：
1. 具有 n 个顶点的图将具有尺寸 n×n。
2. 如果在 Vi 和 Vj 之间存在边缘，则无向图 G 的邻接矩阵表示中的项目 Mij 将为1。
(2) 临界矩阵小测验
1、有个顶点的无向完全图有多少条边？
A. N(N - 1) / 2 B. N(N + 1) / 2 C. N*N D. N*N - N
2、给定有向图的邻接矩阵如下： 顶点2（编号从0开始）的出度和入度分别是：?
3、有向图的邻接矩阵一定是不对称的？
4、用一维数组G[ ]存储有4个顶点的无向图如下：
G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点 2 和顶点 0 之间是有边的。
(2) 邻接表 (链表 + 数组)
提出： 由于邻接矩阵表示，每个顶点都要为它分配 n 条边，其实很多边是不存在的。例如 B —> E 之间就没有边。
优点： 邻接表只关心存在的边，因此无空间浪费；由 链表 + 数组 组成。 说明：
1. 标号为 A 的结点的关联结点为 B、D。（并不表示指向的方向）
2. 邻接列表将节点值和指向下一个相邻节点的指针存储到相应节点。
3. 邻接列表的长度之和等于无向图中存在的边数的 2 倍。
带权的网图：
四、图的遍历
(1) Depth-First-Search
例子： 迷宫点灯 （1） 给定一个入口点 (左上角)，在视力范围内 walker 可以看到 左、下、中这盏灯。
（2） 任意挑选一盏灯去点亮，假如 walker 向右边走。这时 walker 又可以看到两盏灯，一盏是左边的 (起点)，一盏是右下角的暗灯。
（3） walker 选择点亮了右下角的灯，这时 walker 又选择点亮左下角的灯。
（4） walker 有可以选择左、上、左上角的灯，假设 walker 点亮了上面的灯，发现左边的灯是暗的，这时点亮它。
（5） 此处，walker 发现四周的灯都被自己点亮了！那么 walker 应该原路返回一步。
（6） walker 回退了一步，发现四周的灯又是刚刚被点亮的！（并且看到了出口 (也是一开始的入口)）
（7） 这时 DFS 有一个策略：当发现四周的灯都被点亮，这时不应该回到出口，而是回退一步（如果返回后的情形同上，那么继续 (7) 步骤）。
（8） 原路返回的情形也对应着堆栈元素的出栈！
（9） DFS 的伪码描述：
void DFS(int V) {
visited(V) = true; //点亮
for( V 的每一个邻结点 W )
if( !visited(W) )
DFS(W); //如果发现周围的灯都被点亮，那么原路返回就 == 递归返回上一层
}
若有 N 个顶点 E 条边，它的时间复杂度：取决于图的表示方法！
邻接表 —> O (N + E)临界矩阵 —> O (N * N)，因为需要对临界矩阵的一行进行遍历才知道邻接点的位置。
(2) Breadth-First-Search
树是其实一种特殊的图，那么 Breadth-First-Search 的变量类似于树的层序遍历
（1） 指定一个起点，把 AddQueue(起点)，当 removeFirst() 时，顺带地把起点相关联的全部结点 addLast()，并把起点设置为 visited。
（2） 下一轮开始，把 firstElem，相关联的全部结点也 addLast()，直到
（3） BFS 的伪码描述：
void BFS(int V) {
visited(V);
queue.addFirst(V);
while( !queue.isEmpty() ) {
V = queue.removeFirst();
for(//V的每一个邻接点W) { //邻接矩阵表示这一步比较耗时！
visited(W);
queue.addFirst(W);
}
}
}
若有 N 个顶点 E 条边，它的时间复杂度：取决于图的表示方法！
邻接表 —> O (N + E)，临界矩阵 —> O (N*N)，因为需要对临界矩阵的一行进行遍历才知道邻接点的位置。
(3) 两种遍历的比较
① DFS
这时，DFS 的表现并不佳！
② BFS
一、 为什么不一直用 BFS？BFS 什么时候变现不好呢?
答案： 离出发点越远、BFS就会越慢：右下角
二、 试比较 DFS 和 BFS 的优点和缺点
对于层次比较深的问题，用 BFS 队列中的元素较少，而用 DFS 栈中的元素较多，DFS 消耗的空间更多；对于层次比较少但每层的路径很多的问题来说，BFS 队列比 DFS 栈空间开销更大。如果所需要求解的问题在层次较低的地方就可以找到答案，那 BFS 比 DFS 时间效率更高如果在层次较深的地方 DFS 效率更高。
DFS 一条路走到黑，BFS 在任意节点时都需要查看周边全部可能结果。
人生策略来看，前者就是不撞南墙不回头，后者则是随时查看所有可能。从探索效率上来看，前者可能更高，后者稍低。
③ 图不连通怎么遍历？
—> 参考