BFS
| Run Settings | |
|---|---|
| Language | Java |
| Language Version | |
| Run Command |
| Snippet Metadata | |
|---|---|
| Owner | ambar411342 |
| Created | |
| Modified | |
| Visibility | Public |
import java.awt.Point;
public class Main {
public static void main(String args[]){
Map myMap = new Map(10,10);
Node start = new Node(new Point(1,2));
Node goal = new Node(new Point(4,0));
myMap.printMap();
BFS map2dbfs = new BFS(myMap, start, goal);
}
}
import java.awt.Point;
import java.util.LinkedList;
public class BFS {
LinkedList<Node> currentExpand;
LinkedList<Node> nextExpand;
LinkedList<Node> solution;
Node start, goal;
public BFS(Map map, Node start, Node goal){
this.start = start;
this.goal = goal;
currentExpand = new LinkedList<Node>();
nextExpand = new LinkedList<Node>();
solution = new LinkedList<Node>();
currentExpand.add(start);
boolean next = true;
while(next){
for(Node cn:currentExpand){
for(Node nn:map.getNextNode(cn)){
if(!isInLine(cn,nn)){
cn.addChild(nn);
nextExpand.add(nn);
}
}
}
currentExpand.clear();
if(nextExpand.size() == 0){
next = false;
System.out.println("stop");
continue;
}
for(Node nn:nextExpand){
if(nn.equals(goal)){
next = false;
generateSolution(nn);
printSolution();
break;
}else{
currentExpand.add(nn);
}
}
nextExpand.clear();
}
}
public boolean isInLine(Node parent, Node current){
if(current.equals(parent)){
return true;
}else if(parent.parent != null){
return isInLine(parent.parent,parent);
}else{
return false;
}
}
public void generateSolution(Node goal){
Node cn = goal;
while(cn.parent != null){
solution.addFirst(cn);
cn = cn.parent;
}
solution.addFirst(cn);
}
public void printSolution(){
if(solution != null){
System.out.println("\nAda solusi");
System.out.println("start"+start.toString()+", goal"+goal.toString());
for(Node n : solution){
System.out.print(n.toString());
}
}else{
System.out.println("\nTidak ada solusi");
}
}
}
import java.awt.Point;
import java.util.LinkedList;
public class Map {
int width = 0;
int height = 0;
int[][] map;
public Map(int width, int height){
this.width = width;
this.height = height;
map = new int[width][height];
}
public void printMap(){
for(int j = 0; j < height; j++){
for(int i = 0; i< width; i++){
System.out.print(map[i][j]+"("+i+","+j+") , ");
}
System.out.println();
}
}
public LinkedList<Node> getNextNode(Node n){
Point p = n.idNode;
int xr[] = {1,0,-1,0};
int yr[] = {0,1,0,-1};
LinkedList<Node> list = new LinkedList<Node>();
for(int i = 0; i < 4; i++){
int nx = p.x+xr[i];
int ny = p.y+yr[i];
if((nx >= 0 && nx < width) && (ny >= 0 && ny < height)){
list.add(new Node(new Point(nx,ny)));
}
}
return list;
}
}
import java.awt.Point;
import java.util.LinkedList;
public class Node {
protected Point idNode;
protected Node parent;
protected LinkedList<Node> childs;
public Node(Point idNode){
this.idNode = idNode;
childs = new LinkedList<Node>();
}
public Point getIdNode() {
return idNode;
}
public void setIdNode(Point idNode){
this.idNode = idNode;;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent){
this.parent = parent;
}
public LinkedList<Node> getChilds() {
return childs;
}
public void setChilds(LinkedList<Node> childs) {
this.childs = childs;
}
public void addChild(Node child){
childs.add(child);
child.setParent(this);
}
public boolean equals(Object ob){
if(ob instanceof Node){
if(((Node)ob).idNode.equals(idNode))
return true;
else
return false;
}
return false;
}
public String toString(){
return "("+idNode.x+","+idNode.y+")";
}
}
| Editor Settings | |
|---|---|
| Theme | |
| Key bindings | |
| Full width | |
| Lines |
- More Actions
- Fork Snippet
- Share Snippet