Everything you use in your daily digital life is dependent on connections. Whether you maintain a friend list in your favorite social networking platform such as Facebook or you use Google Maps for finding the fastest way back home from your workplace, you deal with inter-connected data.

Graph is the most effective means for modeling connections in software engineering. Although “graph” may remind you of high-school math diagrams, in computer science it is just a drawing representing connection between points.

Graph algorithms are computer instructions for analyzing such graphs. Many programmers regard graph theory as a highly challenging area with tons of terminology and concepts from mathematics. However, when put in context and explained with real-life analogies, graph algorithms turn out to be rather logical.

Basic Concepts of Graph Theory & Algorithms Simplified

Two Key Terms to Understand: Nodes & Edges

Nodes (Vertices): Entities that comprise your network. They are the nouns of the network: “people,” “cities,” “web pages,” or “airport terminals.”

Edges: Connections between the nodes. They are the verbs: “is friends with,” “connects to,” or “links to.”

Depending on your specific needs, you will encounter the following types of graphs:

Undirected Graph: Connection is bidirectional. If Alice is Facebook friends with Bob, Bob will automatically become Alice’s friend too. The connection is bidirectional.

Directed Graph: Connection is unidirectional and represented by an arrow. If Alice follows a celebrity on Instagram, the connection is unidirectional. Unless the celebrity follows Alice back, she will not be friends with him/her.

Weighted Graph: Connection is characterized with a numeric value, such as “distance,” “travel time,” or “financial cost.” For example, in your map graph there will be an edge with the distance of 215 miles between New York and Boston.

1. Network Exploration: BFS vs DFS

Before you can perform any complex analysis of your network, you need to discover it first. This process is called Traversal. There are two major approaches to traversing a network, and they resemble two completely different people.

Breadth-First Search (BFS): The Cautious Explorer

Imagine you throw a pebble into a pond, and observe concentric ripples expanding from the place where it fell down. BFS algorithm works similarly. Starting from your initial node, BFS first examines all immediate neighbors (Level 1), then their neighbors (Level 2), and so forth.

Real-Life Analogy: How do you find someone to write a recommendation letter for you? First, you contact your close friends. If they know no one to help you, you extend your circle of contacts to your friends’ friends.

Use Case in Technology: BFS algorithm forms the basis of calculating degrees of separation in a social network. LinkedIn uses BFS algorithm to calculate degrees of connection between users.

Depth-First Search (DFS): The Bold Adventurer

Unlike BFS, DFS does not examine all immediate neighbors of your node at once. Instead, it chooses one path and explores it till the dead end, backtracks to the last intersection point and continues exploring other paths.

Real-Life Analogy: Imagine you find yourself in a maze and have to find a way out. You turn left and keep walking in that direction until you reach a dead end. Then you go back to the last intersection point and explore another, deeper path.

Use Case in Technology: DFS algorithm is especially helpful in finding the path between two nodes, detecting cycles within a network, and solving puzzles like Sudoku.

2. Pathfinding: Dijkstra’s Algorithm

Routing is among the most frequent problems of software engineering. Creating a navigation application like Google Maps or Waze, you cannot use BFS because roads have different distances, traffic, and speed limits (weight). In this case, you will need Dijkstra’s algorithm for a weighted graph.

Dijkstra’s algorithm keeps the current table of minimum travel times from your starting point to all other points in your map. During each iteration, Dijkstra performs greedy evaluation: it selects the closest yet unexplored checkpoint and checks all its connections, updating minimum times if needed.

Real-Life Application: Whenever you type your destination into Google Maps or GPS navigation system in your car, millions of routing calculations take place using Dijkstra’s algorithm for finding you the quickest driving route.

3. Influence Tracking: PageRank

Not all nodes in your network are equal. Some are more influential, authoritative, or popular than the others. To solve this problem, Google founders Larry Page and Sergey Brin developed PageRank algorithm.

PageRank is a democratic voting algorithm with one exception: votes cast from authoritative nodes carry much more weight. PageRank determines the prestige of a node depending on the number of incoming connections (links).

If an insignificant blog posts a link to your website, your PageRank score will increase slightly. However, when a massive authoritative website such as Wikipedia.org or The New York Times.com links to your website, it will grant you immense prestige.

Real-Life Application: Apart from ranking websites, PageRank algorithm can be used for recommending Twitter and LinkedIn accounts to follow and identifying crucial proteins in biological networks.

4. Cost Optimization: Prim’s & Kruskal’s

Imagine yourself a network architect who is asked to lay optical fibers to connect seven separate office buildings in a big city. It is costly to lay wires, and therefore your aim is to connect all seven buildings using the minimum length of cables, while keeping your network loop-free.

Such optimized loop-free network is called Minimum Spanning Tree (MST). Two classical algorithms can be used to calculate MST:

Prim’s Algorithm: The Growing Plant

Prim’s algorithm adopts a localized approach. You choose one of the buildings as a starting point and examine all connections. You pick the cheapest cable and connect your second building to the network. Next, you examine connections of both buildings and pick the cheapest connection to the third building. This process repeats until all buildings are connected.

Kruskal’s Algorithm: The Forest Joiner

Kruskal’s algorithm differs from Prim’s one in that it does not start from one point. Kruskal examines all connections in the city and sorts them from the cheapest to the most expensive. It starts laying cables picking up the cheapest connection each time. Although Kruskal creates isolated sub-networks along the way, there is one rule: if a connection creates a loop, Kruskal skips it. Ultimately, all islands will unite into one network.

Summary Table of Graph Algorithms for Your Convenience

For your convenience in choosing the optimal graph strategy for your development project, please see the table below:

What is the Difference Between Graph and Tree?

A tree is a special case of Graph, which means it is a subclass of graphs. While general graph can be completely chaotic, being directed, having loops, disconnected components, and alternative paths, tree must meet two conditions: it must be fully connected (all nodes are reachable from any other node) and acyclic (it must not contain any closed loops). In a tree, there is only one unique path between any two nodes.

Why should I use Adjacency List over Adjacency Matrix?

In order to execute graph algorithms, you need to model your graph in computer memory. Adjacency matrix is a two-dimensional flat array of rows and columns representing nodes. It allows you to quickly check whether there is a connection between any two nodes, but consumes lots of memory. Conversely, adjacency list stores a compact list of neighbors for each node, making it memory-efficient for sparse graphs (graphs with few connections).

Why do I need Bellman-Ford algorithm?

As it has been explained above, Dijkstra’s algorithm assumes that edge weights (costs) are positive values such as distances or time. When dealing with financial models (rewards and rebates) or physics simulations (energy gains), however, Dijkstra’s algorithm becomes useless. Bellman-Ford algorithm is somewhat slower than Dijkstra’s one, but capable of handling negative costs, and even detecting them within a network.

What is the Historical Importance of Königsberg Bridge Problem?

Seven Bridges of Königsberg is a famous mathematical problem giving birth to graph theory in 1736. In there were seven bridges connecting landmasses separated by a river, and people wondered if it was possible to design a walking route crossing each bridge only once and without repetitions. Mathematician Leonhard Euler proved that such route was impossible to design and created the first graph in the process.

What is the Time Complexity of BFS/DFS Traversals?

Time complexity of both Breadth-First Search and Depth-First Search is O(V + E). Here, V stands for the number of Vertices (Nodes) in your graph, while E stands for the number of Edges (Connections).