Updated with BFT and DFT methods Graph implementation using adjacency lists. Graph.java updated: the two traversal methods are added. TestGraphs.java has been updated to call BFT and DFT. You need IntQueue and IntStack classes for this program. You can use IntQueue implementation with linked lists and this IntStack implementation.

public class Graph {
    private Vertex [] vertices;
    private boolean directed; // true if the graph is directed

    public Graph(int n, boolean directed) {
	vertices = new Vertex [n];
	this.directed = directed;
	for (int i = 0; i < n; ++i) {
	    vertices[i] = new Vertex(i);
	}
    }

    public void setEdges(int [] startPoints, int [] endPoints) {
	if (startPoints.length != endPoints.length) {
	    throw new RuntimeException ("Invalid edges data");
	}
	if (directed) {
	    for (int i = 0 ; i < startPoints.length; ++i) {
		vertices[startPoints[i]].addEdge(vertices[endPoints[i]]);
	    }
	} else {
	    // need to set both directions
	    for (int i = 0 ; i < startPoints.length; ++i) {
		vertices[startPoints[i]].addEdge(vertices[endPoints[i]]);
		vertices[endPoints[i]].addEdge(vertices[startPoints[i]]);
	    }
	}
    }

    public String toString() {
	String toPrint = "";
	for (int i = 0; i < vertices.length; ++i) {
	    toPrint += "vertex " + vertices[i].getId();
	    toPrint += " Connected to:"; 
	    VertexNode current = vertices[i].getEdges();
	    while (current != null) {
		toPrint += " " +  current.getLink().getId();
		current = current.getNext();
	    }
	    toPrint += "\n";
	}
	return toPrint;
    }
    
    public void BFT() {
	// the array holds distances from the starting vertex
	int [] distances = new int [vertices.length];
	// -1 stands for infinity
	for (int i = 0; i < distances.length; ++i ) {
	    distances[i] = -1;
	}
	IntQueue queue = new IntQueue();
	
	queue.enqueue(0);
	distances[0]=0;
	
	while(!queue.isEmpty()){
	    int n=queue.dequeue();
	    VertexNode v = vertices[n].getEdges();
	    while (v != null) {
		int x = v.getLink().getId();
		if(distances[x] == -1) {
		    queue.enqueue(x);
		    distances[x] = distances[n]+1;
		}
		v = v.getNext();
		
	    }
	}
	
	// print out the distances from vertex 0 to each vertex
	for (int i = 0; i < distances.length; ++i) {
	    System.out.println("vertex: " + i + " distance: " + distances[i]);
	}
    }

    public void DFT() {
	// the array holds distances from the starting vertex
	int [] distances = new int [vertices.length];
	// -1 stands for infinity
	for (int i = 0; i < distances.length; ++i ) {
	    distances[i] = -1;
	}
	IntStack stack = new IntStack();
	
	stack.push(0);
	distances[0]=0;
	
	while(!stack.isEmpty()){
	    int n = stack.pop();
	    VertexNode v = vertices[n].getEdges();
	    while (v != null) {
		int x = v.getLink().getId();
		if(distances[x] == -1) {
		    stack.push(x);
		    distances[x] = distances[n]+1;
		}
		v = v.getNext();
		
	    }
	}
	
	// print out the distances from vertex 0 to each vertex
	for (int i = 0; i < distances.length; ++i) {
	    System.out.println("vertex: " + i + " distance: " + distances[i]);
	}
    }
}



public class VertexNode {
    private Vertex linkTo;
    private VertexNode next;

    public VertexNode(Vertex linkTo, VertexNode next) {
	this.linkTo = linkTo;
	this.next = next;
    }

    public Vertex search(Vertex v) {
	VertexNode current = this;
	while (current != null) {
	    if (current.linkTo.equals(v)) {
		return v;
	    }
	}
	return null;
    }

    public Vertex getLink() {
	return linkTo;
    }
    
    public VertexNode getNext() {
	return next;
    }
}



public class Vertex {
    private int id;
    private VertexNode edges;

    public Vertex(int id) {
	this.id = id;
    }

    public void addEdge(Vertex v) {
	VertexNode vn = new VertexNode(v,edges);
	edges = vn;
    }

    public boolean equals(Object o) {
	Vertex v = (Vertex) o;
	if (v.id == this.id) {
	        return true;
	}
	return false;
    }

    public int getId() {
	return id;
    }

    public VertexNode getEdges() {
	return edges;
    }
}

Updated TestGraphs method

public class TestGraphs {
    public static void main(String [] args) {
	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("BFT:");
	g.BFT();
	System.out.println("DFT:");
	g.DFT();
    }
}


This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.