摘要: 简单说一下回溯法，回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点压栈；当该节点出栈时，我们再把它标记为没有走过，这样就能保证另外一条路也能经过该点了
阅读全文
posted @
2012-08-20 16:09 小鼠标 阅读(426) |
评论 (0) |
编辑 收藏
摘要: 图的常见遍历方式有两种：深度优先遍历和广度优先遍历，他们的作用是将图中的每个点都访问一遍，只不过是顺序不同。
如果把图中的每条边长都相等（比如都是1）的话，深度优先遍历的过程是：
1.任意选定一个点p0作为遍历的起点
2.从未访问节点中任选一个距离p0最近的点进行访问，并标记该点被访问过
3.重复第2步，直到该连通分支中的所有节点都被访问过
阅读全文
posted @
2012-08-20 12:23 小鼠标 阅读(1589) |
评论 (0) |
编辑 收藏