[Intermediate] Generic Un-directed Graph Implementation with Depth-First Search

Generic Un-directed Graph Implementation with Depth-First Search

A Graph is a data structure that is a mathematical model that has tons of real-world uses.

We use a Depth-First Search here to see if the Edges are 'connected'.

Here is a simple implementation in Java that could be extended to include other elements such as Breadth-First Search, Shortest Path, etc.

// Generic Un-directed Graph Implementation with Depth-First Search
// by [u/Philboyd_Studge](/u/Philboyd_Studge)

import java.util.ArrayList;

@SuppressWarnings("unchecked")

public class Graph<T extends Comparable<T>>
{
	// an enum for the three stated used by the Depth first search
	public enum State { UNVISITED, VISITED, COMPLETE };

	// a list to hold all the vertices
	private ArrayList<Vertex> vertexList;

	// list to hold the edges 
	// not really used for anything
	// but display purposes
	private ArrayList<Edge> edgeList;

	public Graph()
	{
		vertexList = new ArrayList<>();
		edgeList = new ArrayList<>();
	}


	public void add(T x, T y)
	{
		Edge e = new Edge(x, y);
		edgeList.add(e);
	}

	public Vertex findVertex(T v)
	{
		for (Vertex each : vertexList)
		{
			if (each.getValue().compareTo(v)==0)
				return each;
		}
		return null;
	}

	public String toString()
	{
		String retval = "";
		for (Vertex each : vertexList)
		{
			retval += each.toString() + "\n";
		}
		return retval;
	}

	public String edgesToString()
	{
		String retval = "";
		for (Edge each : edgeList)
		{
			retval += each;
		}
		return retval;
	}

	// get first node and call recursive method
	// check if is graph is connected
	public boolean DepthFirstSearch()
	{
		if (vertexList.isEmpty()) return false;

		// get first node
		Vertex root = vertexList.get(0);
		if (root==null) return false;

		// call recursive function
		DepthFirstSearch(root);
		return isConnected();
	}

	// recurse through nodes
	private void DepthFirstSearch(Vertex v)
	{
		v.setState(State.VISITED);

		// loop through neighbors
		for (Vertex each : v.getAdjacentList())
		{
			if (each.getState()==State.UNVISITED)
			{
				DepthFirstSearch(each);
			}
		}
		v.setState(State.COMPLETE);
	}

	// test if DFS returned a connected graph
	public boolean isConnected()
	{
		for (Vertex each : vertexList)
		{
			if (each.getState() != State.COMPLETE)
				return false;
		}
		return true;
	}

	// vertex class
	class Vertex
	{
		T value;
		ArrayList<Vertex> adjacent;
		State state;

		public Vertex(T v)
		{
			value = v;
			adjacent = new ArrayList<>();
			state = State.UNVISITED;
		}

		public State getState()
		{
			return state;
		}

		public void setState(State s)
		{
			state = s;
		}

		public T getValue()
		{
			return value;
		}

		public void addNeighbor(Vertex n)
		{
			adjacent.add(n);
		}

		public ArrayList<Vertex> getAdjacentList()
		{
			return adjacent;
		}

		public String toString()
		{
			String retval = "";
			retval += "Vertex: " + value + ":";
			for (Vertex each : adjacent)
			{
				retval += each.getValue() + " ";
			}
			return retval;
		}


	}

	// edge class
	class Edge
	{
		private Vertex x;
		private Vertex y;

		public Edge(T v1, T v2)
		{
			// check to see if first vertex exists
			x = findVertex(v1);
			if (x == null) 
			{
				// doesn't exist, add new
				x = new Vertex(v1);
				// and add to master list
				vertexList.add(x);
			}
			// same for second vertex
			y = findVertex(v2);
			if (y == null) 
			{
				y = new Vertex(v2);
				vertexList.add(y);
			}
			// add each vertex to the adjacent list for the other
			x.addNeighbor(y);
			y.addNeighbor(x);

		}


		public String toString()
		{
			return "Edge X:" + x.getValue() + " Y:" + y.getValue() + "\n";
		}


	}

	public static void main(String[] args) {
		Graph g = new Graph();
		System.out.println(g.DepthFirstSearch());
		g.add(0,1);
		g.add(0,2);
		g.add(1,3);
		g.add(2,3);
		g.add(2,4);
		g.add(3,5);
		g.add(3,6);
		g.add(5,6);


		System.out.println(g);
		System.out.println(g.edgesToString());
		System.out.println("Graph is connected: " + g.DepthFirstSearch());
		System.out.println();

		g.add(7,3);
		
		System.out.println(g);
		System.out.println(g.edgesToString());
		System.out.println("Graph is connected: " + g.DepthFirstSearch());
		System.out.println();

		Graph<String> gString = new Graph<>();
		gString.add("apple","fruit");
		gString.add("orange","fruit");
		gString.add("broccoli","vegetable");
		gString.add("beef","meat");
		gString.add("meat","food");
		gString.add("fruit","food");
		gString.add("vegetable","food");

		System.out.println(gString);
		System.out.println(gString.edgesToString());
		System.out.println("Graph is conected: " + gString.DepthFirstSearch());

	}
}

Output

false
Vertex: 0:1 2
Vertex: 1:0 3
Vertex: 2:0 3 4
Vertex: 3:1 2 5 6
Vertex: 4:2
Vertex: 5:3 6
Vertex: 6:3 5

Edge X:0 Y:1
Edge X:0 Y:2
Edge X:1 Y:3
Edge X:2 Y:3
Edge X:2 Y:4
Edge X:3 Y:5
Edge X:3 Y:6
Edge X:5 Y:6

Graph is connected: true

Vertex: 0:1 2
Vertex: 1:0 3
Vertex: 2:0 3 4
Vertex: 3:1 2 5 6 7
Vertex: 4:2
Vertex: 5:3 6
Vertex: 6:3 5
Vertex: 7:3

Edge X:0 Y:1
Edge X:0 Y:2
Edge X:1 Y:3
Edge X:2 Y:3
Edge X:2 Y:4
Edge X:3 Y:5
Edge X:3 Y:6
Edge X:5 Y:6
Edge X:7 Y:3

Graph is connected: false

Vertex: apple:fruit
Vertex: fruit:apple orange food
Vertex: orange:fruit
Vertex: broccoli:vegetable
Vertex: vegetable:broccoli food
Vertex: beef:meat
Vertex: meat:beef food
Vertex: food:meat fruit vegetable

Edge X:apple Y:fruit
Edge X:orange Y:fruit
Edge X:broccoli Y:vegetable
Edge X:beef Y:meat
Edge X:meat Y:food
Edge X:fruit Y:food
Edge X:vegetable Y:food

Graph is conected: true