import
java.util.*;
class Node {
int no;
String name;
Node left;
Node right;
boolean hasleft;
boolean hasright;
float Hn, Gn, Fn;
}
public class BFS {
public static void main(String
args[]) {
Scanner sc = new
Scanner(System.in);
LinkedList open = new
LinkedList();
LinkedList close = new
LinkedList();
LinkedList track = new
LinkedList();
int n, i, k, j;
String goal, ch;
System.out.println("Enter
number of nodes:");
n = sc.nextInt();
Node nd[] = new Node[n];
for(i=0, k=0;i<n-1;k++)
{
if(i==0) {
nd[i] = new
Node();
System.out.println("Enter
ROOT node");
nd[i].name
= sc.next();
nd[i].no =
i;
}
System.out.println(nd[k].name
+ " Has Left Child? (y/n)");
ch = sc.next();
if(ch.charAt(0)=='y'
|| ch.charAt(0)=='Y') {
i++;
nd[i] = new
Node();
System.out.println("Enter
Child nodes:");
nd[i].name
= sc.next();
nd[i].no =
i;
nd[k].left
= nd[i];
nd[k].hasleft
= true;
}
System.out.println(nd[k].name
+ " Has Right Child? (y/n)");
ch =
sc.next();
if(ch.charAt(0)=='y'
|| ch.charAt(0)=='Y') {
i++;
nd[i]
= new Node();
System.out.println("Enter
Child nodes:");
nd[i].name
= sc.next();
nd[i].no
= i;
nd[k].right
= nd[i];
nd[k].hasright
= true;
}
}
System.out.println("Enter
Goal State:");
goal = sc.next();
for(i=0;i<n;i++) {
if(i==0) {
open.add(nd[i].name);
track.add(nd[i].no);
}
System.out.println((i+1)+".\n"+
"OPEN: "+open+"\t\t X = "+open.getFirst()+"\nCLOSE: "+close);
if(goal.equals(open.getFirst()))
{
System.out.println("GOAL
STATE "+open.getFirst()+" found");
break;
}
else {
close.add(open.getFirst());
open.removeFirst();
int g =
(int)track.getFirst();
track.removeFirst();
if(nd[g].hasleft==true
&& nd[g].hasright==true) {
open.add(nd[i].left.name);open.add(nd[i].right.name);
track.add(nd[i].left.no);track.add(nd[i].right.no);
}
else
if(nd[g].hasleft==true && nd[g].hasright==false) {
open.add(nd[i].left.name);track.add(nd[i].left.no);
}
else
if(nd[g].hasleft==false && nd[g].hasright==true) {
open.add(nd[i].right.name);track.add(nd[i].right.no);
}
}
if(open.isEmpty()==true)
{
System.out.println((i+1)+".\n"+
"OPEN: "+open+"\nCLOSE: "+close);
System.out.println("GOAL STATE
"+goal+" not found");
}}
}
}
OUTPUT:
Enter number of nodes:
5
Enter ROOT node
A
A Has Left Child? (y/n)
y
Enter Child nodes:
B
A Has Right Child? (y/n)
y
Enter Child nodes:
C
B Has Left Child? (y/n)
y
Enter Child nodes:
D
B Has Right Child? (y/n)
y
Enter Child nodes:
E
Enter Goal State:
E
1.
OPEN: [A] X = A
CLOSE: []
2.
OPEN: [B, C] X = B
CLOSE: [A]
3.
OPEN: [C, D, E] X = C
CLOSE: [A, B]
4.
OPEN: [D, E] X = D
CLOSE: [A, B, C]
5.
OPEN: [E] X = E
CLOSE: [A, B, C, D]
GOAL STATE E found
--------------------------------------------------------------------------------------------------------------------------
Enter number of nodes:
3
Enter ROOT node
A
A Has Left Child? (y/n)
y
Enter Child nodes:
B
A Has Right Child? (y/n)
y
Enter Child nodes:
C
Enter Goal State:
D
1.
OPEN: [A] X = A
CLOSE: []
2.
OPEN: [B, C] X = B
CLOSE: [A]
3.
OPEN: [C] X = C
CLOSE: [A, B]
4.
OPEN: []
CLOSE: [A, B, C]
GOAL STATE D not found
0 comments:
Post a Comment