java廣度優先
1. 深度優先和廣度優先 的區別 ，用法。
1、主體區別
深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件)。
寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。
2、演算法區別
深度優先搜索是每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。
廣度優先搜索是每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。
3、用法
廣度優先屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。
深度優先即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。
(1)java廣度優先擴展閱讀：
實際應用
BFS在求解最短路徑或者最短步數上有很多的應用，應用最多的是在走迷宮上，單獨寫代碼有點泛化，取來自九度1335闖迷宮一例說明，並給出C++/Java的具體實現。
在一個n*n的矩陣里走，從原點（0,0）開始走到終點（n-1,n-1），只能上下左右4個方向走，只能在給定的矩陣里走，求最短步數。n*n是01矩陣，0代表該格子沒有障礙，為1表示有障礙物。
int mazeArr[maxn][maxn]; //表示的是01矩陣int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4個方向，int visit[maxn][maxn]; //表示該點是否被訪問過，防止回溯，回溯很耗時。核心代碼。基本上所有的BFS問題都可以使用類似的代碼來解決。
2. （急）編寫一個java工程，隨機自動生成一個迷宮，並分別運用廣度優先和深度優先算出入口到出口的路徑
3. 在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所使用的游標機制
形成對照。
4. 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所使用的游標機制
形成對照。
5. 求高手，給兩到三個廣度優先的例子，Java最好，C++的不要出現指針。最好還有詳細的說明，謝謝
是不是圖的廣度優先搜索？我也在正在學著數據結構，湊巧就有個這個函數，給你看看。有需要拿完整程序再說。廣度優先和深度優先的都給你。
這里用的是鄰接矩陣為1就是聯通了，為0就是斷開的。
public void dfs(){ 深度優先
vertexList[0].wasVisited=true; 設置訪問標記 vertexList[]為頂點數組，每個頂點類帶有訪問標記和標簽(類裡面的各種信息變數)
displayVertex(0);
theStack.push(0); 壓棧
while(!theStack.isEmpty()){ 為空不操作，不為空操作
int v=getAdjUnvisitedVertex(theStack.peek()); 看棧的當前值
if(v==-1) 如果沒有鄰接點
theStack.pop(); 出棧
else{ 有鄰接點就繼續讓鄰接點入棧
vertexList[v].wasVisited=true; 置為已訪問
displayVertex(v); 輸出頂點
theStack.push(v); 壓棧
}
}
for(int j=0;j<nVerts;j++)
vertexList[j].wasVisited=false; 初始化訪問標志，避免使用標志的時候都成了true
}
public void bfs(){ 廣度優先
vertexList[0].wasVisited=true; 設置為已經搜索過
displayVertex(0); 輸出
theQueue.insert(0); 隊列插入
int v2;
while(!theQueue.isEmpty()){
int v1=theQueue.remove(); 出隊
while((v2=getAdjUnvisitedVertex(v1))!=-1){ 如果沒有鄰接點不操作，有繼續操作，此時會完成給v2更新賦值的操作
vertexList[v2].wasVisited=true;
displayVertex(v2);
theQueue.insert(v2); 不斷讓新的鄰接點坐標入隊
}
}
for(int j=0;j<nVerts;j++)
vertexList[j].wasVisited=false;
}
public int getAdjUnvisitedVertex(int v){
for(int i=0;i<nVerts;i++)
if(adjMat[v][i]==1&&vertexList[i].wasVisited==false)
return i; 返回和該點相鄰且未被訪問的點下標（有return就不用break了）
return -1;
}
6. 什麼是樹的遍歷java
樹遍歷方法:有先序遍歷、中序遍歷、後序遍歷以及廣度優先遍歷四種遍歷樹的方法
Demo:
publicclassThreeLinkBinTree<E>{
publicstaticclassTreeNode{
Objectdata;
TreeNodeleft;
TreeNoderight;
TreeNodeparent;
publicTreeNode(){
}
publicTreeNode(Objectdata){
this.data=data;
}
publicTreeNode(Objectdata,TreeNodeleft,TreeNoderight,TreeNodeparent){
this.data=data;
this.left=left;
this.right=right;
this.parent=parent;
}
}
privateTreeNoderoot;
//以默認的構造器創建二叉樹
publicThreeLinkBinTree(){
this.root=newTreeNode();
}
//以指定根元素創建二叉樹
publicThreeLinkBinTree(Edata){
this.root=newTreeNode(data);
}
/**
*為指定節點添加子節點
*
*@paramparent需要添加子節點的父節點的索引
*@paramdata新子節點的數據
*@paramisLeft是否為左節點
*@return新增的節點
*/
publicTreeNodeaddNode(TreeNodeparent,Edata,booleanisLeft){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
if(isLeft&&parent.left!=null){
thrownewRuntimeException(parent+"節點已有左子節點，無法添加左子節點");
}
if(!isLeft&&parent.right!=null){
thrownewRuntimeException(parent+"節點已有右子節點，無法添加右子節點");
}
TreeNodenewNode=newTreeNode(data);
if(isLeft){
//讓父節點的left引用指向新節點
parent.left=newNode;
}else{
//讓父節點的left引用指向新節點
parent.right=newNode;
}
//讓新節點的parent引用到parent節點
newNode.parent=parent;
returnnewNode;
}
//判斷二叉樹是否為空
publicbooleanempty(){
//根據元素判斷二叉樹是否為空
returnroot.data==null;
}
//返回根節點
publicTreeNoderoot(){
if(empty()){
thrownewRuntimeException("樹為空，無法訪問根節點");
}
returnroot;
}
//返回指定節點（非根節點）的父節點
publicEparent(TreeNodenode){
if(node==null){
thrownewRuntimeException("節點為null，無法訪問其父節點");
}
return(E)node.parent.data;
}
//返回指定節點（非葉子）的左子節點，當左子節點不存在時返回null
publicEleftChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
returnparent.left==null?null:(E)parent.left.data;
}
//返回指定節點（非葉子）的右子節點，當右子節點不存在時返回null
publicErightChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
returnparent.right==null?null:(E)parent.right.data;
}
//返回該二叉樹的深度
publicintdeep(){
//獲取該樹的深度
returndeep(root);
}
//這是一個遞歸方法：每一棵子樹的深度為其所有子樹的最大深度+1
privateintdeep(TreeNodenode){
if(node==null){
return0;
}
//沒有子樹
if(node.left==null&&node.right==null){
return1;
}else{
intleftDeep=deep(node.left);
intrightDeep=deep(node.right);
//記錄其所有左、右子樹中較大的深度
intmax=leftDeep>rightDeep?leftDeep:rightDeep;
//返回其左右子樹中較大的深度+1
returnmax+1;
}
}
//實現先序遍歷
//1、訪問根節點
//2、遞歸遍歷左子樹
//3、遞歸遍歷右子樹
publicList<TreeNode>preIterator(){
returnpreIterator(root);
}
privateList<TreeNode>preIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//處理根節點
list.add(node);
//遞歸處理左子樹
if(node.left!=null){
list.addAll(preIterator(node.left));
}
//遞歸處理右子樹
if(node.right!=null){
list.addAll(preIterator(node.right));
}
returnlist;
}
//實現中序遍歷
//1、遞歸遍歷左子樹
//2、訪問根節點
//3、遞歸遍歷右子樹
publicList<TreeNode>inIterator(){
returninIterator(root);
}
privateList<TreeNode>inIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//遞歸處理左子樹
if(node.left!=null){
list.addAll(inIterator(node.left));
}
//處理根節點
list.add(node);
//遞歸處理右子樹
if(node.right!=null){
list.addAll(inIterator(node.right));
}
returnlist;
}
//實現後序遍歷
//1、遞歸遍歷左子樹
//2、遞歸遍歷右子樹
//3、訪問根節點
publicList<TreeNode>postIterator(){
returnpostIterator(root);
}
privateList<TreeNode>postIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//遞歸處理左子樹
if(node.left!=null){
list.addAll(postIterator(node.left));
}
//遞歸處理右子樹
if(node.right!=null){
list.addAll(postIterator(node.right));
}
//處理根節點
list.add(node);
returnlist;
}
//實現廣度優先遍歷
//廣度優先遍歷又稱為按層遍歷，整個遍歷演算法先遍歷二叉樹的第一層（根節點），再遍歷根節點的兩個子節點（第二層），以此類推
publicList<TreeNode>breadthFirst(){
Queue<TreeNode>queue=newArrayDeque<TreeNode>();
List<TreeNode>list=newArrayList<TreeNode>();
if(root!=null){
//將根元素加入「隊列」
queue.offer(root);
}
while(!queue.isEmpty()){
//將該隊列的「隊尾」的元素添加到List中
list.add(queue.peek());
TreeNodep=queue.poll();
//如果左子節點不為null，將它加入「隊列」
if(p.left!=null){
queue.offer(p.left);
}
//如果右子節點不為null，將它加入「隊列」
if(p.right!=null){
queue.offer(p.right);
}
}
returnlist;
}
}
7. java連連看使用廣度優先演算法實現，求具體解釋廣度優先演算法和代碼
void bfs(TreeNode t){
Queue q = new LinkedList<TreeNode>();
q.enqueue(t);
while(!q.isEmpty && q.peek().element != null){
TreeNode temp = q.dequeue();
System.out.println(temp.element);
q.enqueue(temp.leftchild);
q.enqueue(temp.rightchild);
}
}
class TreeNode <AnyType>{
AnyType element;
TreeNode rightchild;
TreeNode leftchild;
}
8. 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 } };