下面是我修改了滴源码,是基于一张简单的地图,在地图上搜索目的节点,依次用深度优先、广度优先、Dijkstra算法实现.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;
/**
*
* @author yinzhuo
*/
public class Arithmatic {
boolean flag = true;
// 一张地图
static int[][] map = new int[][]// 地图数组
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
DOM解析
①构建Document对象：
DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
DocumentBuilder db = bdf.newDocumentBuilder();
InputStream is = Thread.currentThread().getContextClassLoader().getResourceAsStream(xml文件);
Document doc = bd.parse(is);
②遍历DOM对象
Document：XML文档对象,由解析器获取
NodeList：节点数组
Node：节点(包括element、#text)
Element：元素,可用于获取属性参数
SAX(Simple API for XML)解析
【DefaultHandler类】
SAX事件处理程序的默认基类,实现了DTDHandler、ErrorHandler、ContextHandler和EntityResolver接口,通常
做法是,继承该基类,重写需要的方法,如startDocument()
【创建SAX解析器】
SAXParserFactory saxf = SAXParserFactory.newInstance();
SAXParser sax = saxf.newSAXParser();
注：关于遍历
①深度优先遍历(Depthi-First Traserval)
②广度优先遍历(Width-First Traserval)
JDOM(Java-based Document Object Model)
StAX(Streaming API for XML)
你百度一下jackson,这个可以很好的转换类型.比如bean和json转换.map和json的转换,json和xml的转换等,都可以的.也很好使.
假设初始状态是图中所有顶点均未被访问
从某个顶点出发,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到.
若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止.
实现深度优先遍历的关键在于回溯.所谓"回溯",就是自后往前,追溯曾经走过的路径.
算法特点
深度优先搜索是一个递归的过程.
首先,选定一个出发点后进行遍历,如果有邻接的未被访问过的节点则继续前进.
若不能继续前进,则回退一步再前进
若回退一步仍然不能前进,则连续回退至可以前进的位置为止.
重复此过程,直到所有与选定点相通的所有顶点都被遍历.
深度优先搜索是递归过程,带有回退操作,所以呢需要使用栈存储访问的路径信息.当访问到的当前顶点没有可以前进的邻接顶点时,需要进行出栈操作,将当前位置回退至出栈元素位置.
图解过程
无向图的深度优先遍历
以下图所示无向图说明深度优先搜索遍历过程.
实例一
今天这一节插入图片描述
假设我们从顶点A开始,遍历过程中的每一步如下：
首先选取顶点A为起始点,输出A顶点信息,而且将A入栈,并且标记A为已访问顶点
A的邻接顶点有C、D、F,从中任意选取一个顶点前进.这里我们选取C为前进位置顶点.输出C顶点信息,将C入栈,并标记C为已访问顶点.当前位置指向顶点C
顶点C的邻接顶点有A、D、B,此时A已经标记为已访问顶点,所以呢不能继续访问.从B或者D中选取一个顶点前进,这里我们选取B顶点为前进位置顶点.输出B顶点信息,将B入栈,标记B顶点为已访问顶点.当前位置指向B
顶点B的邻接顶点只有C、E,C已被标记,不能继续访问,所以呢选取E为前进位置顶点,输出E顶点信息,将E入栈,标记E顶点,当前位置指向E.
顶点E的邻接顶点均已被标记,此时无法继续前进,则需要进行回退.将当前位置回退至顶点B,回退的同时将E出栈.
顶点B的邻接顶点也均被标记,需要继续回退,当前位置回退至C,回退同时将B出栈.
顶点C可以前进的顶点位置为D,则输出D顶点信息,将D入栈,并标记D顶点.当前位置指向顶点D.
顶点D没有前进的顶点位置,所以呢需要回退操作.将当前位置回退至顶点C,回退同时将D出栈.
顶点C没有前进的顶点位置,继续回退,将当前位置回退至顶点A,回退同时将C出栈.
顶点A前进的顶点位置为F,输出F顶点信息,将F入栈,并标记F.将当前位置指向顶点F.
顶点F的前进顶点位置为G,输出G顶点信息,将G入栈,并标记G.将当前位置指向顶点G.
顶点G没有前进顶点位置,回退至F.当前位置指向F,回退同时将G出栈.
顶点F没有前进顶点位置,回退至A,当前位置指向A,回退同时将F出栈.
顶点A没有前进顶点位置,继续回退,栈为空,则以A为起始的遍历结束.若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程.直至所有顶点均被访问.
采用深度优先搜索遍历顺序为A-C-B-E-D-F-G.
利用一个临时栈来实现回溯,最终遍历完所有顶点
问题：
（1）必须选取A作为遍历的起点吗?
不是原则我们可以选取任何一个节点作为起点进行开始,进行深度优先遍历
随便哪个都行.
当有多个临界点可选时,相当于走迷宫时出现了多个分叉路口,我们只要不走之前走过的路就行了.所以关键在于标记哪个点是否已经走过.不过,一般我们会定义一个原则,必须不碰重复点的情况下,选择走左/右手第一条没有走过的路,这样比较好理解
两个原则：
右手原则： 在没有碰到重复顶点的情况下,分叉路口始终是向右手边走,每路过一个顶点就做一个记号
左手原则： 在没有碰到重复顶点的情况下,分叉路口始终是向左手边走,每路过一个顶点就做一个记号
下面以右手原则进行深度优先遍历再看个例子
实例二
原则我们可以选取任何一个节点作为起点进行开始,进行深度优先遍历,假设我们从顶点A开始,遍历过程中的每一步如下：
第一步：从顶点A开始,将顶点A标记为已访问节点
第二步：根据右手原则,访问顶点B,并将B标记为已访问节点
第三步：右手原则,访问顶点C
第四步：右手原则,访问顶点D
第五步：右手原则,访问顶点E
第六步：右手原则,访问顶点F
第七步：右手原则,应该先访问顶点F的邻接顶点A,但发现A已经被访问,则访问A之外的最右侧顶点G
第八步：右手原则,先访问顶点B,顶点B已经被访问；在访问顶点D,顶点D已经被访问；最后访问顶点H
第九步：发现顶点H的邻接顶点均已被访问,则退回到顶点G;
第十步：顶点G的邻接顶点均已被访问,则退回到顶点F；
第十一步：顶点F的邻接顶点已被访问,则退回到顶点E；
第十二步：顶点E的邻接顶点均已被访问,则退回到顶点D；
第十三步：顶点D的邻接顶点I尚未被访问,则访问顶点I；
第十四步：顶点I的邻接顶点均已被访问,则退回到顶点D;
第十五步：顶点D的邻接顶点均已被访问,退回到顶点C；
第十六步：顶点C的邻接顶点均已被访问,则退回到顶点B；
顶点B的邻接顶点均已被访问,则退回到顶点A,顶点A为起始顶点,深度优先搜索结束.
图的深度优先搜索和二叉树的前序遍历、中序遍历、后序遍历本质上均属于一类方法.
首先选定一个未被访问过的顶点V作为起始顶点（或者访问指定的起始顶点V）,并将其标记为已访问
然后搜索与顶点V邻接的所有顶点,判断这些顶点是否被访问过,如果有未被访问过的顶点W；再选取与顶点W邻接的未被访问过的一个顶点并进行访问,依次重复进行.当一个顶点的所有的邻接顶点都被访问过时,则依次回退到最近被访问的顶点.若该顶点还有其他邻接顶点未被访问,则从这些未被访问的顶点中取出一个并重复上述过程,直到与起始顶点V相邻接的所有顶点都被访问过为止.
有向图深度优先搜索
（1）以顶点A为起始点,输出A,将A入栈,并标记A为已经访问.当前位置指向A.
（10）顶点C没有前进位置,进行回退至D,回退同时将C出栈.
（11）继续执行此过程,直至栈为空,以A为起始点的遍历过程结束.若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程.直至所有顶点均被访问.
性能分析
)
广度优先搜索
算法思想
思想：
从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点
然后分别从这些邻接点出发依次访问它们的邻接点,并使得"先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到.
如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止.
实现广度优先遍历的关键在于回放.
回溯与重放是完全相反的过程.
仍然以刚才的图为例,按照广度优先遍历的思想
像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放.
同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现.
另外,还需要标记某个点是否已经被访问过,可以用数组、set等来实现
可以看出,广度优先搜索它其实就是一种"地毯式"层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索.
广度优先搜索类似于树的层次遍历,是按照一种由近及远的方式访问图的顶点.在进行广度优先搜索时需要使用队列存储顶点信息.
无向图的广度优先搜索
（1）选取A为起始点,输出A,A入队列,标记A,当前位置指向A.
（10）队列空,则以A为起始点的遍历结束.若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程.直至所有顶点均被访问.
有向图的广度优先搜索
（1）选取A为起始点,输出A,将A入队列,标记A.
（10）队列头为D,D出队列,D的邻接顶点为B,B已被标记,无新元素入队列
（11）队列为空,且所有元素均被访问,广度优先搜索遍历过程结束.广度优先搜索的输出序列为：A-B–C-E-F-G-H-D.
算法分析
我们来看下,广度优先搜索的时间、空间复杂度是多少呢?假设图有V个顶点,E条边
每个顶点都需要进出一遍队列,每个边都会被访问一次.所以,广度优先搜索的时间复杂度是O(V◆E).当然,对于一个连通图来说,也就是说一个图中的所有顶点都是连通的,,E 肯定要大于等于 V-1,所以,广度优先搜索的时间复杂度也可以简写为 O(E)
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列上.这两个存储空间的大小都不会超过顶点的个数,所以空间复杂度是 O(V).
总结
图的遍历主要就是这两种遍历思想,深度优先搜索使用递归方式,需要栈结构辅助实现.广度优先搜索需要使用队列结构辅助实现.在遍历过程中可以看出,
对于连通图,从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点
对于非连通图,从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点.
实现
深度优先遍历
当图采用邻接矩阵进行存储,递归的实现操作：
#define MAXVBA 100
typedef struct {
char vexs[MAXVBA];
int arc[MAXVBA][MAXVBA];
int numVertexes, numEdges;
} MGraph;
// 邻接矩阵的深度有限递归算法
#define TRUE 1
#define FALSE 0
typedef int Boolean; // 这里我们定义Boolean为布尔类型,其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组
void DFS(MGraph G, int i){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
for (int j = 0; j G.numVertexes; ◆◆j) {
if (G.arc[i][j] == 1 !visited[j]){
DFS(G, j); // 对为访问的邻接顶点递归调用
}
// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
int i;
// 初始化所有顶点状态都是未访问过状态
for (i = 0; i G.numVertexes; ◆◆i) {
visited[i] = FALSE;
//防止图为非联通的情况,遍历整个图
if (!visited[i]){ // 若是连通图,只会执行一次
DFS(G, i);
当图采用邻接矩阵进行存储,栈的实现操作：
void DFS_Stack(MGraph G, int i)
int node;
int count = 1;
printf("%c ", G.vexs[i]); // 打印已访问顶点
node = i;
push(i); //开始的节点入栈
while(count G.numVertexes) //still has node not visited
/* 所有被访问的节点依次入栈,只有node当找不到下一个相连的节点时,才使用出栈节点 */
for(j=0; j G.numVertexes; j◆◆)
if(G.arc[node][j] == 1 visited[j] == FALSE)
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
count◆◆;
push(j); //push node j
break;
if(j == G.numVertexes) //与node相连的顶点均已被访问过,所以需要从stack里取出node的上一个顶点,再看该顶点的邻接顶点是否未被访问
node = pop();
else //找到与node相连并且未被访问的顶点,
node = j;
请添加图片描述
邻接表存储下图的深度优先搜索代码实现,与邻接矩阵的思想相同,只是实现略有不同：
// 邻接表的深度有限递归算法
void DFS(GraphAdjList GL, int i)
EdgeNode *p;
printf("%c " GL-adjList[i].data);
p = GL-adjList[i].firstEdge;
while(p)
if( !visited[p-adjvex] )
DFS(GL, p-adjvex);
p = p-next;
// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
for( i=0; i GL-numVertexes; i◆◆ )
visited[i] = FALSE; // 初始化所有顶点状态都是未访问过状态
if( !visited[i] ) // 若是连通图,只会执行一次
DFS(GL, i);
广度优先遍历
// 邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G)
int i, j;
Queue Q;
for( i=0; i G.numVertexes; i◆◆ )
initQueue( Q );
if( !visited[i] )
printf("%c ", G.vex[i]);
EnQueue(Q, i);
while( !QueueEmpty(Q) )
DeQueue(Q, i);
for( j=0; j G.numVertexes; j◆◆ )
if( G.art[i][j]==1 !visited[j] )
printf("%c ", G.vex[j]);
EnQueue(Q, j);
(1)DOM解析
DOM是html和xml的应用程序接口(API),以层次结构（类似于树型）来组织节点和信息片段,映射XML文档的结构,允许获取
【优点】
①允许应用程序对数据和结构做出更改.
②访问是双向的,可以在任何时候在树中上下导航,获取和操作任意部分的数据.
【缺点】
①通常需要加载整个XML文档来构造层次结构,消耗资源大.
【解析详解】
Document： XML文档对象,由解析器获取
NodeList： 节点数组
Node： 节点(包括element、#text)
Element： 元素,可用于获取属性参数
流模型中的"推"模型分析方式.通过事件驱动,每发现一个节点就引发一个事件,事件推给事件处理器,通过回调方法
完成解析工作,解析XML文档的逻辑需要应用程序完成
【优势】
①不需要等待所有数据都被处理,分析就能立即开始.
②只在读取数据时检查数据,不需要保存在内存中.
③可以在某个条件得到满足时停止解析,不必解析整个文档.
④效率和性能较高,能解析大于系统内存的文档.
①需要应用程序自己负责TAG的处理逻辑（例如维护父/子关系等）,文档越复杂程序就越复杂.
②单向导航,无法定位文档层次,很难同时访问同一文档的不同部分数据,不支持XPath.
【原理】
简单的说就是对文档进行顺序扫描,当扫描到文档(document)开始与结束、元素(element)开始与结束时通知事件
处理函数(回调函数),进行相应处理,直到文档结束
【事件处理器类型】
①访问XML DTD：DTDHandler
②低级访问解析错误：ErrorHandler
③访问文档内容：ContextHandler
Java特定的文档对象模型.自身不包含解析器,使用SAX
①使用具体类而不是接口,简化了DOM的API.
②大量使用了Java集合类,方便了Java开发人员.
①没有较好的灵活性.
②性能较差.
简单易用,采用Java集合框架,并完全支持DOM、SAX和JAXP
①大量使用了Java集合类,方便Java开发人员,同时提供一些提高性能的替代方法.
②支持XPath.
③有很好的性能.
①大量使用了接口,API较为复杂.
【和推式解析相比的优点】
②同推式解析相比,拉式解析的代码更简单,而且不用那么多库.
④拉式解析允许你过滤XML文件和跳过解析事件.
【简介】
javax.xml.stream包中.XMLStreamReader接口用于分析一个XML文档,而XMLStreamWriter接口用于生成一个
XML文档.XMLEventReader负责使用一个对象事件迭代子分析XML事件-这与XMLStreamReader所使用的光标机制
形成对照.
以上就是土嘎嘎小编为大家整理的广度优先遍历java代码相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！