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:

November 27, 2016 at 7:45 am

Reblogged this on Little Stuff.

LikeLike