Graph implementation with BFS and DFS methods. Note that you need IntQueue.class and IntStack.class.
public class Graph {
// instance variables go here:
private boolean isDirected;
private Vertex [] vertices;
// constructor: n is the number of vertices,
// directed is a boolean which is true if the graph is directed,
// false otherwise
public Graph(int n, boolean directed) {
isDirected = directed;
vertices = new Vertex[n];
for (int i = 0; i < n; ++i) {
vertices[i] = new Vertex();
}
}
// startPoints are the starting points of edges, endPoints are the
// ending points
public void setEdges(int [] startPoints, int [] endPoints)
throws GraphException {
if (startPoints.length != endPoints.length)
throw new GraphException("invalid egdes data");
// adding edges to the graph
for (int i = 0; i < startPoints.length; ++i) {
// checking if vertices with these numbers exist
if (startPoints[i] >= vertices.length)
throw new GraphException("invalid starting vertex");
if (endPoints[i] >= vertices.length)
throw new GraphException("invalid ending vertex");
// adding the edge
vertices[startPoints[i]].addEdge(endPoints[i]);
// adding back edge for undirected graph
if (!isDirected) {
vertices[endPoints[i]].addEdge(startPoints[i]);
}
}
}
public String toString() {
String s = "";
for (int i=0; i < vertices.length; ++i) {
s += i+": ";
Edge edge = vertices[i].getFirst();
while (edge != null) {
s += edge.getEndPoint() + " ";
edge = edge.getNext();
}
s += '\n';
}
return s;
}
public void BFS() {
IntQueue q = new IntQueue();
int [] distances = new int[vertices.length];
for (int i = 0; i < distances.length; ++i) {
distances[i] = -1;
}
q.enqueue(0);
distances[0] = 0;
while (!q.isEmpty()) {
int v = q.dequeue();
Edge edge = vertices[v].getFirst();
while (edge != null) {
if (distances[edge.getEndPoint()] == -1) {
q.enqueue(edge.getEndPoint());
distances[edge.getEndPoint()] = distances[v] + 1;
}
edge = edge.getNext();
}
}
for (int i = 0; i < vertices.length; ++i) {
System.out.println("distance from 0 to " + i + " is " + distances[i]);
}
}
public void DFS() {
IntStack s = new IntStack();
int [] pathLength = new int[vertices.length];
for (int i = 0; i < pathLength.length; ++i) {
pathLength[i] = -1;
}
s.push(0);
pathLength[0] = 0;
while (!s.isEmpty()) {
int v = s.pop();
Edge edge = vertices[v].getFirst();
while (edge != null) {
if (pathLength[edge.getEndPoint()] == -1) {
s.push(edge.getEndPoint());
pathLength[edge.getEndPoint()] = pathLength[v] + 1;
}
edge = edge.getNext();
}
}
for (int i = 0; i < vertices.length; ++i) {
System.out.println("the length of DFS path from 0 to " + i + " is " + pathLength[i]);
}
}
}
public class Vertex {
private Edge edges;
public void addEdge(int endPoint) {
Edge edge = new Edge(endPoint);
edge.setNext(edges);
edges = edge;
}
public Edge getFirst() {
return edges;
}
}
public class Edge {
private int endPoint;
private Edge next;
public Edge(int endPoint) {
this.endPoint = endPoint;
}
public void setNext(Edge edge) {
next = edge;
}
public Edge getNext() {
return next;
}
public int getEndPoint() {
return endPoint;
}
}
public class GraphException extends Exception {
public GraphException(String s) {
super(s);
}
}
Testing code for a graph:
public class TestGraphs {
public static void main(String [] args) throws GraphException {
Graph g = new Graph(10,false); // undirected graph
int [] starts = {0, 6, 3, 4, 2, 3, 5, 7, 8, 0, 9, 1};
int [] ends = {1, 2, 0, 7, 3, 1, 2, 5, 6, 8, 4, 9};
g.setEdges(starts, ends);
System.out.println(g);
System.out.println("Breadth first search");
g.BFS();
System.out.println("Depth first search");
g.DFS();
}
}
This is an example from CSci 2101 course.