图论算法定义和计算.ppt

第二节 图的遍历 一深度优先与广度优先遍历 从图中某一顶点出发系统地访问图中所有顶点使每个顶点恰好被访问一次这种运算操作被称为图的遍历为了避免重复访问某个顶点可以设一个标志数组visited[i]未访问时值为false访问一次后就改为true 图的遍历分为深度优先遍历和广度优先遍历两种方法两者的时间效率都是O(n*n) 1.深度优先遍历 深度优先搜索(Depth First Search--DFS