poj1273--网络流
摘要: 最赤裸的网络流，不断找出增广路增广即可。找增广路时，这里用的深度优先搜索。
阅读全文
posted @
2012-09-07 21:29 小鼠标 阅读(281) |
评论 (1) 编辑
poj2488--回溯
摘要: 简单说一下回溯法，回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点压栈；当该节点出栈时，我们再把它标记为没有走过，这样就能保证另外一条路也能经过该点了
阅读全文
posted @
2012-08-20 16:09 小鼠标 阅读(434) |
评论 (0) 编辑
poj2386--图的遍历
摘要: 图的常见遍历方式有两种：深度优先遍历和广度优先遍历，他们的作用是将图中的每个点都访问一遍，只不过是顺序不同。
如果把图中的每条边长都相等（比如都是1）的话，深度优先遍历的过程是：
1.任意选定一个点p0作为遍历的起点
2.从未访问节点中任选一个距离p0最近的点进行访问，并标记该点被访问过
3.重复第2步，直到该连通分支中的所有节点都被访问过
阅读全文
posted @
2012-08-20 12:23 小鼠标 阅读(1594) |
评论 (0) 编辑
zoj1060，poj1094--拓扑排序
摘要: 下面我先说以下拓扑排序：
严蔚敏《数据结构》上的定义是：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
直观的说偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
拓扑排序的具体做法是：
1.在有向图中选择一个没有前驱（入度为0）的顶点，输出
2.从图中删除该顶点和所有以它为尾的弧，并更新相关点的入度
3.重复1，2步，直到所有顶点都被输出，或者发现图中存在回路。
阅读全文
posted @
2012-08-16 19:19 小鼠标 阅读(1795) |
评论 (0) 编辑
单源最短路径Dijkstra算法
摘要: dijkstra算法是解决单源最短路径问题的经典算法，具有O(N^2)的时间复杂度（N为节点个数），这种算法采用的是贪心策略，它与最小生成树的Prim算法极其相似，这两种算法仅仅是cost[]代表的含义不同……
阅读全文
posted @
2012-08-08 16:27 小鼠标 阅读(1870) |
评论 (0) 编辑