Graph implementation using adjacency lists (finished).

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 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);
    }
}

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.