import java.util.ArrayList;
public class BfsData
{
// Graph adjacency matrix (unweighted graph)
static private int[][] graph = { {0,3,0,0,2}, // 0->1 0->3
{0,0,0,33,0}, // 1->2, 1->3
{0,0,0,22,0}, // 2->4
{0,0,0,0,3}, // 3->2, 3->4
{0,0,0,0,0} // 4->1
};
//--------------------------------------------------------------
public static void main (String[] args)
{
ArrayList<Integer> Start = new ArrayList();
Start.add(0); // The start node
ArrayList<ArrayList> Queue = new ArrayList();
Queue.add(Start); // inserted in the initial queue of paths as [[Start]]
// Use one search at a time (comment the others)
// ArrayList Path = depth_first(Queue,4); // Depth first search
ArrayList Path = breadth_first(Queue,4); // Breadth first search
// ArrayList Path = uni_cost(Queue,4); // Uniform cost search
System.out.println(Path);
// System.out.println(path_cost(Path));
}
//--------------------------------------------------------------
// Adds to the queue paths extending the first path in the queue
public static ArrayList<ArrayList> extend (ArrayList<Integer> Path)
{
ArrayList<ArrayList> NewPaths = new ArrayList();
for (int i=0;i<graph.length;i++)
if (graph[Path.get(0)][i]>0 && !Path.contains(i))
{
ArrayList Path1 = (ArrayList)Path.clone();
System.out.println(Path1+"=====jjjj====");
Path1.add(0,i);
NewPaths.add(Path1);
System.out.println(NewPaths+"====NewPaths==");
}
return NewPaths;
}
//--------------------------------------------------------------
// Appends y to x and returns the result in a new ArrayList z
public static ArrayList append (ArrayList x, ArrayList y)
{
ArrayList z = (ArrayList)x.clone();
for (int i=0;i<y.size();i++) z.add(y.get(i));
return z;
}
//--------------------------------------------------------------
// Breadth first search for a path from Start to Goal.
// The Start node must be in the initial queue of paths as [[Start]]
public static ArrayList<ArrayList> breadth_first(ArrayList<ArrayList> Queue, int Goal)
{
if (Queue.size()==0) return Queue; // path not found
if ((Integer)Queue.get(0).get(0) == Goal) // if Goal is the first node in the first path
return Queue.get(0); // return path
else // replace the first path with all its extensions and put them at the end of the queue
{
ArrayList<ArrayList> NewPaths = extend(Queue.get(0));
Queue.remove(0);
return breadth_first(append(Queue,NewPaths),Goal);
}
}
//--------------------------------------------------------------
public static int path_cost (ArrayList<Integer> Path)
{
int cost = 0;
for (int i=0;i<Path.size()-1;i++)
cost = cost + graph[Path.get(i+1)][Path.get(i)];
return cost;
}
public static void sort(ArrayList<ArrayList> Queue)
{
int out, in;
for(out=Queue.size()-1; out>=1; out--)
for(in=0; in<out; in++)
if( path_cost(Queue.get(in)) > path_cost(Queue.get(in+1)) )
swap(Queue, in, in+1);
}
//--------------------------------------------------------------
private static void swap(ArrayList<ArrayList> a, int one, int two)
{
ArrayList<Integer> temp = a.get(one);
a.set(one,a.get(two));
a.set(two,temp);
}
}
As Above program, in that place i will directly send the adjacent matrix file through file reader, that file is
a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad
a 0 3 0 0 2 1 0 0 0 2 0 0 42 1 0 0 11 0 6 0 0 0 0 43 0 36 0 23 0 24
b 0 0 0 33 0 25 0 36 0 0 0 3 24 0 2 0 0 47 0 0 8 3 0 17 0 0 0 0 4 20
c 0 0 0 22 0 12 16 0 34 0 0 7 0 2 0 0 0 0 0 16 0 13 0 0 0 25 0 0 0 10
d 0 0 0 0 3 4 0 0 0 0 5 12 8 0 0 0 2 12 0 0 3 0 0 24 32 0 0 0 0 0
e 0 0 0 0 0 0 1 4 0 12 0 20 0 0 0 0 13 0 1 16 0 0 0 0 2 4 5 6 0 0
f 0 0 0 0 0 0 1 0 2 0 13 8 0 0 1 0 4 0 0 8 0 0 0 12 1 0 0 0 1 0
g 0 0 0 0 0 0 0 1 12 0 3 5 0 2 0 3 0 0 1 2 0 0 0 5 10 0 1 2 1 0
h 0 0 0 0 0 0 0 0 3 34 5 0 0 0 0 0 1 12 1 0 0 0 0 0 2 0 3 0 1 0
i 0 0 0 0 0 0 0 0 0 1 2 0 0 42 0 1 5 34 1 0 0 1 0 0 0 0 0 1 0 0
j 0 0 0 0 0 0 0 0 0 0 0 1 22 0 11 0 25 41 0 0 0 0 0 0 0 1 0 1 0 4
k 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 23 0 12 0 2 0 3 0 1 0 0 1 1
l 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 19 12 0 0 1 0 0 0 0 2 0 4 0 2 0
m 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 5 1 0 0 0 0 3 0 2 0 0 0 0 0 0
n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 23 0 5 32 0 50 0 1 0 3 4
o 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 0 0 2 53 0 2 21 3 0 0 0 1
p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 24 0 0 12 38 0 2 0 0
q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 24 0 0 24 0 0 12 0 5 0 0 0
r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 12 0 57 0 0 2 0
s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 24 0 1 0 5 12 0
t 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 24 1 6 0 0 1
u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 1 0 0
v 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 22 1 1 4 0
w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 38 0 0 5 7 0
x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 5 0 1
y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 21 0 1
z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1
aa 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42 0 0
ab 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0
ac 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
ad 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
"" static private int[][] graph = { {0,3,0,0,2}, // 0->1 0->3
{0,0,0,33,0}, // 1->2, 1->3
{0,0,0,22,0}, // 2->4
{0,0,0,0,3}, // 3->2, 3->4
{0,0,0,0,0} // 4->1
};"" ....in that ""---"" i will set that above matrix file ?how to set that file??
No comments:
Post a Comment