bfs算法java代码 java nfs

Java 鼠标控制人物移动，地图随人物移动

去学习A星寻路，可以得到最短路径，其中也包括了绕开障碍物的代码，然后就是动画的图片切换了，如果说要地图跟随主角移动，那个应该是滚屏操作，也就是说你主角往右走，超过窗口或者屏幕（全屏）坐标一半的时候，地图整个往左移动，速度和主角的一样就出来效果了。如果你看不懂A星的话，那咂就给你一段BFS的C++语言代码，自己转换成JAVA代码写法（就是改些关键字，有不少经典的游戏算法都来自C/C++）就可以了，这个是简化版的A星寻路，一样可以找到最近的路径，你把path 这个路径记录下来再换算成像素位置就可以得到行走的具体步伐了...

#include "stdafx.h"

#include iostream

using namespace std;

const int rows = 10;//行数

const int cols = 10;//列数

const int nummax = 4;//每一步，下一步可以走的方向：4个

//四种移动方向(左、右、上、下)对x、y坐标的影响

//x坐标：竖直方向，y坐标：水平方向

const char dx[nummax] = {0,0,-1,1};

const char dy[nummax] = {-1,1,0,0};

//障碍表

char block[rows][cols] = {

0,1,0,0,0,0,0,0,0,0,

0,1,1,0,1,1,1,0,0,0,

0,0,0,0,0,0,0,0,0,0,

1,0,1,0,0,0,0,0,0,0,

0,0,0,0,0,0,1,1,1,0,

0,1,0,0,0,0,1,0,0,0,

0,0,0,0,0,0,1,1,0,1,

0,1,0,0,0,1,0,1,0,1,

0,1,1,1,0,0,0,1,0,1,

0,0,0,0,0,0,0,0,0,0,

};

char block2[rows][cols] = {

0,1,0,0,0,0,0,0,0,0,

0,1,1,0,1,1,1,0,0,0,

0,0,0,0,0,0,0,0,0,0,

1,0,1,0,0,0,0,0,0,0,

0,0,0,0,0,0,1,1,1,0,

0,1,0,0,0,0,1,0,0,0,

0,0,0,0,0,0,1,1,0,1,

0,1,0,0,0,1,0,1,0,1,

0,1,1,1,0,0,0,1,0,1,

0,0,0,0,0,0,0,0,0,0,

};

char path[rows][cols] = {0};//记录路径

int startX = 0,startY = 0;//起始点坐标

int endX = rows - 1,endY = cols - 1;//目标点坐标

//保存节点位置坐标的数据结构

typedef struct tagQNode{

char x,y;

int parentNode;//父节点索引

}QNode;

//打印路径

void printPath()

{

cout  ""  endl;

for (int i = 0;i  rows;++i)

{

for (int j = 0;j  cols;++j)

{

if (1 == path[i][j])

{

cout  "♀";

}

else if(block2[i][j]==0)

cout  "∷";

else if(block2[i][j]==1)

cout  "■";

}

cout  endl;

}

cout  endl;

cout  endl;

}

void BFS()

{

int num = rows * cols;

//利用数组来模拟队列

QNode *queue = (QNode *)malloc(num * sizeof(QNode));

//起始点入队列

queue[0].x = queue[0].y = 0;

queue[0].parentNode = -1;//起始点没有父节点

int front = 0,rear = 1;//队列的头和尾

while(front != rear)//队列不为空

{

for (int i = 0;i  nummax;++i)

{

    char nextX,nextY;//下一步的坐标

nextX = queue[front].x + dx[i];

nextY = queue[front].y + dy[i];

//下一个节点可行

if (nextX = 0  nextX  rows   nextY = 0  nextY  cols   0 == block[nextX][nextY])

{

    //寻找到目标点

if (nextX == endX  nextY == endY)

{

    //生成路径

path[nextX][nextY] = 1;

int ParIn = front;

while(ParIn != -1)

{

path[queue[ParIn].x][queue[ParIn].y] = 1;

ParIn = queue[ParIn].parentNode;

}

//printPath();

}

//入栈

queue[rear].x = nextX;

queue[rear].y = nextY;

queue[rear].parentNode = front;

++rear;

//标记此点已被访问

block[nextX][nextY] = 1;

}

}

++front;

}

free(queue);

}

int _tmain(int argc, _TCHAR* argv[])

{

BFS();

printPath();

system("pause");

    return 0;

}

相关问答

Q1: 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.addAdj(vertexList);

if (!is) {vertexList.addAdj(vertexList);}

}

