java深度优先遍历

A. 深度优先搜索遍历和广度优先搜索的遍历序列及具体步骤和原因，

1->2->3->4 （表示1可达到2，达到3，达到4）

2->1->3->5

3->1->2->4->5->6

4->1->3->6

5->2->3->6

6->3->4->5

广度优先搜索就是把每一行按照顺序输出，去掉重复的，即先看1，有1,2,3,4，然后看2，因为有3,4了，所以只要5，然后看3，以此类推。。一行行来。

深度优先搜索，是先看1，然后1可以到2，然后直接看2,2可以到3,5随便选一个都可以，我们到3好了，然后看3的那行可以到1,2,4,5,6随便选一个都可以，不过要去掉重复的，以此类推。可以排出很多种的。

(1)java深度优先遍历扩展阅读：

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

B. java解析xml的几种方式哪种最好

(1)DOM解析
DOM是html和xml的应用程序接口(API)，以层次结构（类似于树型）来组织节点和信息片段，映射XML文档的结构，允许获取
和操作文档的任意部分，是W3C的官方标准
【优点】
①允许应用程序对数据和结构做出更改。
②访问是双向的，可以在任何时候在树中上下导航，获取和操作任意部分的数据。
【缺点】
①通常需要加载整个XML文档来构造层次结构，消耗资源大。
【解析详解】
①构建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： 元素，可用于获取属性参数
(2)SAX(Simple API for XML)解析
流模型中的"推"模型分析方式。通过事件驱动，每发现一个节点就引发一个事件，事件推给事件处理器，通过回调方法
完成解析工作，解析XML文档的逻辑需要应用程序完成
【优势】
①不需要等待所有数据都被处理，分析就能立即开始。
②只在读取数据时检查数据，不需要保存在内存中。
③可以在某个条件得到满足时停止解析，不必解析整个文档。
④效率和性能较高，能解析大于系统内存的文档。
【缺点】
①需要应用程序自己负责TAG的处理逻辑（例如维护父/子关系等），文档越复杂程序就越复杂。
②单向导航，无法定位文档层次，很难同时访问同一文档的不同部分数据，不支持XPath。
【原理】
简单的说就是对文档进行顺序扫描，当扫描到文档(document)开始与结束、元素(element)开始与结束时通知事件
处理函数(回调函数)，进行相应处理，直到文档结束
【事件处理器类型】
①访问XML DTD：DTDHandler
②低级访问解析错误：ErrorHandler
③访问文档内容：ContextHandler
【DefaultHandler类】
SAX事件处理程序的默认基类，实现了DTDHandler、ErrorHandler、ContextHandler和EntityResolver接口，通常
做法是，继承该基类，重写需要的方法，如startDocument()
【创建SAX解析器】
SAXParserFactory saxf = SAXParserFactory.newInstance();
SAXParser sax = saxf.newSAXParser();
注：关于遍历
①深度优先遍历(Depthi-First Traserval)
②广度优先遍历(Width-First Traserval)
(3)JDOM(Java-based Document Object Model)
Java特定的文档对象模型。自身不包含解析器，使用SAX
【优点】
①使用具体类而不是接口，简化了DOM的API。
②大量使用了Java集合类，方便了Java开发人员。
【缺点】
①没有较好的灵活性。
②性能较差。
(4)DOM4J(Document Object Model for Java)
简单易用，采用Java集合框架，并完全支持DOM、SAX和JAXP
【优点】
①大量使用了Java集合类，方便Java开发人员，同时提供一些提高性能的替代方法。
②支持XPath。
③有很好的性能。
【缺点】
①大量使用了接口，API较为复杂。
(5)StAX(Streaming API for XML)
流模型中的拉模型分析方式。提供基于指针和基于迭代器两种方式的支持,JDK1.6新特性
【和推式解析相比的优点】
①在拉式解析中，事件是由解析应用产生的，因此拉式解析中向客户端提供的是解析规则，而不是解析器。
②同推式解析相比，拉式解析的代码更简单，而且不用那么多库。
③拉式解析客户端能够一次读取多个XML文件。
④拉式解析允许你过滤XML文件和跳过解析事件。
【简介】
StAX API的实现是使用了Java Web服务开发（JWSDP）1.6，并结合了Sun Java流式XML分析器(SJSXP)-它位于
javax.xml.stream包中。XMLStreamReader接口用于分析一个XML文档，而XMLStreamWriter接口用于生成一个
XML文档。XMLEventReader负责使用一个对象事件迭代子分析XML事件-这与XMLStreamReader所使用的光标机制
形成对照。

C. 简述深度优先搜索遍历的方法。

简述深度优先搜索遍历的方法？深度优先搜索算法(Depth-First-Search, DFS)，最初是一种用于遍历或搜索树和图的算法，在LeetCode中很常见，虽然感觉不难，但是理解起来还是有点难度的。

简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。

思路
假如对树进行遍历，沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当达到边际时回溯上一个节点再进行搜索。如下图的一个二叉树。


首先给出这个二叉树的深度优先遍历的结果(假定先走左子树)：1->2->4->5->3->6->7

那是怎样得到这样的结果呢？
根据深度优先遍历的概念：沿着这树的某一分支向下遍历到不能再深入为止，之后进行回溯再选定新的分支。

定义节点

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
递归的方式

分别对左右子树进行递归，一直到底才进行回溯。如果不了解递归可以参考我的博客你真的懂递归吗？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面实现了递归方式的深度优先遍历，也可以利用栈把递归转换为迭代的方式。

但是为了保证出栈的顺序，需要先压入右节点，再压左节点。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接着再列举个利用深度优先遍历的方式的题目

扫雷
给定一个表示游戏板的二维字符矩阵，'M'表示一个未挖出的地雷，'E'表示一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。

根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例

输入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根据给定的规则，当给定一个Click坐标，当不为雷的时候以此坐标为基点向四周8个方向进行深度遍历，把空格E填充为B，并且把与地雷M相连的空方块标记相邻地雷的数量。

注意 ：



在这个题中可以沿着8个方向递归遍历，所有要注意程序中，采用了两个for循环可以实现向8个方向递归。

D. java如何实现 深度优先 广度优先

下面是我修改了滴源码，是基于一张简单的地图，在地图上搜索目的节点，依次用深度优先、广度优先、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, 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, 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 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };