Intro To The Graph Data Structure

A real world problem solved through graph algorithms

In todays article, we’ll take a dive in to learning more about graphs and their implementation to solving real world problems. Some common examples of situations where you can use graphs are: social network(friends of friends), page recommendations(based on most popular search), the study of molecules in chemistry and physics, transportation networks, and etc.

Things to know about graphs

Parts of a graph
1. Vertices(nodes) — Where data is stored.
2. Edges(connections) — Connects 2 different vertices together. And they can also go in one direction. Which creates what’s called directed graphs or digraphs. Additionally, these edges can have weights.

Types of graphs
1. Undirected — Vertices on both sides of the edges have connection to each other and you can see that the relationship goes both ways.
2. Directed — Vertices on both sides of the edges have connection to each other. But the connection only goes one way(either from the first vertex to the second vertex, or otherwise).
3. Weighted — Branches that have a numerical weight.

Properties of a graph
These properties define the graph itself, and is not a specific drawing of the graph. Here are some examples of graph properties.
1. Path — A sequence of vertices where they are adjacent to the vertex next to it
2. Coloring — An assignment of different colors to all vertices so the vertex at the end of each edge has a unique color
3. Degree — The number of edges that point out of the vertex
4. Weight — The value attached on its edges.
5. Diameter — The longest shortest path of that graph
6. Connected graph — When a graph has at least 1 vertex and there is a path between all vertices

Problems that can be solved
Here are a set of problems that can be questioned and solved in a graph model
1.Verification — Do these vertices form a path?
2. Existence — Is there a path in this graph?, Is there a path of length n?
3. Instance — Find a path from source vertex to distance vertex.
4. Enumeration — How many paths of length n exists in this graph?
5. Optimization — What is the longest path?, What is the shortest path?

Before heading in to solving a real world problem using graphs, I want to introduce algorithms that are very common and you will most likely be using or even get asked in some technical interviews.

Graph Algorithms

Breadth First Search (BFS)
BFS is a way to traverse through the graph in an order where it’s closest to the root vertex. In an iterative approach, we use a Queue data structure to keep track of each step in the traversals.

Below is a representation of running bfs on a graph. The list of order call orders from the first vertex visited, to the last vertex visited.

Graph problems that can be solved using the BFS algorithm:
• Finding a path from a vertex to another
• Finding the minimum path from a vertex to another
• Finding all the paths from a vertex to another
• Finding a minimum spanning tree of an unweighted graph

Depth First Search (DFS)
DFS is a way to traverse through the graph in a way where it tries to go farthest from the root vertex. DFS requires to use a Stack data structure so we go furthest away from the vertex instead of a level search like the bfs algorithm.

Below is a representation of running dfs on a graph. The list of order call orders from the first vertex visited, to the last vertex visited.

Graph problems that can be solved using the DFS algorithm:
• Proving that a graph is connected
• Finding if there are existing paths within the graph
• Checking if a graph is bipartite (A graph is bipartite when the vertices can be divided into 2 independent sets and all the edges from one of the set connect to the other. Or we can also say a bipartite graph will not contain any odd length cycles.)

Prim’s Algorithm
Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree in a weighted undirected graph. The algorithm builds up a tree one vertex at a time choosing its minimal weight of a vertex in each step.

Dijkstra’s Algorithm
Dijkstra’s algorithm is another greedy algorithm that that finds the shortest path between vertices in a graph. The algorithm finds the shortest path between the given vertex and every other connecting vertex to it. We can also optimize the run time of this algorithm by using a priority queue. This reduces the time of looking up the vertex that has the least distance.

Sample Real World Implementation

We’re going to examine graph theory application on Apple Map Routes. Have you ever noticed that out of thousands of routes you can take from getting from one location to another, Apple maps, or any other online map, will chose to take the shortest path.
However, The map applications we use have much more values to account for apart from its distance, such as traffic, or road blockage during specific times in a day.

We are going to solve these common problems in this sample project:
1. Checking if there is a path from location A to location B
2. Finding the fastest route from location A to location B
3. Seeing how many places we can travel to based on our starting location

Let’s start off by creating a graph and vertex class to handle our calculations. You can follow this link to get to my GitHub repository for this project!

The rest of the article will be me explaining the pseudocode that I followed to get to the solutions! Please try to solve them first even if it’s just a few minutes of brainstorming your ideas. It will be helpful to understand the problem and some ideas of solving it first!

1. Checking if there is a path from location A to location B

Finding a path between 2 vertices can be solved by either using BFS or DFS.
Check out the code to this problem!

Properties:
visited —Set to store all vertices that will be passed in bfs.
queue —Queue for bfs

Pseudocode:
• Add the source vertex to our empty queue as well as adding it to the visited set.
• Loop through the queue while there’re still vertices in it.
• dequeue an item from the queue and store it in a variable named curr
• check if curr is the destination vertex inputted in the function parameter. If it is so, then we can return true, and our function is complete!
• We’re not at the end yet so we would want to continue our bfs algorithm.
• Start off by creating another for loop on curr’s neighbors. And only do the following if the neighbor vertex is not in the visited set:
enqueue neighbor to our queue, and
add neighbor to the visited set.
• Once the while loop has finished executing, we can return false since we’ve looped through the connecting vertices in this graph and still have not found the destination vertex!

2. Finding the fastest route from location A to location B

This problem can be solved by either using BFS or DFS. The functionality is very similar to the solution above🤔 I recommend you try finding the solution to this problem from the pseudocode above before looking below!
Check out the code to this problem!

Properties:
path_found — Boolean variable that is initially the value False. The value will change once we find the destination vertex!
visited—Set to store all vertices that will be passed in bfs.
queue —Queue for bfs
path — Array to store the connecting paths of vertices from the source to the destination vertex .

Pseudocode:
• Add the source vertex to our empty queue as well as adding it to the visited set.
• Loop through the queue while there’re still vertices in it.
• dequeue an item from the queue and store it in a variable named curr
• check if curr is the destination vertex inputed in the function parameter. If it is so, we can set path_found to true and break out of the while loop.
• Otherwise, we would want to create a for loop on curr’s neighbors. And only do the following if the neighbor is not in the visited set:
1. Enqueue neighbor to our queue
2. Add neighbor to the visited set
3. Set the neighbor’s parent variable to curr vertex
• Once the while loop has finished executing, we want to do a check statement if path_found is true. If it’s true, that means we can start appending to our path array! But we must follow these steps carefully:
1. Set our curr vertex to be the destination vertex,
2. Loop through while curr still has a value so we can: append curr to our path array, and update curr to become curr’s parent.
[I just want to note that in this step, with the parent variable, we’re traversing up the tree. And you can visualize it as the root node being the source vertex, and the distance vertex is the last node in the tree.]
• Outside the while loop, we can return path in reverse order!

3. Seeing how many places we can travel to based on our starting location

Since our graph represents vertices as a location, we can implement finding the degree of that vertex! A degree of a vertex simply means the count of the connecting edges. Let’s jump right in our brainstorm!
Check out the code to this problem!

Properties:
vert_obj —Vertex object from our graph

Pseudocode:
• Since our vertex class has a property that tracks all it’s neighbors, we can simply return the length of calling the vertex’s neighbors!

And that will be a wrap on this article on solving problems through graphs! I hope you found value in this blog post and I highly encourage you to try implementing all these methods or even create your own graph theory application!