Name: Graphs in Python - Theory and Implementation
Author: Dimitrije Stamenic

Graphs are an extremely versatile data structure. More so than most people realize! Graphs can be used to model practically anything, given their nature of modeling relationships and hierarchies.
<blockquote>
Nature and human creations are extremely hierarchical.
</blockquote>
Words in a sentence, and sentences in a book can be graphs - represented as a grid. Pixels in an image can be a graph as well. A graph can represent a sequence of steps you want to take, or a sequence of operations an algorithm runs. A graph can represent a molecule, their arangements, up to humans and their relationships, up to streets and intersections, up to cities, countries, planets!
<blockquote>
From an atomic scale to a universe scale - graphs can be used to model any sort of relationship or hierarchy.
</blockquote>
Many common problems in the world can be represented in graphs. Where to open up restaurants to cover an area with guaranteed delivery times, with the minimum investment? Where to route a driver to avoid congestion and get to a target place as soon as possible? How to organize the flow of electrical energy in a city's grids? There isn't a shortage of problems that are inherently graph-based.
Graphs have been an important computational model in the past, and still are today. It's not that you university just wants you to learn them - they're genuinely one of the most useful data structures around. Recently, Graphs have been explored in newer contexts as well. For instance, <a target="_blank" rel="nofollow noopener noreferrer" href="https://arxiv.org/abs/1710.10903">Graph Attention Networks</a> outlies a new type of artificial neural networks that operate on graphs, written by Petar Veličković et al. in 2018 has been cited over 7300 times. It's found major application in the fields of computational chemistry and drug discovery, and the idea is implemented in practically all frameworks dealing with modeling molecules as graphs.
<blockquote>
Getting started with graphs can be daunting. Literature can be scattered and searching online typically involves various different implementations and a non-continuity between the material you're reading.
</blockquote>
For that reason, we're compiling an introductory course to Graphs in Python, in an attempt to standardize the fundamentals to help you form a solid basis on graph theory. The course is intended to expand through time, with new algorithms being added in.
<h3 id="graphssimplified">Graphs Simplified</h3>
Graphs can be complicated more than warranted. Fundamentally - they're fairly simple, but given the interdisciplinary usage of them, terminology can get confusing, since it overlaps and certain should-be-synonyms suddenly don't refer to the same thing anymore. You'll generally find people disagreeing in terms of terminology in the field, and especially online. If English is not your native language, and you've studied graph theory in a different language - translator freedom and loss of context between translation can make it even more confusing.
<blockquote>
What's true?
</blockquote>
Like with most things - it's hard to tell. You can't refer to the &quot;original source&quot; since scientific fields change through time, and the standard of &quot;truth&quot; changes with them. The best you could do is accept that there are various (slightly different) definitions and terminologies and abstain from semantic arguments. The point is fairly straightforward.
Each graph consists of nodes (also called vertices) and edges also sometimes known as arcs. This is where the first semantic argument can be raised! Computer Scientists more commonly call these nodes and edges. Mathematicians more commonly use the terms vertex and edge but also arc, and make a distinction between an edge (undirected) and an arc (directed). Additionally - not all combinatorialists and geometrists are in agreement here either. Official literature from universities also differs here. Some don't ascribe a difference between edges and arcs, while some do.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 Note: Throughout the course, we'll be using the Computer Science notation of node and edge for the sake of consistency.

 </div>
 </div>
 The point is: we can look at nodes/vertices as &quot;chunks of data&quot; and edges/arcs as &quot;relations between those chunks of data&quot;.
