Best First Search: Graphs

package graphs;
import java.util.*;
import graphs.State;
public class GraphImplementation
{
public void dfs(Node root)
{
//Avoid infinite loops
if(root == null) return;

System.out.print(root.getVertex() + “\t”);
root.state = State.Visited;

//for every child
for(Node n: root.getChild())
{
//if childs state is not visited then recurse
if(n.state == State.Unvisited)
{
dfs(n);
}
}
}

public void bfs(Node root)
{
//Since queue is a interface
Queue<Node> queue = new LinkedList<Node>();

if(root == null) return;

root.state = State.Visited;
//Adds to end of queue
queue.add(root);

while(!queue.isEmpty())
{
//removes from front of queue
Node r = queue.remove();
System.out.print(r.getVertex() + “\t”);

//Visit child first before grandchild
for(Node n: r.getChild())
{
if(n.state == State.Unvisited)
{
queue.add(n);
n.state = State.Visited;
}
}
}
}

public static Graphs createNewGraph()
{
Graphs g = new Graphs();
Node[] temp = new Node[8];

temp[0] = new Node(“S”, 2);
temp[1] = new Node(“A”, 3);
temp[2] = new Node(“D”, 3);
temp[3] = new Node(“B”, 3);
temp[4] = new Node(“E”, 3);
temp[5] = new Node(“F”, 2);
temp[6] = new Node(“G”, 1);
temp[7] = new Node(“C”, 1);
//S = 0
temp[0].addChildNode(temp[1]);
temp[0].addChildNode(temp[2]);
//A = 1
temp[1].addChildNode(temp[0]);
temp[1].addChildNode(temp[2]);
temp[1].addChildNode(temp[3]);
//D = 2
temp[2].addChildNode(temp[0]);
temp[2].addChildNode(temp[4]);
temp[2].addChildNode(temp[1]);
//B = 3
temp[3].addChildNode(temp[4]);
temp[3].addChildNode(temp[7]);
temp[3].addChildNode(temp[1]);
//E = 4
temp[4].addChildNode(temp[5]);
temp[4].addChildNode(temp[2]);
temp[4].addChildNode(temp[3]);
//F = 5
temp[5].addChildNode(temp[4]);
temp[5].addChildNode(temp[6]);
//G = 6
temp[6].addChildNode(temp[5]);
//C = 7
temp[7].addChildNode(temp[3]);

for (int i = 0; i < 8; i++)
{
g.addNode(temp[i]);
}
return g;
}

public static void main(String[] args) {

Graphs gDfs = createNewGraph();
GraphImplementation s = new GraphImplementation();

System.out.println(“—————DFS—————“);
s.dfs(gDfs.getNode()[0]);
System.out.println();
System.out.println();
Graphs gBfs = createNewGraph();
System.out.println(“—————BFS—————“);
s.bfs(gBfs.getNode()[0]);

}

}

package graphs;

public class Graphs {

public int count; // num of vertices
private Node vertices[];

public Graphs()
{
vertices = new Node[8];
count = 0;
}

public void addNode(Node n)
{
if(count < 10)
{
vertices[count] = n;
count++;
}
else
{
System.out.println(“graph full”);
}
}

public Node[] getNode()
{
return vertices;
}
}

package graphs;
public class Node {

public Node[] child;
public int childCount;
private String vertex;
public State state;

public Node(String vertex)
{
this.vertex = vertex;
}

public Node(String vertex, int childlen)
{
this.vertex = vertex;
childCount = 0;
child = new Node[childlen];
}

public void addChildNode(Node adj)
{
adj.state = State.Unvisited;
if(childCount < 30)
{
this.child[childCount] = adj;
childCount++;
}
}

public Node[] getChild()
{
return child;
}

public String getVertex()
{
return vertex;
}

}

public enum State {

Unvisited,Visiting,Visited;
}