相关定义

图、顶点、邻接关系(边)

图 graph 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: $G (V, E)$ 其中，G表示一个图，V是图G中 顶点 vertex 的集合，E是图G中边的集合。

线性结构中，元素仅有线性关系，每个元素只有一个直接前驱和直接后继，逻辑关系为“前驱-后继”；
树形结构中，数据元素（结点）之间有着明显的层次关系，每层上的元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。逻辑关系为“parent-child”；
图形结构中，数据元素（顶点）之间具有任意关系，图中任意两个数据元素之间都可能相关，逻辑关系称为 邻接 adjacent

无向边 undirected：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对 $(V_{i}, V_{j})$ 来表示，则左侧无向图表示为： $G = (V_{1}, E_{1})$ ，其中顶点的集合 $V_{1} = {A ， B ， C ， D}$ ; 边的集合 $E_{1} = {(A, B), (B, C), (C, D), (D, A), (A, C)}$
有向边 directed：若从顶点 $V_{i}$ 到 $V_{j}$ 的边有方向，则称这条边为有向边，也称为弧, 用有序偶 $< V_{i}, V_{j} >$ 来表示， $V_{i}$ 称为弧尾， $V_{j}$ 称为弧头，即 $V_{i}$ 指向 $V_{j}$ 。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。右侧有向图表示为： $G = (V_{2}, E_{2})$ ，其中顶点集合 $V_{2} = {A, B, C, D}$ ; 弧集合 $E 2 = {< A, D >, < B, A >, < C, A >, < B, C >}$
网或 有权图：每条边上带有 权weight 的图，也分有向和无向。
完全无向图：该无向图中任意两个顶点之间都存在边，n个顶点共含有 $C_{n}^{2} = \frac{n \times (n - 1)}{2}$ 条边；
完全有向图：该有向图中任意两个顶点之间都存在方向相反的两条弧，n个顶点共含有 $2 \times C_{n}^{2} = n \times (n - 1)$ 条边；

以无向图 $G (V, E)$ 为例，含有n个顶点e条边：

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

深度优先搜索 DFS
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到。