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.

Therefore:

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
    // MAY NOT BE DIRECTIONAL
    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){
        vertices.add(v);
    }

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

    // 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
        graph.addVertex(v0);
        graph.addVertex(v1);
        graph.addVertex(v2);
        graph.addVertex(v3);
        graph.addVertex(v4);
        graph.addVertex(v5);

        // 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
        stack.push(start);

        System.out.println(start.value);

        // while there's stuff in our stack
        while(!stack.isEmpty()){

            // 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
                    stack.push(e.end);

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

                    System.out.println(focusNode.value);
                    break;
                }

            }

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

    }

 

 

Breadth First Search (uses a Queue)

 

    public void breadthFirstSearch(Vertex start){

        Vertex focusNode = start;

        Queue queue = new LinkedList();

        focusNode.visisted = true;
        queue.add(focusNode);



        while(!queue.isEmpty()){
            boolean foundPath = false;
            for(Edge e: edges){

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

            }
 
            // SET THE FOCUS NODE HERE AS THE NEXT QUEUE'D ITEM
            if(foundPath == false){
                System.out.println(queue.remove().value);
                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:

Advertisements