关于作者：
作者：flowlet，资深开发专家，
大厂资深云网络从业人员
博客：www.flowlet.net
无论是数据中心内的整网网络拓扑，还是网络设备内的业务转发逻辑（如开源用户态网络协议栈 VPP：Vector Packet Processing）都构成一张有向图。想要从这张图中提取有用信息，就需要图论方面的相关知识。
本文讲解下图论基础及深度优先遍历（DFS）、广度优先遍历（BFS）。
1、图论基础
图论（Graph Theory）是离散数学的一个分支，图（Graph）是由点集合和这些点之间的连线组成，其中点被称为：顶点（Vertex/Node/Point），点与点之间的连线则被称为：边（Edge/Arc/Link）。记为，G = (V, E)。
1.1 有向图和无向图
根据边是否有方向，图可以被划分为：有向图（Directed Graph）和无向图（Undirected Graph）。一般我们把有向图的顶点和边称为：(Node, Arc)，而无向图的顶点和边称为：(Vertex, Edge)。
与顶点相关联的边的数目则称为该顶点的度（Degree），对于有向图而言，顶点 A 的出度（Outdegree） 为以 A 为起点的有向边的数目，顶点 A 的入度（Indegree） 为以 A 为终点的有向边的数目。对于无向图而言其没有出度和入度的概念。
1.2 加权图和无权图
每条边都有权值（Weight） 的图称为加权图（Weighted Graph），相反每条边都没有权值的图称为无权图（Unweighted Graph）。
1.3 稀疏图和稠密图
稀疏图（Sparse Graph）：边的数目相对较少（远小于 n x (n-1)）的图称为稀疏图。
稠密图（Dense Graph）：边的数目相对较多的图称为稠密图。
2、图的表示
图的存储可以通过顺序存储结构和链式存储结构来实现。其中顺序存储结构包括：邻接矩阵和边集数组。链式存储结构包括：邻接表、链式前向星、十字链表和邻接多重表。
接下来我们来介绍两种常用的图存储结构：邻接矩阵与邻接表。
2.1 邻接矩阵
邻接矩阵（Adjacency Matrix）：使用一个二维矩阵来存储顶点之间的邻接关系。
对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将矩阵 V[i][j] 和 V[j][i] 标记为 1；相反矩阵 V[i][j] 为 0 则代表两点之间没边。对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
对于有向图来说，如果有一条从顶点 i 指向顶点 j 的边，我们就将矩阵 V[i][j] 标记为 1。对于加权图而言，数组中存储就是对应的权值。
邻接矩阵的特点：
优点：实现简单，可以直接查询顶点 Vi 与 Vj 之间是否存在边（或者直接查询其边的权值），因此增删查改操作的效率很高，时间复杂度均为 O(1)。
缺点：空间复杂度为 O(
