javabfs

『壹』 BFS求源代碼及思路

1、演算法用途：

是一種圖像搜索演演算法。用於遍歷圖中的節點，有些類似於樹的深度優先遍歷。這里唯一的問題是，與樹不同，圖形可能包含循環，因此我們可能會再次來到同一節點。

2、主要思想：

主要藉助一個隊列、一個布爾類型數組、鄰接矩陣完成（判斷一個點是否查看過，用於避免重復到達同一個點，造成死循環等），先將各點以及各點的關系存入鄰接矩陣。

再從第一個點開始，將一個點存入隊列，然後在鄰接表中找到他的相鄰點，存入隊列，每次pop出隊列頭部並將其列印出來（文字有些抽象，實際過程很簡單），整個過程有點像往水中投入石子水花散開。

4、復雜度分析：

演算法藉助了一個鄰接表和隊列，故它的空問復雜度為O(V）。 遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程，其耗費的時間取決於所採用結構。 鄰接表表示時，查找所有頂點的鄰接點所需時間為O(E)，訪問頂點的鄰接點所花時間為O（V）,此時，總的時間復雜度為O(V+E)。

『貳』 深度優先和廣度優先 的區別 ，用法。

1、主體區別

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件)。

寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。

2、演算法區別

深度優先搜索是每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

廣度優先搜索是每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

3、用法

廣度優先屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

深度優先即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。

(2)javabfs擴展閱讀：

實際應用

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問題都可以使用類似的代碼來解決。

『叄』 Java推箱子怎麼寫啊

這是我之前寫的一篇java實現推箱子演算法的文章，簡單的給你看一下：

《推箱子游戲》是一款益智游戲，游戲目標是搬運工自己來找出到某個位置的最短路徑，然後自己走過去。

最後完成地圖顯示問題，每個節點存儲自己父親節點的地址，當節點發現自己已經完成之後根據地址向上查找直到樹頂，望採納，謝謝。

『肆』 分別用DFS和BFS演算法給電腦設置AI(JAVA)

有必勝策略的吧。。狀態空間的上限是3^9也就是不到20000實際上沒有這么多。所以直接採用BFS標記會比較好。演算法的話就是填充表，把表（九個格子）填為必勝、必敗，己勝，開始的時候全部標為必敗，再從勝狀態開始向回BFS（或者DFS也可以），己勝狀態向回標的一定是敗狀態，必勝狀態的上一狀態為必敗態，必敗態的上一狀態可能是必敗或者必勝（這就是因為這傢伙走錯棋了所以要輸！）
我的習慣。不寫代碼。沒有意思。