bfsjava

⑴ java推箱子怎麼寫啊

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

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

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

⑵ BFS求源代碼及思路

1、演算法用途：

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

2、主要思想：

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

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

4、復雜度分析：

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

⑶ Java 語言中 二叉樹的遍歷

public class BinaryTreeTest
{
public static void main(String args[])
{
BinaryTreeTest b=new BinaryTreeTest();
int data[]={12,11,34,45,67,89,56,43,22,98};
BinaryTree root =new BinaryTree(data[0]); System.out.print("二叉樹的中的數據：");
for(int i=1;i{
root.insertTree(root,data[i]);
System.out.print(data[i-1]+";");
} System.out.println(data[data.length-1]); int key=Integer.parseInt(args[0]); if(b.searchkey(root,key))
{
System.out.println("找到了:"+key);
}
else
{
System.out.println("沒有找到："+key);
}
} public boolean searchkey(BinaryTree root, int key)
{
boolean bl=false;
if(root==null)
{
bl=false;
return bl;
}
else if(root.data==key)
{
bl=true;
return bl;
}
else if(key>=root.data)
{
return searchkey(root.rightpoiter,key);
}
return searchkey(root.leftpoiter,key);
}
} class BinaryTree
{
int data;
BinaryTree leftpoiter;
BinaryTree rightpoiter; BinaryTree(int data)
{
this.data=data;
leftpoiter=null;
rightpoiter=null;
} public void insertTree(BinaryTree root, int data)
{
if(data>=root.data)
{
if(root.rightpoiter==null)
{
root.rightpoiter=new BinaryTree(data);
}
else
{
insertTree(root.rightpoiter,data);
}
}
else
{
if(root.leftpoiter==null)
{
root.leftpoiter=new BinaryTree(data);
}
else
{
insertTree(root.leftpoiter,data);
}
}
}
}

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

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

⑸ Java如何讓一個形狀動起來，就比如貪吃蛇

你知道動畫是如何動起來的么?沒錯,就是一張一張的畫,快速地閃過,當速度足夠快的時候,就好像這個圖形動起來了..
同理,在用java做可移動圖形的時候,比如我們用awt繪圖,當我們一遍一遍擦除重繪,速度到一定程度的時候, 這個圖形就好像動了起來..
2018年8月28日15:55:01

⑹ java中如何把圖用鄰接表表示出來

package my.graph;
import java.util.ArrayList;
import java.util.Iterator;
import my.queue.*;
import my.stack.StackX;
/**
* 鄰接表表示
* @author xiayi
*
*/
public class Graph {
private int MAX_VERTS = 20;
private Vertex vertexList[];
private boolean is = false;//是否為有向圖
private int nVerts = 0;

private StackX stackX;
private Vertex dfs[];

private Vertex bfs[];
private Queue queue;

public Graph(){
vertexList = new Vertex[MAX_VERTS];
dfs = new Vertex[MAX_VERTS];
bfs = new Vertex[MAX_VERTS];
}
public Graph(int n){
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];

}
public Graph(int n, boolean is){
this.is = is;
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
//////////////////////////////////////////////
public boolean isIs() {
return is;
}
public void setIs(boolean is) {
this.is = is;
}
public Vertex[] getVertexList() {
return vertexList;
}
public Vertex[] getDfs() {
return dfs;
}
public Vertex[] getBfs() {
return bfs;
}

////////////////////////////////////////////////////
/**
* 添加頂點
*/
public void addVertex(Vertex vertex){
vertex.setIndex(nVerts);
vertexList[nVerts] = vertex;
nVerts++;
}
/**
* 添加邊
*/
public void addEdge(int start, int end){
vertexList[start].addAdj(vertexList[end]);
if (!is) {vertexList[end].addAdj(vertexList[start]);}
}
/**
* 返回節點個數
* @return
*/
public int getVertsCount(){
return vertexList.length;
}

/**
* 深度優先迭代器
* @return
*/
public Iterator dfsIterator(){
dfs();
return new DfsIterator();
}
/**
* 廣度優先迭代器
* @return
*/
public Iterator bfsIterator(){
bfs();
return new BfsIterator();
}
////////////////////////////////////////////////////////
public void displayGraph(){
ArrayList<Vertex> next = null;
for (int i = 0; i < vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayList<Vertex> next = vertex.getAdj();
if(next == null){ System.out.println(vertex.toString()+" 無連接點");}
else{
System.out.print(vertex.toString()+"有鄰接點:");
for (int i = 0; i < next.size(); i++) {
System.out.print("頂點"+next.get(i).label+", ");
}
System.out.println();
}
}

///////////////////////////////////////////////////////////

public void dfs(){
stackX = new StackX(MAX_VERTS);
vertexList[0].isVisted = true;
dfs[0] = vertexList[0];

stackX.push(vertexList[0]);
int dfsIndex = 0;

Vertex vertex;
while(!stackX.isEmpty()){
vertex = getAdjVertex((Vertex)stackX.peek());
if(vertex == null){
stackX.pop();
}else{
vertex.isVisted = true;
dfs[++dfsIndex]=vertex;
stackX.push(vertex);
}
}

for (int i = 0; i < getVertsCount(); i++) {
vertexList[i].isVisted = false;
}

}

public void bfs() {
queue = new Queue(MAX_VERTS);
vertexList[0].isVisted = true;
bfs[0] = vertexList[0];
queue.insert(vertexList[0]);
int bfsIndex = 0;
Vertex vertex;
while(!queue.isEmpty()){
Vertex vertex2 = (Vertex)queue.remove();
while((vertex = getAdjVertex(vertex2))!=null){
vertex.isVisted = true;
bfs[++bfsIndex] = vertex;
queue.insert(vertex);
}
}

for (int i = 0; i < getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
/**
* 得到一個鄰接點
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayList<Vertex> adjVertexs = vertex.getAdj();
for (int i = 0; i < adjVertexs.size(); i++) {
if(!adjVertexs.get(i).isVisted){
return adjVertexs.get(i);
}
}
return null;
}
/////////////////////////////////////////////////////////////
private abstract class GraphIterator implements Iterator{

int count = 0;
public GraphIterator(){
}
public boolean hasNext() {
return count != getVertsCount()-1;
}
public Object next() {
// TODO Auto-generated method stub
return null;
}
public void remove() {
// TODO Auto-generated method stub

}

}
//深度優先迭代
private class DfsIterator extends GraphIterator{
public DfsIterator(){
super();
}

public Vertex next() {
return dfs[count++];
}
}
//廣度優先迭代
private class BfsIterator extends GraphIterator{
public BfsIterator(){
super();
}

public Object next() {
return bfs[count++];
}
}
/////////////////////////////////////////////////////////

public static void main(String[] args) {
int nVerts = 10;
int c = 'A'-1;
Vertex vertex;
Graph myGraph = new Graph(nVerts, false);
for (int i = 0; i < nVerts; i++) {
c++;
vertex = new Vertex((char)(c));
myGraph.addVertex(vertex);
}
myGraph.addEdge(0, 1);
myGraph.addEdge(0, 4);
myGraph.addEdge(1, 2);
myGraph.addEdge(2, 3);
myGraph.addEdge(4, 5);
myGraph.addEdge(4, 6);
myGraph.addEdge(5, 8);
myGraph.addEdge(6, 7);
myGraph.addEdge(7, 8);
myGraph.addEdge(8, 9);

System.out.println("深度優先迭代遍歷：");
for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());

}

System.out.println("/n廣度優先迭代遍歷：");
for (Iterator iterator = myGraph.bfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());

}
}
}
class Vertex{
public char label;
public boolean isVisted;
public int index;
private ArrayList<Vertex> next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//為節點添加鄰接點
public void addAdj(Vertex ver){
if(next == null) next = new ArrayList<Vertex>();
next.add(ver);
}

public ArrayList<Vertex> getAdj(){
return next;
}

public void setIndex(int index){
this.index = index;
}

public String toString(){
return "頂點 "+label+",下標："+index+".";
}
}

代碼來自：http://blog.csdn.net/Java2King/article/details/5683429