数据结构--无向图

1,779 阅读1分钟

图的定义:

图是由一组顶点和一组能够将两个顶点相连的边组成。

连通图:如果从任意一个顶点都存在一条路径到达另一个任意顶点,就称为连通图,一个非连通图由若干连通的部分组成,都称为极大连通子图。

无向图:即连接两个顶点的边是没有方向的。

无向图的遍历

深度优先遍历原理(DFS):

  • 从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达。

  • 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点。

  • 当回退到的路口已没有可走的通道时继续回退。

广度优先遍历原理(BFS):

从起点开始,遍历所有与起点连通的顶点,再遍历与这些顶点连通的顶点,即先搜索距离起点距离为1的顶点,再遍历与起点距离为2的顶点.....