图

图

图由vertext以及edge组成，分为有向图和无向图。

以下为图的相关概念

度

与顶点相邻的边的数量，在有向图中，分为入度以及出度。

权

边可以有权重，代表距离、费用、时间或者其他度量。

路径

从一个顶点到另一个顶点的一系列连续的边。

路径长度

不考虑权重，路径为边的数量；考虑权重，路径为权重的累加。

环

在有向图中，从顶点A开始，经过若干条边，回到A，则形成了环。

图的连通性

两个顶点之间存在路径，则称两个顶点是连通的。若图中所有顶点都连通，则陈为连通图。若子图连通，则子图为连通分量。

图的表示方法

• 邻接矩阵（二维数组）

   A B C D             A B C D
A  0 1 1 0          A  0 1 1 0
B  1 0 0 1          B  0 0 0 1
C  1 0 0 1          C  0 0 0 1
D  0 1 1 0          D  0 0 0 0

• 邻接表（数组＋链表）

A -> B -> C          A -> B -> C
B -> A -> D          B -> D
C -> A -> D          C -> D
D -> B -> C          D

图的克隆（深拷贝）

• BFS遍历克隆

1. use queue for traversal
2. poll one，clone this node
3. handle all edge，if edge do not clone，clone this node and add to map
4. update current node's edges