- 浏览: 583978 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现,而广度优先搜索通过队列来实现。
深度优先搜索:
下面图中的数字显示了深度优先搜索顶点被访问的顺序。
为了实现深度优先搜索,首先选择一个起始顶点并需要遵守三个规则:
(1) 如果可能,访问一个邻接的未访问顶点,标记它,并把它放入栈中。
(2) 当不能执行规则1时,如果栈不空,就从栈中弹出一个顶点。
(3) 如果不能执行规则1和规则2,就完成了整个搜索过程。
广度优先搜索:
在深度优先搜索中,算法表现得好像要尽快地远离起始点似的。相反,在广度优先搜索中,算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
实现广度优先搜索,也要遵守三个规则:
(1) 访问下一个未来访问的邻接点,这个顶点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问顶点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
下面是一个练习的简单例子:列磁盘目录(深度优先和广度优先实现)
下载源码:
深度优先搜索:
下面图中的数字显示了深度优先搜索顶点被访问的顺序。
为了实现深度优先搜索,首先选择一个起始顶点并需要遵守三个规则:
(1) 如果可能,访问一个邻接的未访问顶点,标记它,并把它放入栈中。
(2) 当不能执行规则1时,如果栈不空,就从栈中弹出一个顶点。
(3) 如果不能执行规则1和规则2,就完成了整个搜索过程。
广度优先搜索:
在深度优先搜索中,算法表现得好像要尽快地远离起始点似的。相反,在广度优先搜索中,算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
实现广度优先搜索,也要遵守三个规则:
(1) 访问下一个未来访问的邻接点,这个顶点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问顶点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
下面是一个练习的简单例子:列磁盘目录(深度优先和广度优先实现)
import java.io.File; import java.io.IOException; import java.util.Stack; import java.util.Queue; import java.util.LinkedList; public class ListFile{ public static void main(String[] args) throws IOException { File file = new File("c:/java/guest"); DFS1(file); System.out.println("--------------------------------"); System.out.println("--------------------------------"); // DFS2(file); BFS(file); } // 文件深度非递归遍历 private static void DFS1(File file) throws IOException { Stack<File> stack = new Stack<File>(); stack.push(file); File fileInStack = null; while (!stack.isEmpty()) { fileInStack = stack.pop(); System.out.println("dir:" + fileInStack.getCanonicalPath()); File[] files = fileInStack.listFiles(); for (File eachFile : files) { if (eachFile.isFile()) { System.out.println("file:" + eachFile.getCanonicalPath()); } else { stack.push(eachFile); } } } } // 文件深度递归遍历 private static void DFS2(File file) throws IOException { System.out.println("dir:" + file.getCanonicalPath()); File[] files = file.listFiles(); for (File eachFile : files) { if (eachFile.isFile()) { System.out.println("file:" + eachFile.getCanonicalPath()); } else { DFS2(eachFile); } } } // 文件广度非递归遍历 private static void BFS(File file) throws IOException{ System.out.println(file.getCanonicalPath()); Queue<File> queue = new LinkedList<File>(); queue.offer(file); File fileInQueue = null; while (queue.size() > 0) { fileInQueue = queue.poll(); //System.out.println("dir--:" + fileInQueue.getCanonicalPath()); File[] files =fileInQueue.listFiles(); for (File eachFile : files) { if (eachFile.isFile()) { System.out.println("file:" + eachFile.getCanonicalPath()); } else { System.out.println("dir--:" + eachFile.getCanonicalPath()); queue.offer(eachFile); } } } } }
下载源码:
发表评论
-
图的练习题(有解答)
2012-12-27 22:23 26141. 填空题 ⑴ 设无向图G ... -
排序练习题
2012-12-27 16:46 1498一、选择题 1、以下序 ... -
2011计算机考研题
2012-12-20 12:19 1453初中的数学书上 ... -
2010计算机考研题:循环左移数组
2012-12-18 16:56 1443一、第一种方法,都想得到的。 static int[] L ... -
两种方法反转单链表
2012-12-17 20:38 1743/** * @author luochengcheng ... -
2009计算机考研题:查找链表中倒数第k个结点
2012-12-15 20:36 1332原理:两个指针先都指向头指针的下一节点,一个指针先走K-1 ... -
二叉搜索树练习 HDU3791
2012-11-25 19:52 1608一棵二叉查找树是按二叉树结构来组织的。这样的树可以用 ... -
上楼梯(深搜+回溯)JAVA解答
2012-11-12 15:28 1309N阶楼梯上楼问题:一次可以走两阶或一阶,请把所有行走方式打印出 ... -
深度优先搜索解组合问题(JAVA)
2012-11-10 12:17 1529题:输出从n不同元素中取m个的所有组合 下面程序使用了深度优先 ... -
图示克鲁斯卡尔构造最小生成树的过程
2012-11-06 11:29 1456... -
图示普里姆算法构造最小生成树的过程
2012-11-06 11:24 1391... -
由二叉树的后序遍历和中序遍历结果写出前序遍历
2012-10-07 17:32 1501【题目】 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ... -
树与二叉树:选择题50个
2012-08-23 16:33 3046单项选择题 (C) 1. 不含任何结点的空树 ... -
二叉树:填空题
2012-08-22 13:17 1832填空: 1. 由3个结点所 ... -
输出给定二叉树的嵌套括号表示(java)
2012-08-21 20:52 1762题:对于下图的二叉树,输出其嵌套括号表示 import j ... -
二叉树:选择题
2012-08-21 15:20 1188下面是有关二叉树的叙述,请判断正误(每小题1分,共10分) ( ... -
如何求完全二叉树的叶子节点数?
2012-08-20 22:21 2850设完全二叉树的高度为K: 题:设一棵完全二叉树有700个 ... -
线性表自测题一套及解答
2012-08-10 21:22 2149自测卷 ... -
数据结构概论自测题及答案一套
2012-08-09 21:54 1261一、填空题 ......................... ... -
栈和队列:判断题
2012-08-09 11:35 2147二 判断题 1. 消除递归不一定需要使用栈,此说法( √ ...
相关推荐
#####使用python开发定向抓取器mini_spider.py,实现对种子链接的广度优先抓取,并把URL长相符合特定pattern的网页保存到磁盘上。程序运行:python mini_spider.py -c spider.conf#####配置文件spider.conf:[spider]...
17 广度优先搜索及深度优先搜索 18 实现基本的串操作 19 计算各点到源点的最短距离 20 储油问题 21 中奖彩球问题 22 0-1背包问题 24 二叉树算法集 25 模拟LRU页面置换算法 26 大...
实例17 广度优先搜索及深度优先搜索 53 实例18 实现基本的串操作 59 实例19 计算各点到源点的最短距离 62 实例20 储油问题 65 实例21 中奖彩球问题 67 实例22 0-1背包问题 69 实例23 阶梯计数问题 72 ...
实例17 广度优先搜索及深度优先搜索 53 实例18 实现基本的串操作 59 实例19 计算各点到源点的最短距离 62 实例20 储油问题 65 实例21 中奖彩球问题 67 实例22 0-1背包问题 69 实例23 阶梯计数问题 72 ...
实例17 广度优先搜索及深度优先搜索 53 实例18 实现基本的串操作 59 实例19 计算各点到源点的最短距离 62 实例20 储油问题 65 实例21 中奖彩球问题 67 实例22 0-1背包问题 69 实例23 阶梯计数问题 72 ...
实例17 广度优先搜索及深度优先搜索 53 实例18 实现基本的串操作 59 实例19 计算各点到源点的最短距离 62 实例20 储油问题 65 实例21 中奖彩球问题 67 实例22 0-1背包问题 69 实例23 阶梯计数问题 72 ...
065 图的深度优先遍利 066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值...
实例116 图的深度优先搜索 172 实例117 图的广度优先搜索 175 实例118 Prim算法求最小生成树 177 实例119 迪杰斯特拉算法 180 第4章 算法 183 4.1 简单问题算法 184 实例120 任意次方后的最后三位 ...
065 图的深度优先遍利 066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值...
065 图的深度优先遍利 066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值计算与趣味...
066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值计算与趣味数学篇 075 绘制余弦曲线...
065 图的深度优先遍利 066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值...
065 图的深度优先遍利 066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值...
042 插入排序 043 希尔排序 044 冒泡排序 045 快速排序 ...和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 ...
请使用python开发一个迷你定向抓取器mini_spider.py,实现对种子链接的广度优先抓取,并把URL长相符合特定pattern的网页保存到磁盘上。程序运行:python mini_spider.py -c spider.conf###配置文件spider.conf:...
065 图的深度优先遍利 066 图的广度优先遍利 067 求解最优交通路径 068 八皇后问题 069 骑士巡游 070 用栈设置密码 071 魔王语言翻译 072 火车车厢重排 073 队列实例 074 K阶斐波那契序列 第三部分 数值...