## DEV Community is a community of 880,569 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Altoneisha Rose

Posted on • Updated on

# Graphs

Today we will be talking about the two ways we can search through the graph data structure. First a rephresher on graphs. Graphs are used to describe a model that shows the route from one node to another node. Graphs consist of multiple nodes connected in between by edges.
Unlike trees, graphs are not hierarchical. There is no parent nodes, just nodes with relationships between other nodes. Graphs can be undirected, which means that the relationship of any 2 nodes connected by an edge is a symmetrical relationship. Graphs can alternatively be directed, which means there is an asymmetrical relationship between nodes that are connected by an edge. In the image below, fig 1 is undirected meaning it has no direction to an edge, while figure two has direction to the edge. Now we will explore the differnce bewtween the search methods.

Depth First Search(DFS)

The first method we will talk about is Depth First Search. DFS is a recursive algorithm for searching all the vertices of a graph. DFS uses stacks in its implementation. This search method takes the scenic-route deep through the nodes. the search will start off at the first node and transverse down through the connecting edges all the way to the node that have no child attached or end node, then it will travese its way back up until it finds a new path to get to the end.

In the image above we will start off at node 0 and jump to node three then from node three to node one then to node 6 and so on.

With this method if we were looking for node 4 it would take a while to find because of the algorithm it uses to search. Because this graph has a property of being cyclical, meaning it can be routed back to a node it already visited, we can implement a storage for all of the nodes it visits.

In the image above we have a call stack of the path the graph takes in its execution. Once it reaches the end of a node it will use this call stack to traverse its way back up to find a new path to the end.

With the stack array above we will have the value set to a boolean so that everytime we vist a node we will set the node value equal to true. this helps to stop our graph from going back to the same node twice in its search and slowing down our code. A non-recurssive code implementation could look like this.