bfsjava代码 javafx代码

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

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

武义ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联公司的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：028-86922220（备注：SSL证书合作）期待与您的合作！

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...

参考：

贪吃蛇 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;

}

}

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;

}

BFS求源代码及思路？

1、算法用途：

是一种图像搜索演算法。用于遍历图中的节点，有些类似于树的深度优先遍历。这里唯一的问题是，与树不同，图形可能包含循环，因此我们可能会再次来到同一节点。

2、主要思想：

主要借助一个队列、一个布尔类型数组、邻接矩阵完成（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将各点以及各点的关系存入邻接矩阵。

再从第一个点开始，将一个点存入队列，然后在邻接表中找到他的相邻点，存入队列，每次pop出队列头部并将其打印出来（文字有些抽象，实际过程很简单），整个过程有点像往水中投入石子水花散开。

（邻接表是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集）

3、代码（java）：

(以上图为例的代码）

1 import java.util.*; 2  3 //This class represents a directed graph using adjacency list

4 //representation  5 class Graph1 { 6     private static int V; // No. of vertices 7     private LinkedListInteger a Lists 8  9     // Constructor10     Graph1(int v) {11         V = v;12         adj = new LinkedList[v];13         for (int i = 0; i v; ++i)14             adj[i] = new LinkedList();15     }16 17     // Function to add an edge into the graph18     void addEdge(int v, int w) {19         adj[v].add(w);20     }21 22     // prints BFS traversal from a given source s23     public void BFS() {24         // Mark all the vertices as not visited(By default25         // set as false)26         boolean visited[] = new boolean[V];27         // Create a queue for BFS28         LinkedListInteger queue = new LinkedListInteger();29 30         for (int i = 0; i V; i++) {31             if (!visited[i]) {32                 BFSUtil(i, visited, queue);33             }34         }35     }36 37     public void BFSUtil(int s, boolean visited[], LinkedListInteger queue) {38         // Mark the current node as visited and enqueue it39         visited[s] = true;40         queue.add(s);41 42         while (queue.size() != 0) {43             // Dequeue a vertex from queue and print it44             s = queue.poll();45             System.out.print(s + " ");46 47             // Get all adjacent vertices of the dequeued vertex s48             // If a adjacent has not been visited, then mark it49             // visited and enqueue it50             IteratorInteger i = adj[s].listIterator();51             while (i.hasNext()) {52                 int n = i.next();53                 if (!visited[n]) {54                     visited[n] = true;55                     queue.add(n);56                 }57             }58         }59     }60 61     // Driver method to62     public static void main(String args[]) {63         Graph1 g = new Graph1(4);64 65         g.addEdge(0, 1);66         g.addEdge(0, 2);67         g.addEdge(1, 2);68         g.addEdge(2, 0);69         g.addEdge(2, 3);70         g.addEdge(3, 3);71 72         System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");73         g.BFS();74     }75 }

4、复杂度分析：

算法借助了一个邻接表和队列，故它的空问复杂度为O(V）。 遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。 邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。