You'll oftentimes also see this notation:
$$ 
G = (V, E) 
$$
Or:
$$ 
G = (N, E) 
$$
A graph (<code>G</code>), consists of vertices/nodes (<code>V</code>/<code>N</code>) and eges (<code>E</code>). Can you guess which formula was written by a mathematician and which by a computer scientist?
If we want to point out that two chunks of data are related to each other in some way - we'd connect them with an edge. Nodes are usually represented as circles with an identifying mark on them, so that we can distinguish between nodes, and edges are represented via lines (or arrows, as we'll see later) that connect two nodes. This is just a human-interpretable abstraction.
A form of the graph data structure is often used when making maps for a city's bus or metro lines. For instance, if you've ever been to a metro/bus station - you'd see a simplified map of the city, with a bunch of stations. Each station is a node in a graph, and the lines that a metro/bus follows are edges of that graph:
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-1.png" alt="">
This graph shows what different bus stops we have and how they are connected. For example, we can see that, using this bus line, to get from Bus Stop A to Bus Stop C we'd have to go through Bus Stop B - we can't get there any other way.
<h4 id="weightedgraphs">Weighted Graphs</h4>
Let's say we wanted to add information regarding how long it took on average (in minutes) to get from one bus stop to another. We'd add &quot;weights&quot; to our edges:
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-2.png" alt="">
Weights can represent any arbitrary measurable. In the case of a map represented as a graph - it could be the time it takes to traverse that edge. Or - it could be the current congestion. In the case of a molecule, the weight could be the strength of the connection between atoms. In the case of a power grid, it could be the resistance of the cable or the loss of energy when transferring electricity. This depends highly on the specific problem you're modeling with a graph, and the domain of that problem.
Let's get back to the bus stops! Now our graph shows even more information than before, we see how long it takes to get from one stop to another. We can deduce that getting from Bus Stop A to Bus Stop C would take 23 minutes since we'd need to &quot;traverse&quot; the edge connecting Bus Stop A and Bus Stop B that has a weight of 15 and the (Bus Stop B -&gt; Bus Stop C) edge, which has a weight of 8.
<h4 id="directedandundirectedgraphs">Directed and Undirected Graphs</h4>
Now we'll look at another graph concept - directed and undirected graphs. Let's say that our bus line didn't have the same stops in both directions.
More precisely, when our bus starts from Bus Stop A it goes through B, C, and ends at D; however, in the other direction it doesn't go through C but an altogether different bus stop E, before then going through B. We might make something like this:
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-3.png" alt="">
As the spoiler in the picture suggests - this approach isn't correct. Just looking at this graph we can't understand which bus stops the bus goes through in which direction, since nothing's stopping us from getting from B to E even though we should only be able to get from E to B.
This is where directed graphs come into play. The edges in directed graphs are represented via arrows instead of lines, an arrow pointing from A to B means &quot;we can get from A to B but not vice versa&quot;. If we wanted to say we can get both from A to B and from B to A, we'd use a double-sided arrow.
Now, the cycle is no longer ambiguous:
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-4.png" alt="">
Now it's clear that we can't go from B to E or from D to C, etc. It's clear that we can make graphs as simple or as complex as we want to. We could go one step further in our example, if for some reason it took a different amount of time to travel between some bus stops depending on the direction we're going.
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-5.png" alt="">
<h4 id="connectedanddisconnectedgraphs">Connected and Disconnected Graphs</h4>
A graph can also be connected and disconnected. A graph is connected if there is a path (which consists of one or more edges) between each pair of nodes. On the other hand, a graphs is disconnected if there is a pair of nodes which can't aren't connected by a path of edges.
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-7.png" alt="">

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 Note: A frequent misconception is that graphs need to be connected, or at least that every node needs to be connected to another in some way. This isn't true. A graph can just as easily be consisted of any number of nodes without a single edge between them. However, many traversal algorithms require graphs to be connected to work properly.

 </div>
 </div>
 <h3 id="applicationsofgraphs">Applications of Graphs</h3>
