图的存储形式：邻接矩阵（数组）

图的存储形式：邻接矩阵（数组）2015-09-16邻接矩阵：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

比如考虑下面这个有向图：

如果用邻接矩阵存储可以表示为：

1.顶点数组：

2.邻接矩阵：

图的遍历：

深度优先（DFS）：

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾访问过，则深度优先搜索可从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中还有顶点未访问，则另选图中未访问的顶点作为起始点，重复上述过程，直至所有顶点被访问。

上图深度优先遍历结果：abcdfeghi

广度优先（BFS）：

广度优先搜索类似于树的层次遍历。假设从图中某顶点v出发，在访问了v之后，依次访问v的各个未曾访问的邻接点，然后分别从这些邻接点触发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时仍有顶点没访问，另选图中未访问的顶点作为起始点，重复上述过程，直至所有顶点被访问。

上图广度优先遍历结果：abgcehidf