/**

* 返回节点个数

* @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(){

ArrayListVertex next = null;

for (int i = 0; i vertexList.length; i++) {

printVertx(vertexList[i]);

}

}

public void printVertx(Vertex vertex){

ArrayListVertex 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){

ArrayListVertex 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 ArrayListVertex next = null;

public Vertex(char lab) // constructor

{

label = lab;

isVisted = false;

}

//为节点添加邻接点

public void addAdj(Vertex ver){

if(next == null) next = new ArrayListVertex();

next.add(ver);

}

public ArrayListVertex getAdj(){

return next;

}

public void setIndex(int index){

this.index = index;

}

public String toString(){

return "顶点 "+label+",下标："+index+".";

}

}

代码来自：

Q2: 贪吃蛇 java代码

自己写着玩的,很简单,你试一试哦...

主要用了javax.swing.Timer这个类:

import java.awt.*;

import javax.swing.*;

@SuppressWarnings("serial")

public class MainClass extends JFrame {

ControlSnake control;

Toolkit kit;

Dimension dimen;

public static void main(String[] args) {

new MainClass("my snake");

}

public MainClass(String s) {

super(s);

control = new ControlSnake();

control.setFocusable(true);

kit = Toolkit.getDefaultToolkit();

dimen = kit.getScreenSize();

add(control);

setLayout(new BorderLayout());

setLocation(dimen.width / 3, dimen.height / 3);// dimen.width/3,dimen.height/3

setSize(FWIDTH, FHEIGHT);

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

setResizable(false);

setVisible(true);

}

public static final int FWIDTH = 315;

public static final int FHEIGHT = 380;

}

import java.util.*;

import java.awt.*;

import java.awt.event.*;

import javax.swing.*;

import javax.swing.Timer;

import java.util.Random;

@SuppressWarnings("serial")

public class ControlSnake extends JPanel implements ActionListener {

Random rand;

ArrayListPoint list, listBody;

String str, str1;

static boolean key;

int x, y, dx, dy, fx, fy, flag;

int snakeBody;

int speed;

public ControlSnake() {

snakeBody = 1;

str = "上下左右方向键控制 P键暂停...";

str1 = "现在的长度为:" + snakeBody;

key = true;

flag = 1;

speed = 700;

rand = new Random();

list = new ArrayListPoint();

listBody = new ArrayListPoint();

x = 5;

y = 5;

list.add(new Point(x, y));

listBody.add(list.get(0));

dx = 10;

dy = 0;

fx = rand.nextInt(30) * 10 + 5;// 2

fy = rand.nextInt(30) * 10 + 5;// 2

setBackground(Color.WHITE);

setSize(new Dimension(318, 380));

final Timer time = new Timer(speed, this);

time.start();

addKeyListener(new KeyAdapter() {

public void keyPressed(KeyEvent e) {

if (e.getKeyCode() == 37) {

dx = -10;

dy = 0;

} else if (e.getKeyCode() == 38) {

dx = 0;

dy = -10;

} else if (e.getKeyCode() == 39) {

dx = 10;

dy = 0;

} else if (e.getKeyCode() == 40) {

dx = 0;

dy = 10;

} else if (e.getKeyCode() == 80) {

if (flag % 2 == 1) {

time.stop();

}

if (flag % 2 == 0) {

time.start();

}

flag++;

}

}

});

}

public void paint(Graphics g) {

g.setColor(Color.WHITE);

g.fillRect(0, 0, 400, 400);

g.setColor(Color.DARK_GRAY);

g.drawLine(3, 3, 305, 3);

g.drawLine(3, 3, 3, 305);

g.drawLine(305, 3, 305, 305);

g.drawLine(3, 305, 305, 305);

g.setColor(Color.PINK);

for (int i = 0; i listBody.size(); i++) {

g.fillRect(listBody.get(i).x, listBody.get(i).y, 9, 9);

}

g.fillRect(x, y, 9, 9);

g.setColor(Color.ORANGE);

g.fillRect(fx, fy, 9, 9);

g.setColor(Color.DARK_GRAY);

str1 = "现在的长度为:" + snakeBody;

g.drawString(str, 10, 320);

g.drawString(str1, 10, 335);

}

public void actionPerformed(ActionEvent e) {

x += dx;

y += dy;

if (makeOut() == false) {

JOptionPane.showMessageDialog(null, "重新开始......");

speed = 700;

snakeBody = 1;

x = 5;

y = 5;

list.clear();

list.add(new Point(x, y));

listBody.clear();

listBody.add(list.get(0));

dx = 10;

dy = 0;

}

addPoint(x, y);

if (x == fx y == fy) {

speed = (int) (speed * 0.8);//速度增加参数

if (speed 200) {

speed = 100;

}

fx = rand.nextInt(30) * 10 + 5;// 2

fy = rand.nextInt(30) * 10 + 5;// 2

snakeBody++;// 2

} // 2

repaint();

}

public void addPoint(int xx, int yy) {

// 动态的记录最新发生的50步以内的移动过的坐标

// 并画出最新的snakeBody

if (list.size() 100) {//蛇身长度最长为100

list.add(new Point(xx, yy));

} else {

list.remove(0);

list.add(new Point(xx, yy));

}

if (snakeBody == 1) {

listBody.remove(0);

listBody.add(0, list.get(list.size() - 1));

} else {

listBody.clear();

if (list.size() snakeBody) {

for (int i = list.size() - 1; i 0; i--) {

listBody.add(list.get(i));

}

} else {

for (int i = list.size() - 1; listBody.size() snakeBody; i--) {

listBody.add(list.get(i));

}

}

}

}

public boolean makeOut() {

if ((x 3 || y 3) || (x 305 || y 305)) {

return false;

}

for (int i = 0; i listBody.size() - 1; i++) {

for (int j = i + 1; j listBody.size(); j++) {

if (listBody.get(i).equals(listBody.get(j))) {

return false;

}

}

}

return true;

}

}

Q3: JAVA求10个景点间各个景点的最短路径 图随便话 距离随便 求代码

最有效，切不复杂的方法使用Breadth First Search (BFS). 基本代码如下（伪代码）。因为BFS不用递归，所以可能会有点难理解。

public Stack findPath(Vertex 起始景点, Vertex 目标景点){

Queue Vertex q = new QueueVertex();

s.enqueue(起始景点);

Vertex 当前位置;

while(!s.isEmpty()){

当前位置 = s.dequeue();

if (当前位置 == 目标景点) break;

for (每一个相邻于 当前位置 的景点 Vertex v){

if (!v.visited){

v.parent = 当前位置;

// 不是规定，不过可以节省一点时间

if (v == 目标景点){

current = v;

break;

}

s.enqueue(Vertex v);

v.visited = true;

}

}

}

Stack Vertex solution = new Stack Vertex();

Vertex parent = current;

while (parent != 起始景点){

solution.push(parent);

parent = current.parent;

}

for (graph中的每一个vertex) vertex.visited = false;

return solution(); // 其实这里建议用一个 Path 的inner class 来装所获得的路线

}

然后再 main 求每两个景点之间的距离即可

public static void main(String[] argv){

PathFinder pf = new PathFinder();

Stack[][] 路径 = new Stack[10][10];

for(int i=0; ipf.vertices.length; i++){

for(int j=i+1; jpf.vertices.length; j++){

Stack s = pf.findPath(pf.vertices[i], pf.vertices[j]);

路径[i][j] = s; 路径[j][i] = s; // 假设你的graph是一个undirected graph

}

}

// 这么一来就大功告成了！对于每两个景点n 与 m之间的最短路径就是在 stack[n][m] 中

}

还有一种方法就是用Depth First Search递归式的寻找路径，不过这样比较慢，而且我的代码可能会造成stack overflow

public Stack dfs(Vertex 当前景点，Vertex 目标景点){

if(当前景点 == 目标景点) return;

Stack solution = new Stack();

Stack temp;

for (相邻于 点钱景点 的每一个 Vertex v){

if (!v.visited){

v.visited = true;

temp = dfs(v, 目标景点);

// 抱歉，不记得是stack.size()还是stack.length()

if (solution.size() == 0) solution = temp;

else if(temp.size() solution.size()) solution = temp;

v.visited = false; 复原

}

}

return solution;

}

然后再在上述的Main中叫dfs...

参考：

Q4: 分别用DFS和BFS算法给电脑设置AI(JAVA)

有必胜策略的吧。。状态空间的上限是3^9也就是不到20000实际上没有这么多。所以直接采用BFS标记会比较好。算法的话就是填充表，把表（九个格子）填为必胜、必败，己胜，开始的时候全部标为必败，再从胜状态开始向回BFS（或者DFS也可以），己胜状态向回标的一定是败状态，必胜状态的上一状态为必败态，必败态的上一状态可能是必败或者必胜（这就是因为这家伙走错棋了所以要输！）

我的习惯。不写代码。没有意思。