Let’s talk about Graphs. No, no, not those types of Graphs with the X and Y axises … Software Graphs.

A software graph is any collection of Nodes that also contain edges between some or all Nodes. Programmatically, a graph is a structure consisting of a set of arrays (also called dimensions) and a set of edges.

Let’s see what this looks like as a graphic:



V0 through V5 represent vertices, while 1 through 9 represent edges. As you can imagine, there are arrows containing a direction through the graph – thus we call this type of graph, a directed graph. If the arrows weren’t present, we would call the graph undirected.

It turns out that it’s actually quite simple to represented a graph in programming – and that is to store an array of vertices as well as an array of edges.

vertices = ( V0, V1, V2, V3, V4, V5 );

edges = ( (V0, V1), (V0, V5), (V1, V2), (V2, V3), (V3, V4), (V3, V5), (V4, V0), (V5, V4) );

It’s worth noting again that this graph is directed, therefore the edges are presented using smooth braces. If the graph was undirected, we would represented the edges using curly braces.


Directed: (V0, V1) != (V1, V0)

Undirected: {V0, V1} == {V1, V0}

Additionally, edges may also hold values which make certain paths more ‘costly’ than others. Before we get into how to traverse graphs, how about we build one?

class Vertex{

    // stores the vertex's value
    String value;
    // tells us whether a vertex is visited
    boolean visited = false;

    public Vertex(String value){

        this.value = value;



class Edge{

    // stores the start/end of an edge
    Vertex start;
    Vertex end;
    int value;

    public Edge(Vertex start, Vertex end){

        // we'll just make our edges cost 1 each
        value = 1;

        this.start = start;
        this.end = end;



class Graph{

    // contains our list of vertices
    ArrayList vertices = new ArrayList<>();

    // contains our list of edges
    ArrayList edges = new ArrayList<>();
    boolean directed;

    public Graph(boolean directed){
        this.directed = directed;

    // add a vertex
    public void addVertex(Vertex v){

    // add an edge
    public void addEdge(Vertex start, Vertex end){
        Edge edge = new Edge(start, end);

    // prints out the directional connections of a vertex (edges)
    public void directionalConnections(Vertex v){

        for(Edge e: edges){
            if(e.start == v){
                System.out.println("There is a connection between " + e.start.value + " and " + e.end.value);


    // prints out the un-directional connections of a vertex (edges)
    public void undirectionalConnections(Vertex v){

        for(Edge e: edges){
            if(e.start == v || e.end == v){
                System.out.println("There is a connection between " + e.start.value + " and " + e.end.value);



public class Main {

    public static void main(String [] args){
        Graph graph = new Graph(true);

        // create the vertices in the form of cities
        Vertex v0 = new Vertex("V0");
        Vertex v1 = new Vertex("V1");
        Vertex v2 = new Vertex("V2");
        Vertex v3 = new Vertex("V3");
        Vertex v4 = new Vertex("V4");
        Vertex v5 = new Vertex("V5");

        // add them to our vertices array

        // add the edges
        graph.addEdge(v0, v1);
        graph.addEdge(v0, v5);
        graph.addEdge(v1, v2);
        graph.addEdge(v2, v3);
        graph.addEdge(v3, v4);
        graph.addEdge(v3, v5);
        graph.addEdge(v4, v0);
        graph.addEdge(v5, v4);



Now that we have some basis of how to model a graph in code, let’s take a look at how to traverse a graph (search for items). The two standard ways are: Depth First Search and Breadth First Search.


Depth First Search (uses a Stack)

In depth first search, we traverse the graph from a starting vertex and then continue to explore along continuous edges until we hit a vertex with no adjacent vertices. After which, we backtrack a little and then attempt to find a new path. If no new paths can be found, we’ve successfully visited all of the edges. Let’s take a look at how we do this:

    public void depthFirstSearch(Vertex start){

        Stack stack = new Stack<>();

        // focusNode is where we're currently at
        Vertex focusNode;

        // mark the start as visisted
        start.visisted = true;

        // push the start onto the stack


        // while there's stuff in our stack

            // set the focusNode to the top value in the stack
            focusNode = stack.peek();

            // initialize our boolean, which tells us
            // if a valid edge is found for that focusNode
            // to be false
            boolean foundPath = false;

            // get the next vertex
            for(Edge e: edges){

                // if the start of the edge is the focusNode
                // and the end of that edge is not visited
                if(e.start == focusNode && e.end.visisted == false){

                    // tell the system we found a path
                    foundPath = true;

                    // mark the end node as visited
                    e.end.visisted = true;

                    // push it onto the stack

                    // set the new focusNode equal to the end
                    focusNode = e.end;



            // if no path was found,
            // pop the top off of the stack
            // and continue with the item below
            if(foundPath == false){




Breadth First Search (uses a Queue)


    public void breadthFirstSearch(Vertex start){

        Vertex focusNode = start;

        Queue queue = new LinkedList();

        focusNode.visisted = true;

            boolean foundPath = false;
            for(Edge e: edges){

                if(e.start == focusNode && e.end.visisted != true){
                    e.end.visisted = true;
                    foundPath = true;

            if(foundPath == false){
                focusNode = queue.peek();




The difference between the two is that one, we use a Queue and two, we set the focusNode outside of the edge loop. As you recall, DFS keeps going until it hits a dead end across one line of nodes – whereas BFS searches all of one nodes connections before moving on and doing the same to the next one.


Here is a video explaining Depth First Search and Breadth First Search: