数据结构之图的遍历和部分性质

本文主要是介绍数据结构之图的遍历和部分性质，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

无向图和有向图

1、无向图中，任意两个顶点之间都存在边的话，就是无向完全图。
　含有n个顶点的无向完全图有 $\frac{n \times (n-1)}{2}$ 条边。
　有向图中，若任意两个顶点之间都存在方向互为相反的有向边，则就是有向完全图。
　含有n个顶点的有向完全图有 $n \times (n-1)$ 条有向边。
2、带权的图常称为网。

图的遍历

1、深度优先遍历（deep-first-search，DFS）：实际上是一种递归，按照某一种规则，比如一直访问当前顶点的右顶点，依次遍历，直到回到出发点；若图中尚有顶点未被访问到，就选图中一个未被访问的顶点作为起点，重复上述过程，直至图中所有顶点都被访问到。
　　对于邻接矩阵存储结构的图，要遍历一个ｎ节点ｅ条边的图来说，要查找每个顶点的邻接点需要访问矩阵中所有元素，因此时间复杂度是 $O(n^2)$
　　对于用邻接表存储结构的图，找邻接点所需的时间取决于顶点和边的数量，时间复杂度是 $O(n+e)$ 。
2、广度优先遍历（breadth-first-search，BFS）：图的广度优先遍历类似于树的层序遍历。