邻接矩阵:用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。
比如考虑下面这个有向图:
如果用邻接矩阵存储可以表示为:
1.顶点数组:
2.邻接矩阵:
图的遍历:
深度优先(DFS):
深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。假设初始状态是图中所有顶点未曾访问过,则深度优先搜索可从图中的某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;若此时图中还有顶点未访问,则另选图中未访问的顶点作为起始点,重复上述过程,直至所有顶点被访问。
上图深度优先遍历结果:abcdfeghi
广度优先(BFS):
广度优先搜索类似于树的层次遍历。假设从图中某顶点v出发,在访问了v之后,依次访问v的各个未曾访问的邻接点,然后分别从这些邻接点触发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时仍有顶点没访问,另选图中未访问的顶点作为起始点,重复上述过程,直至所有顶点被访问。
上图广度优先遍历结果:abgcehidf
时间: 2024-09-19 09:59:43