Here are a few examples of data that can be conveniently stored/represented using graphs, keeping in mind that this is just a grain of sand on the beach:
<ul>
<li>Modeling nature: As stated earlier - many things in nature is naturally modeled as a graph, from molecules to galaxies.</li>
<li>A set of people and their affiliations: This can be done using an undirected graph, since we're assuming that if person A knows person B, the same is true vice versa (hopefully). The different people would be represented by nodes, and if person A knows person B there will be an edge connecting the two nodes.</li>
<li>The structure of a website: Different pages on a website are nodes, and there is a directed edge between page A and page B if a link to page B exists on page A. For example the home page often has links to an About Us and Contact page.</li>
<li>Mutually dependent tasks: We can represent what tasks need to be completed before task A and what tasks cannot be completed before A has been completed in the following way - if there is a directed edge from B to A, then A cannot be completed before B is completed; if there is a directed edge from A to C, then C cannot be completed before A is completed:</li>
</ul>
<img src="https://s3.stackabuse.com/media/articles/graph-theory-and-graph-related-algorithms-6.png" alt="">
Here we can see that we can put on glasses, socks, pants and a t-shirt regardless of other clothes. But we can't put on shoes before putting on pants and socks. And we can't go-out before doing everything else, except putting on glasses, since they might not be necessary. These types of graphs are easily sorted and we can see a feasible order of task execution using Topological Sorting.
<h3 id="graphscomparedtotrees">Graphs Compared to Trees</h3>
If you are familiar with trees, graphs are easy to understand - trees are a special kind of graph, i.e. graphs with certain restrictions. Every tree is a graph, but not every graph is a tree.
By definition, trees are undirected graphs that:
<ul>
<li>Are acyclic, i.e. we can't traverse back to any starting node we choose without back-tracking</li>
<li>A cycle is created by adding any edge into the existing tree</li>
<li>The path between any two nodes is unique</li>
<li>There is a distinct root node</li>
<li>The graph is connected (there's a path between every two nodes)</li>
</ul>
Or in very simplified terms - trees are connected graphs without cycles. For graphs, we just get rid of all these restrictions and keep the nodes and edges concept. We'll get back to trees later, when we start covering algorithms that are meant to operate on trees specifically.
<h3 id="graphsasamathematicalterm">Graphs as a Mathematical Term</h3>
Graphs originated from mathematics so it's worth dedicating at least a couple of paragraphs to defining a more formal definition. A graph is an ordered pair <code>G = (N, E)</code>, where <code>N</code> is a set of nodes and <code>E</code> is the set of edges.
Undirected Graphs: <code>E ⊆ {{x, y} | (x, y) ∈ N^2}</code>. Sometimes an extra condition is added if we want to avoid edges that have the same start and end point (i.e. <code>x ≠ y</code>).
Directed Graphs: <code>E ⊆ {(x, y) | (x, y) ∈ N^2}</code>, here as well we can add the condition that <code>x ≠ y</code> if we want to avoid edges that start and end in the same node.
As we can see in the previous definitions of the set of edges <code>E</code>, the only difference is that in the case of directed graphs <code>(x,y)</code> is an ordered pair, while in undirected graphs the pair <code>{x,y}</code> is unordered. This means that in an undirected graph, what matters is that <code>x</code> and <code>y</code> are connected, not in &quot;what order&quot;. So we could have written <code>{y,x}</code> instead of <code>{x,y}</code> while we could not have written <code>(y,x)</code> instead of <code>(x,y)</code> for a directed graph.
In the following lessons - we'll dive into graph representations in code (lists of edges, adjacency matrices and adjacency lists, as well as their implementations). Then, we'll cover some of the most important and widely used algorithms for graph traversal and graph search, starting with the simpler, intuitive ones, and working our way from there:
<ul>
<li>Breadth-First Search and Depth-First Search</li>
<li>Dijkstra's Algorithm</li>
<li>A*</li>
<li>Prim's Algorithm</li>
<li>Boruvka's Algorithm</li>
<li>Kruskal's Algorithm</li>
</ul>

David Landup

Olivera Popović

Graph Theory and Graph-Related Algorithms

Dimitrije Stamenic

Jovana Ninkovic

Representing Graphs in Code

Anđela Niketić

Breadth-First Search (BFS) Algorithm

In this lesson, we'll take a look at one of the two complementary, fundamental and simplest algorithms for Graph traversal - Depth-First Search (DFS). It's the most commonly used algorithm alongside the related Breadth-First Search (BFS) given their simplicity. After going over the main idea used for DFS, we'll implement it in Python on a Graph representation - an adjacency list.
<h3 id="depthfirstsearchtheory">Depth-First Search - Theory</h3>
Depth-First Search (DFS) is an algorithm used to traverse or locate a target node in a graph or tree data structure. It priorities depth and searches along one branch, as far as it can go - until the end of that branch. Once there, it backtracks to the first possible divergence from that branch, and searches until the end of that branch, repeating the process.
Given the nature of the algorithm, you can easily implement it recursively - and you can always implement a recursive algorithm iteratively as well:
<img src="https://s3.stackabuse.com/media/articles/dfs-gif.gif" alt="dfs animation">
The start node is the root node for tree data structures, while with more generic graphs - it can be any node.
DFS is widely-used as a part of many other algorithms that resolve graph-represented problems. From cycle searches, path finding, topological sorting, to finding articulation points and strongly connected components. The reason behind this widespread use of the DFS algorithm lies in its overall simplicity and easy recursive implementation.
<h3 id="thedfsalgorithm">The DFS Algorithm</h3>
The DFS algorithm is pretty simple and consists of the following steps:
<ol>
<li>Mark the current node as visited.</li>
<li>Traverse the neighboring nodes that aren't visited and recursively call the DFS function for that node.</li>
</ol>
The algorithm stops either when the target node is found, or the whole graph has been traversed (all nodes are visited).

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 Note: Since graphs can have cycles, we'll need a system to avoid them so we don't fall into infinity loops. That's why we &quot;mark&quot; every node we pass as visited by adding them to a <code>Set</code> containing only unique entries.

 </div>
 </div>
 By marking nodes as &quot;visited&quot;, if we ever encounter that node again - we're in a loop! Endless computational power and time have been wasted on loops, lost in the aether.
<h4 id="pseudocode">Pseudocode</h4>
Given these steps, we can summarize DFS in pseudocode:
<pre><code class="hljs">DFS(G, u):
 # Input processing
 u.visited = true
 for each v in G.adj[u]:
 if !v.visited:
 DFS(G, v)
 # Output processing
</code></pre>
Input and output processing is performed depending on the purpose of the graph search. Our input processing for DFS will be checking if the current node is equal to the target node.
With this view, you can really start to appreciate just how simple yet useful this algorithm is.
<h3 id="depthfirstsearchimplementation">Depth-First Search - Implementation</h3>
The first thing we need to consider before diving into the implementation of the DFS algorithm itself is how to implement a graph. As in any other article from this series, we've opted to implement it using a fairly basic <code>Graph</code> class. It contains a graph representation and a couple of methods you need to operate with graphs:
<pre><code class="hljs">class Graph:
 # Constructor
 def __init__(self, num_of_nodes, directed=True):
 self.m_num_of_nodes = num_of_nodes
 self.m_nodes = range(self.m_num_of_nodes)
		
 # Directed or Undirected
 self.m_directed = directed
		
 # Graph representation - Adjacency list
 # We use a dictionary to implement an adjacency list
 self.m_adj_list = {node: set() for node in self.m_nodes} 
	
 # Add edge to the graph
 def add_edge(self, node1, node2, weight=1):
 self.m_adj_list[node1].add((node2, weight))

 if not self.m_directed:
 self.m_adj_list[node2].add((node1, weight))
 
 # Print the graph representation
 def print_adj_list(self):
 for key in self.m_adj_list.keys():
 print(&quot;node&quot;, key, &quot;: &quot;, self.m_adj_list[key])
</code></pre>
Let's just quickly recap how does the <code>Graph</code> class work. The <code>__init__()</code> method defines a constructor. It consists of a number of nodes, a set of nodes, and the graph representation. In this case, a graph is represented by an adjacency list - effectively a Python dictionary with each node of the graph set to be one key. A set of adjacent nodes is assigned to each node (key).

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 Note: An adjacency list is a type of graph representation in code, it consists of keys that represent each node, and a set of values for each of them containing nodes that are connected to the key node with an edge. 
Using a dictionary for this is the easiest way to quickly represent a graph in Python, though you could also define your own <code>Node</code> classes and add them to a <code>Graph</code> instance instead.

 </div>
 </div>
 As its name suggests, the <code>add_edge()</code> method is used to add edges to the graph representation. Each edge is represented as in any usual adjacency list. For example, edge <code>1-2</code> is represented by adding <code>2</code> as the adjacent node of node <code>1</code> in the adjacency list. Additionally, our implementation enables you to assign a weight to any edge.
Lastly, we've created the method that prints the graph representation - <code>print_adj_list()</code>.
Now we can implement the DFS algorithm in the <code>Graph</code> class. Depth-First Search implementation is usually recursive in code given how natural of a pair that is, but it can also be easily implemented non-recursively. We'll be using the recursive method:
<pre><code class="hljs">def dfs(self, start, target, path = [], visited = set()):
 path.append(start)
 visited.add(start)
 if start == target:
 return path
 for (neighbour, weight) in self.m_adj_list[start]:
 if neighbour not in visited:
 result = self.dfs(neighbour, target, path, visited)
 if result is not None:
 return result
 path.pop()
 return None 
</code></pre>
We added the start node to the beginning of our traversal path and marked it as visited by adding it to a set of <code>visited</code> nodes. Then, we traversed the start node's neighbors that aren't already visited and called the function recursively for each of them. Recursive calls result in going as deep as we can along one &quot;branch&quot;.
We then saved a reference to the result. In the case the function returns <code>None</code>, that means that the target node was not found in this branch and that we should try another. If the recursive call, in fact, does not return <code>None</code>, that means we have found our target node and we return the traversal path as result.
In the end, if we find ourselves outside of the <code>for</code> loop, it means that all the neighbor branches of the current node have been visited and none of them lead to our target node. So, we remove the current node from the path and return <code>None</code> as result.
<h3 id="runningdfs">Running DFS</h3>
Let's illustrate how the code works through an example. As we've stated before, we'll be using <code>Graph</code> class to represent the graph. Internally, it represents a graph as an adjacency list. Here's the graph we'll be using in the following example:
<img src="https://s3.stackabuse.com/media/articles/graphs-in-python-dfs-1.png" alt="graph">
We'll be searching for a path from node <code>0</code> to node <code>3</code>, if it exists, the path will be saved into a set of visited nodes, called <code>traversal_path</code> so we can reconstruct it for printing.
The first thing we need to do is to create an instance of the <code>Graph</code> class. Our example graph is undirected and has 5 nodes, so we'll create its representation in the following way:
<pre><code class="hljs">graph = Graph(5, directed=False)
</code></pre>
This will create the instance of the <code>Graph</code> representing undirected graph with 5 nodes. Next, we need to add all edges from the example graph into our graph representation:
<pre><code class="hljs">graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
</code></pre>
Now, we've created the complete representation of the example graph. Let's take a look at how does the <code>Graph</code> class internally store our example graph:
<pre><code class="hljs">graph.print_adj_list()
</code></pre>
Which outputs the following:
<pre><code class="hljs">node 0 : {(1, 1), (2, 1)}
node 1 : {(0, 1), (3, 1)}
node 2 : {(0, 1), (3, 1)}
node 3 : {(1, 1), (4, 1), (2, 1)}
node 4 : {(3, 1)}
</code></pre>
This shows the structure of the dictionary used to represent an adjacency list. It's perfectly in line with the implementation of an adjacency list provided in the lesson about graph representations in Python.
Finally, we can find a path from node <code>0</code> to node <code>3</code>:
<pre><code class="hljs">traversal_path = []
traversal_path = graph.dfs(0, 3)
print(traversal_path)
</code></pre>
This will output the found path:
<pre><code class="hljs">[0, 1, 3]
</code></pre>
Now it would be useful to take a look at the steps our algorithm took:
<ul>
<li>Add node <code>0</code> to the traversal path and mark it as visited. Check if node <code>0</code> is equal to target node <code>3</code>, since it's not, continue and traverse its neighbors (<code>1</code> and <code>2</code>).</li>
<li>Is neighbor <code>1</code> visited? - No. Then, the algorithm calls the function recursively for that node.
<ul>
<li>Recursive call for node <code>1</code>: Add node <code>1</code> to the traversal path and mark it as visited. Is <code>1</code> equal to our target node <code>3</code>? - No, continue and traverse its neighbors (<code>0</code> and <code>3</code>).</li>
<li>Is neighbor <code>0</code> visited? - Yes, move on to the next one.</li>
<li>Is neighbor <code>3</code> visited? - No, call the function recursively for this node.
<ul>
<li>Recursive call for node <code>3</code>: Add node <code>3</code> to the traversal path and mark it as visited. Is <code>3</code> equal to our target node <code>3</code>? - Yes, the target node has been found, return the traversal path.</li>
</ul>
</li>
</ul>
</li>
</ul>
<table class="table table-striped">
 <tr>
 <th>Current Node</th>
 <th>Path</th>
 <th>Visited</th>
 </tr>
 <tr>
 <td>0</td>
 <td>[0]</td>
 <td>{0}</td>
 </tr>
 <tr>
 <td>1</td>
 <td>[0, 1]</td>
 <td>{0, 1}</td>
 </tr>
 <tr>
 <td>3</td>
 <td>[0, 1, 3]</td>
 <td>{0, 1, 3}</td>
 </tr>
</table>
The algorithm stops and our program prints out the resulting traversal path from node <code>0</code> to node <code>3</code>:
<pre><code class="hljs">[0, 1, 3]
</code></pre>
After the search, the marked nodes on the graph represent the path we took to get to the target node:
<img src="https://s3.stackabuse.com/media/articles/graphs-in-python-dfs-2.png" alt="marked graph">
In case there was no path between the start and target node, the traversal path would be empty.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 Note: Graphs can also be disconnected, meaning that there are at least two nodes that cannot be connected by a path. In this case, DFS would ignore the nodes that it can't get to.

 </div>
 </div>
 <img src="https://s3.stackabuse.com/media/articles/graphs-in-python-dfs-3.png" alt="disconnected graph">
For example in this graph, if we were to start DFS from node <code>0</code> to node <code>4</code>, there would be no such path because it has no way of getting to the target node.

Depth-First Search (DFS) Algorithm

Scott Robinson

Mila Lukic

Dijkstra's Algorithm

<h3 id="whatisa">What is A*?</h3>
Let's say that you have to get through an enormous maze. This maze is so big that it would take hours to find the goal manually. Additionally, once you finish the maze &quot;by foot&quot;, you're supposed to finish another one.
To make things significantly easier and less time consuming, we'll boil the maze down to a search problem, and come up with a solution that can be applied to any additional maze that we may encounter - as long as it follows the same rules/structure.
Any time we want to convert any kind of problem into a search problem, we have to define six things:
<ol>
<li>A set of all states we might end up in</li>
<li>The start and finish state</li>
<li>A finish check (a way to check if we're at the finished state)</li>
<li>A set of possible actions (in this case, different directions of movement)</li>
<li>A traversal function (a function that will tell us where we'll end up if we go a certain direction)</li>
<li>A set of movement costs from state-to-state (which correspond to edges in the graph)</li>
</ol>
The maze problem can be solved by mapping the intersections to appropriate nodes (red dots), and the possible directions we can go to appropriate graph edges (blue lines).
Naturally, we define the start and finish states as the intersections where we enter the maze (node A), and where we want to exit the maze (node B).
<img src="https://s3.amazonaws.com/stackabuse/media/basic-ai-concepts-a-search-algorithm-1.png" alt="Maze with state nodes">
Now that we have a finished graph, we can discuss algorithms for finding a path from state A to state B. In simple cases (like this one), where the generated graph consists of a small number of nodes and edges, <a rel="nofollow" target="_blank" href="https://stackabuse.com/breadth-first-search-bfs-in-python-theory-and-implementation/">BFS</a>, <a target="_blank" rel="https://stackabuse.com/depth-first-search-dfs-in-python-theory-and-implementation/">DFS</a> and <a target="_blank" href="https://stackabuse.com/dijkstras-algorithm-in-python/">Dijkstra</a> would suffice.
However, in a real-life scenario, because we are dealing with problems of enormous combinatorial complexity, we know we will have to deal with an enormous amount of nodes and edges. For example, there are many states a Rubik's cube can be in, which is why solving it is so difficult. Therefore, we have to use an algorithm that is, in a sense, guided. That is where an informed search algorithm arises, A*.
Informed Search signifies that the algorithm has extra information, to begin with. For example, an uninformed search problem algorithm would be finding a path from home to work completely blind.
On the flip-side, an informed search problem algorithm would be finding a path from home to work with the aid of your sight (seeing what path brings you closer to your destination) or a map (knowing exactly how far away every single point is from your destination).
A* only performs a step if it seems promising and reasonable, according to its functions, unlike other graph-traversal algorithms. It runs towards the goal and doesn't consider any non-optimal steps if it doesn't have to consider them.
This makes A* very useful for artificially intelligent systems - especially in Machine Learning and game development since these systems replicate real-world scenarios.
<h3 id="basicconceptsofa">Basic Concepts of A*</h3>
A* is based on using heuristic methods to achieve optimality and completeness, and is a variant of the best-first algorithm.
When a search algorithm has the property of optimality, it means it is guaranteed to find the best possible solution, in our case the shortest path to the finish state. When a search algorithm has the property of completeness, it means that if a solution to a given problem exists, the algorithm is guaranteed to find it.
Each time A* enters a state, it calculates the cost, <code>f(n)</code> (n being the neighboring node), to travel to all of the neighboring nodes, and then enters the node with the lowest value of <code>f(n)</code>.
These values are calculated with the following formula:
$$ 
\mathcal f(n) = \mathcal g(n) + \mathcal h(n) 
$$
<code>g(n)</code> being the value of the shortest path from the start node to node n, and <code>h(n)</code> being a heuristic approximation of the node's value.
For us to be able to reconstruct any path, we need to mark every node with the relative that has the optimal <code>f(n)</code> value. This also means that if we revisit certain nodes, we'll have to update their most optimal relatives as well. More on that later.
The efficiency of A* is highly dependent on the heuristic value <code>h(n)</code>, and depending on the type of problem, we may need to use a different heuristic function for it to find the optimal solution.
Construction of such functions is no easy task and is one of the fundamental problems of AI. The two fundamental properties a heuristic function can have are admissibility and consistency.
<h3 id="admissibilityandconsistency">Admissibility and Consistency</h3>
A given heuristic function <code>h(n)</code> is admissible if it never overestimates the real distance between n and the goal node.
Therefore, for every node n the following formula applies:
$$ 
h(n)\leq h^*(n) 
$$
<code>h*(n)</code> being the real distance between n and the goal node. However, if the function does overestimate the real distance, but never by more than d, we can safely say that the solution that the function produces is of accuracy d (i.e. it doesn't overestimate the shortest path from start to finish by more than d).
A given heuristic function <code>h(n)</code> is consistent if the estimate is always less than or equal to the estimated distance between the goal n and any given neighbor, plus the estimated cost of reaching that neighbor:
$$ 
c(n,m)+h(m)\geq h(n) 
$$
<code>c(n,m)</code> being the distance between nodes <code>n</code> and <code>m</code>. Additionally, if <code>h(n)</code> is consistent, then we know the optimal path to any node that has been already inspected. This means that this function is optimal.
Theorem: If a heuristic function is consistent, then it is also admissible.
<h3 id="proofbycompleteinduction">Proof by Complete Induction</h3>
The induction parameter <code>N</code> will be the number of nodes between node <code>n</code> and the finish node <code>s</code> on the shortest path between the two.
Base: N=0
If there are no nodes between <code>n</code> and <code>s</code>, and because we know that <code>h(n)</code> is consistent, the following equation is valid:
$$ 
c(n,s)+h(s)\geq h(n) 
$$
Knowing <code>h*(n)=c(n,s)</code> and <code>h(s)=0</code> we can safely deduce that:
$$ 
h^*(n)\geq h(n) 
$$
Induction hypothesis: N &lt; k
We hypothesize that the given rule is true for every <code>N &lt; k</code>.
Induction step:
In the case of <code>N = k</code> nodes on the shortest path from <code>n</code> to <code>s</code>, we inspect the first successor (node <code>m</code>) of the finish node <code>n</code>. Because we know that there is a path from <code>m</code> to <code>n</code>, and we know this path contains <code>k-1</code> nodes, the following equation is valid:
$$ 
ℎ^*(𝑛) = 𝑐(𝑛, 𝑚) + ℎ^*(𝑚) ≥ 𝑐(𝑛, 𝑚) + ℎ(𝑚) ≥ ℎ(𝑛) 
$$
Q.E.D.
<h3 id="implementation">Implementation</h3>
This is a direct implementation of A* on a graph structure. The heuristic function is defined as 1 for all nodes for the sake of simplicity and brevity.
The graph is represented with an adjacency list, where the keys represent graph nodes, and the values contain a list of edges with the the corresponding neighboring nodes.
Here you'll find the A* algorithm implemented in Python:
<pre><code class="hljs">from collections import deque

class Graph:
 # example of adjacency list (or rather map)
 # adjacency_list = {
 # &#x27;A&#x27;: [(&#x27;B&#x27;, 1), (&#x27;C&#x27;, 3), (&#x27;D&#x27;, 7)],
 # &#x27;B&#x27;: [(&#x27;D&#x27;, 5)],
 # &#x27;C&#x27;: [(&#x27;D&#x27;, 12)]
 # }

 def __init__(self, adjacency_list):
 self.adjacency_list = adjacency_list

 def get_neighbors(self, v):
 return self.adjacency_list[v]

 # heuristic function with equal values for all nodes
 def h(self, n):
 H = {
 &#x27;A&#x27;: 1,
 &#x27;B&#x27;: 1,
 &#x27;C&#x27;: 1,
 &#x27;D&#x27;: 1
 }

 return H[n]

 def a_star_algorithm(self, start_node, stop_node):
 # open_list is a list of nodes which have been visited, but who&#x27;s neighbors
 # haven&#x27;t all been inspected, starts off with the start node
 # closed_list is a list of nodes which have been visited
 # and who&#x27;s neighbors have been inspected
 open_list = set([start_node])
 closed_list = set([])

 # g contains current distances from start_node to all other nodes
 # the default value (if it&#x27;s not found in the map) is +infinity
 g = {}

 g[start_node] = 0

 # parents contains an adjacency map of all nodes
 parents = {}
 parents[start_node] = start_node

 while len(open_list) &gt; 0:
 n = None

 # find a node with the lowest value of f() - evaluation function
 for v in open_list:
 if n == None or g[v] + self.h(v) &lt; g[n] + self.h(n):
 n = v;

 if n == None:
 print(&#x27;Path does not exist!&#x27;)
 return None

 # if the current node is the stop_node
 # then we begin reconstructin the path from it to the start_node
 if n == stop_node:
 reconst_path = []

 while parents[n] != n:
 reconst_path.append(n)
 n = parents[n]

 reconst_path.append(start_node)

 reconst_path.reverse()

 print(&#x27;Path found: {}&#x27;.format(reconst_path))
 return reconst_path

 # for all neighbors of the current node do
 for (m, weight) in self.get_neighbors(n):
 # if the current node isn&#x27;t in both open_list and closed_list
 # add it to open_list and note n as it&#x27;s parent
 if m not in open_list and m not in closed_list:
 open_list.add(m)
 parents[m] = n
 g[m] = g[n] + weight

 # otherwise, check if it&#x27;s quicker to first visit n, then m
 # and if it is, update parent data and g data
 # and if the node was in the closed_list, move it to open_list
 else:
 if g[m] &gt; g[n] + weight:
 g[m] = g[n] + weight
 parents[m] = n

 if m in closed_list:
 closed_list.remove(m)
 open_list.add(m)

 # remove n from the open_list, and add it to closed_list
 # because all of his neighbors were inspected
 open_list.remove(n)
 closed_list.add(n)

 print(&#x27;Path does not exist!&#x27;)
 return None
</code></pre>
Let's look at an example with the following weighted graph:
We run the code as so:
<pre><code class="hljs">adjacency_list = {
 &#x27;A&#x27;: [(&#x27;B&#x27;, 1), (&#x27;C&#x27;, 3), (&#x27;D&#x27;, 7)],
 &#x27;B&#x27;: [(&#x27;D&#x27;, 5)],
 &#x27;C&#x27;: [(&#x27;D&#x27;, 12)]
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm(&#x27;A&#x27;, &#x27;D&#x27;)
</code></pre>
And the output would look like:
<pre><code class="hljs">Path found: [&#x27;A&#x27;, &#x27;B&#x27;, &#x27;D&#x27;]
[&#x27;A&#x27;, &#x27;B&#x27;, &#x27;D&#x27;]
</code></pre>
Thus, the optimal path from <code>A</code> to <code>D</code>, found using A*, is <code>A</code>-&gt;<code>B</code>-&gt;<code>D</code>.

Vladimir Batoćanin

A* Search Algorithm

Dijkstra's Algorithm vs A* Algorithm

Minimum Spanning Trees - Prim's Algorithm

Minimum Spanning Trees - Borůvka's Algorithm

Minimum Spanning Trees - Kruskal's Algorithm

Graphs are an extremely versatile data structure. More so than most people realize! Graphs can be used to model practically anything, given their nature of modeling relationships and hierarchies.
<blockquote>
Nature and human creations are very hierarchical.
</blockquote>
Words in a sentence, and sentences in a book can be graphs - represented as a grid. Pixels in an image can be a graph as well. A graph can represent a sequence of steps you want to take, or a sequence of operations an algorithm runs. A graph can represent a molecule, their arrangements, up to humans and their relationships, up to streets and intersections, up to cities, countries, planets!
<blockquote>
From an atomic scale to a universe scale - graphs can be used to model any sort of relationship or hierarchy.
</blockquote>
Many common problems in the world can be represented in graphs. Where to open up restaurants to cover an area with guaranteed delivery times, with the minimum investment? Where to route a driver to avoid congestion and get to a target place as soon as possible? How to organize the flow of electrical energy in a city's grids? There isn't a shortage of problems that are inherently graph-based.
<blockquote>
Getting started with graphs can be daunting. Literature can be scattered and searching online typically involves various different implementations and a non-continuity between the material you're reading.
</blockquote>
For that reason, we're compiling a free introductory course to Graphs in Python, in an attempt to standardize the fundamentals to help you form a solid basis on graph theory.

Graphs in Python - Theory and Implementation

Overview

Lessons