Nicholas Samuel

Dimitrije Stamenic

Guide to Dictionaries in Python

<h2 id="introduction">Introduction</h2>
Basic data types in Python allow us to store a single value under a symbolic name. This roughly follows the mathematical notation of variables. In a way, a name is assigned to a value, so you don't need to remember the actual value, nor its address in computer memory, just a simple, illustrative name.
But, if you need to store a collection of values under one variable name, basic data types won't do the job. You'll need to use more complex data structures. Python has four data types for storing a collection of values under the same name - <a href="https://stackabuse.com/lists-vs-tuples-in-python/" target="_blank">Tuple</a>, <a href="https://stackabuse.com/sets-in-python/" target="_blank">Set</a>, <a href="https://stackabuse.com/python-dictionary-tutorial/" target="_blank">Dictionary</a>, and List. We'll focus on the latter in this article.
A List is a Python data type similar to an array in any other programming language. It stores an ordered collection of values under the same name. Also, it allows duplicate values, as well as changing values of stored elements. The only difference between a List and any usual array is that not all the elements of a List need to have the same data type (it's heterogeneous). For example, one List may contain integer elements, floating-point numbers, strings, as well as other Lists, and any other data type elements:
<pre><code class="hljs">example_list = [1, 3.14, &#x27;abcd&#x27;, [4, 3, 2, 1]]
</code></pre>

 <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>
 
 <div class="w-full">
 Note: You create a Python List by listing its elements between two square brackets - <code>[...]</code>. Each element is separated by a comma - <code>,</code>. Python has an <code>array</code> type, separate from Lists and shouldn't be confused with Lists.

 </div>
 </div>
 </div>
 <blockquote>
In this guide, we'll take a look at how to add elements to the end of a List in Python, how to merge lists, etc. using the <code>append()</code> method, and compare it to other methods used to add elements to a List - <code>extend()</code> and <code>insert()</code>.
</blockquote>
<h2 id="howtoappendelementstoapythonlistusingappend">How To Append Elements to a Python List Using append()</h2>
Appending elements to a List is equal to adding those elements to the end of an existing List. Python provides several ways to achieve that, but the method tailored specifically for that task is <code>append()</code>. It has a pretty straightforward syntax:
<pre><code class="hljs">example_list.append(element)
</code></pre>
This code snippet will add the <code>element</code> to the end of the <code>example_list</code> (which is of <code>list</code> type). As we've stated before, a list can contain elements of different data types. Therefore, <code>element</code> can be of any possible data type - <code>int</code>, <code>float</code>, <code>str</code>, <code>list</code>, <code>tuple</code>, and so on.
In the following sections, we'll go over some practical examples illustrating how to append an individual element to a list, as well as how to append one list to another.

 <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>
 
 <div class="w-full">
 Note: In the following examples, we use a List containing elements of different types.

 </div>
 </div>
 </div>
 <h3 id="howtoaddasingleelementtotheendofapythonlist">How To Add a Single Element to the End of a Python List</h3>
Adding a single element illustrates the main purpose of the <code>append()</code> method in Python. Let's assume you have an example list:
<pre><code class="hljs">example_list = [1, 3.14, &#x27;abcd&#x27;]
</code></pre>
You would add <code>5</code> to the end of the <code>exampe_list</code> in the following way:
<pre><code class="hljs">example_lsit.append(5)
</code></pre>
Now, the <code>example_list</code> will have <code>5</code> added to its end:
<pre><code class="hljs">[1, 3.14, &#x27;abcd&#x27;, 5]
</code></pre>
<h3 id="howtoappendonelisttoanotherinpython">How To Append One List to Another in Python</h3>
Assume you have two lists and want to append one to another:
<pre><code class="hljs">example_list = [1, 3.14, &#x27;abcd&#x27;]
secondary_list = [4, 3, 2, 1]
</code></pre>
The <code>append()</code> method doesn't provide a way to append two lists together in one method call. If you try to append those two lists using <code>append()</code>, the whole <code>secondary_list</code> will be added as a single element of the <code>example_list</code>, creating a nested list:
<pre><code class="hljs">example_list.append(secondary_list)
print(example_list)
</code></pre>
Now, the <code>example_list</code> contains the following elements, which are probably not what you wanted in the first place:
<pre><code class="hljs">[1, 3.14, &#x27;abcd&#x27;, [4, 3, 2, 1]]
</code></pre>
Appending one list into another using <code>append()</code> is achieved by iterating over all elements of a list we want to append and appending each of them to the original List :
<pre><code class="hljs">for element in secondary_list:
 example_list.append(element)

print(example_list)
</code></pre>
That way, we've appended the <code>secondary_list</code> to the end of the <code>example_list</code>:
<pre><code class="hljs">[1, 3.14, &#x27;abcd&#x27;, 4, 3, 2, 1]
</code></pre>
<h2 id="alternativestoappendinpython">Alternatives to append() in Python</h2>
Python List has a couple more methods for adding elements besides <code>append()</code>. Most notably, <code>extend()</code> and <code>insert()</code>. In the following subsections, we'll get into the differences between them and the <code>append()</code> method.
<h3 id="appendvsextend">append() vs extend()</h3>
As we've seen in previous sections, <code>append()</code> is intended to add one element to the end of a List. On the other hand, <code>extend()</code> is used to add multiple elements to the end of a List - effectively, it appends one list to another. Let's see how <code>extend()</code> works:
<pre><code class="hljs">example_list = [1, 3.14, &#x27;abcd&#x27;]
secondary_list = [4, 3, 2, 1]

example_list.extend(secondary_list)
print(example_list)
</code></pre>
Output:
<pre><code class="hljs">[1, 3.14, &#x27;abcd&#x27;, 4, 3, 2, 1]
</code></pre>
Note how <code>extend()</code> appends two lists in one call, and the <code>append()</code> needs to be called one time for each element of a List you want to append! It's a handy method to remember as an alternative.
<h3 id="appendvsinsert">append() vs insert()</h3>
There is no way to insert an element to a specific place in a List using <code>append()</code>, it automatically adds it to the end of a List. That's where <code>insert()</code> comes into view!
Unlike <code>append()</code> and <code>extend()</code>, it accepts two arguments - one is the element you want to insert, and the other is the index of that element in a List.
For example, if you want to add <code>'asdf'</code> to the end of the <code>example_list</code> you would use <code>example_lsit.append('asdf')</code>, as we've seen in previous sections. But if you want to add it to a specific place, say, between <code>3.14</code> and <code>'abcd'</code>, you must use <code>insert()</code>:
<pre><code class="hljs">example_list = [1, 3.14, &#x27;abcd&#x27;]
# Insert element `asdf` on the index `2`
example_list.insert(2, &#x27;asdf&#x27;)

print(example_list)
</code></pre>
This results in:
<pre><code class="hljs">[1, 3.14, &#x27;asdf&#x27;,&#x27;abcd&#x27;]
</code></pre>
Note the difference in indexing of the original and resulting lists. In the original <code>example_list</code>, the element on index <code>2</code> is <code>'abcd'</code>. After adding <code>'asdf'</code>, it is on the index <code>2</code>, and the <code>'abcd'</code> is shifted to the index of <code>3</code>.
<h2 id="conclusion">Conclusion</h2>
After reading this guide, you should have a better understanding of how to use <code>append()</code> method on Python Lists and how it compares to other Python methods for adding elements to a List.
<blockquote>
For a more in-depth comparison of those methods, you should definitely take a look at the following guide - <a href="https://stackabuse.com/append-vs-extend-in-python-lists/" target="_blank">append() vs extend() vs insert() in Python Lists</a>.
</blockquote>

David Landup

In this tutorial - learn how to append, insert and extends lists in Python with practical code examples.

Guide to Python's append() Function

<h2 id="introduction">Introduction</h2>
A character counter is a handy UI feature that displays the remaining number of characters a user can input in a text field - if a text field is bound to a relatively small input size (such as Twitter's limit on 280 characters per tweet). This feature is commonly used alongside text area and/or input field elements to notify a user of the number of used and remaining characters.
<blockquote>
In this article, we will learn how to implement a character counter for text areas in JavaScript from scratch.
</blockquote>
Probably the most famous example of a character counter is Twitter's character counter. It notifies you when the length of your tweet approaches and exceeds 280 characters, but doesn't prevent you from typing more characters. This feature is widely beloved because it doesn't cut off text when you paste a chunk of text longer than the prescribed length of characters and allows you to appropriately plan how you'll break it down into multiple tweets!
By the end of this article, you will be able to make an input field like this:
<img src="https://s3.stackabuse.com/media/articles/character-counter-for-text-areas-with-vanilla-javascript-1.gif" alt="character-counter-javascript">

 <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>
 
 <div class="w-full">
 Note: All of the code involved in creating the form will be present in the guide. Additionally, the source code and live preview are available on <a rel="nofollow noopener" target="_blank" href="https://codepen.io/stamd/pen/BaJJrdq">CodePen</a>.

 </div>
 </div>
 </div>
 <h2 id="howtoimplementacharactercounterinjavascript">How to Implement a Character Counter in JavaScript</h2>
The first thing we need to set up before implementing the character counter is a basic HTML form. It will contain a <code>textarea</code> field and a text representing a character counter. It displays the maximum number of characters and the number of characters left. If the allowed number of characters is exceeded, the text changes color to red:
<pre><code class="hljs">&lt;form&gt;
 &lt;h3&gt;Write Bio: &lt;/h3&gt;
 &lt;textarea name=&quot;tweet&quot; id=&quot;textbox&quot; class=&quot;form-control&quot; rows=&quot;10&quot; cols=&quot;60&quot;&gt;&lt;/textarea&gt;
 &lt;span id=&quot;char_count&quot;&gt;100/100&lt;/span&gt;
 &lt;button type=&quot;submit&quot;&gt;Save&lt;/button&gt;
&lt;/form&gt;
</code></pre>
<h3 id="declaringvariables">Declaring Variables</h3>
After creating a basic HTML form, the next step is to implement a character counter logic using JavaScript. The first step in creating the JavaScript logic is to define our variables and obtain the DOM components we'll be utilizing later. Specifically the <code>textarea</code> field and the <code>span</code> element displaying the character counter:
<pre><code class="hljs">let textArea = document.getElementById(&quot;textbox&quot;);
let characterCounter = document.getElementById(&quot;char_count&quot;);
const maxNumOfChars = 100;
</code></pre>
The <code>textArea</code> will be used to add an event that will activate the logic function. There are numerous events we can use, but the <code>keyup</code> is the best fit for this use case since it will trigger the logic function every time a key is pushed - a character is added or removed from the <code>textarea</code>. The <code>characterCounter</code> is used to display the character counter, and the <code>maxNumOfChars</code> defines the maximum number of characters a user can enter.
<h3 id="implementingthelogic">Implementing The Logic</h3>
The next step would be to create the fundamental logic that allows us to determine the length of the text typed into the <code>textArea</code>, as well as to deduct the length from the maximum number of characters we've chosen. This is what the structure of the logic function could look like:
<pre><code class="hljs">const countCharacters = () =&gt; {
 // Calculate the number of characters entered into the textarea
 // Calculate the number of characters left
 // Display this number in the span tag
};
</code></pre>
And here is how the implementation of the mentioned structure looks like:
<pre><code class="hljs">const countCharacters = () =&gt; {
 let numOfEnteredChars = textArea.value.length;
 let counter = maxNumOfChars - numOfEnteredChars;
 characterCounter.textContent = counter + &quot;/100&quot;;
};
</code></pre>

 <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>
 
 <div class="w-full">
 Note: Please keep in mind that <code>countCharacters()</code> does not handle any style at the moment. For example, we'd like to turn the counter color to red when the maximum number of characters is being approached or exceeded. We'll implement this in a moment, since it's a more subjective type of addition.

 </div>
 </div>
 </div>
 Finally, in order for this to work, we must add an <code>eventListener</code> that will trigger/call this method anytime a character is added/removed from the <code>textarea</code> field by using the <code>input</code> event. Alternatively, we can use the <code>keyup</code> or <code>keydown</code> events instead:
<pre><code class="hljs">textArea.addEventListener(&quot;input&quot;, countCharacters);
</code></pre>
<h3 id="customizingthecountercolor">Customizing The Counter Color</h3>
We'd like to 'alert' a user when the defined maximum number of characters is surpassed as well as when they're approaching it. This is readily accomplished by using conditional statements where we check if the <code>counter</code> is less than zero or less than, say, <code>20</code> if we want to alert them that they're approaching the limit:
<pre><code class="hljs">if (counter &lt; 0) {
 characterCounter.style.color = &quot;red&quot;;
} else if (counter &lt; 20) {
 characterCounter.style.color = &quot;orange&quot;;
} else {
 characterCounter.style.color = &quot;black&quot;;
}
</code></pre>
Here, we've only changed the text based on the number of characters left. There's a lot you can change there. For example, you can disable the <code>textarea</code> if too many characters are typed, truncate the content automatically, and so on.
<h2 id="conclusion">Conclusion</h2>
In this short guide - we've taken a look at how to create a character counter and attach it to a text area in JavaScript, from scratch, with minimal and performant code.

Joel Olawanle

In this tutorial, you'll learn how to implement a custom character counter for text areas in JavaScript, from scratch.

Character Counter for Text Areas with Vanilla JavaScript

<h2 id="introduction">Introduction</h2>
An <code>Array</code> in JavaScript is a standardized, built-in object used to store multiple objects under the same name. In simple terms, you can look at the <code>Array</code> object as an array in any other programming language. It is essentially a class that encapsulates an array (an ordered list of values) and all necessary methods you might need to perform array operations.
The fact every array is ordered means that the place of each element is of great importance. In fact, you can't even extract the value of an element if you don't know its place in the original array.
During iteration, the index of the current element may be relevant to you. This is very straightforward to achieve using the <code>index</code> parameter of the <code>forEach()</code> method.
<blockquote>
In this article, we'll see how to get the current element's array index in JavaScript using the <code>forEach()</code> method.
</blockquote>
<h3 id="foreachmethodbasics">forEach() Method Basics</h3>
The <code>forEach()</code> is a method of the <code>Array</code> class. You can use it to loop through an array and perform a certain operation on each of its elements - though, <code>map()</code> is more commonly used for this purpose. You can customize the performed operations using a callback function - a function passed as a parameter of the <code>forEach()</code> method. A callback function is a simple function that defines the operation to be performed on a single element, and the <code>forEach()</code> method makes sure it will be performed on each element of an array.
The <code>forEach()</code> method has a pretty straightforward syntax:
<pre><code class="hljs">forEach(callback(currentElement, index, arr), thisValue);
</code></pre>
As we've stated before, the <code>forEach()</code> method accepts a <code>callback</code> function that runs on each entry in the array. This <code>callback</code> function takes in three arguments, of which we are only concerned about two - the <code>currentElement</code> which is a required parameter, and its <code>index</code> which is the position of the <code>currentElement</code> in the array.
<h3 id="howtogettheindexofthecurrentelementusingforeachmethod">How to Get the Index of the Current Element Using forEach() Method</h3>
Suppose we have an array of students, and would like to access the index of each element as we're processing them. We'll make use of the <code>index</code> argument, and simply print it out:
<pre><code class="hljs">const students = [&quot;Mark&quot;, &quot;Jane&quot;, &quot;John&quot;, &quot;Sarah&quot;];

students.forEach((student, index) =&gt; {
 console.log(`The index for ${student} is ${index}`);
});
</code></pre>
Output:
<pre><code class="hljs">&quot;The index for Mark is 0&quot;
&quot;The index for Jane is 1&quot;
&quot;The index for John is 2&quot;
&quot;The index for Sarah is 3&quot;
</code></pre>
<h2 id="conclusion">Conclusion</h2>
In this short article, we've explained how to use the <code>index</code> parameter to get the current array index of elements in an <code>Array</code> using the <code>forEach()</code> method.

 <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>
 
 <div class="w-full">
 Note: If you need to dig deeper into the <code>forEach()</code> method in JavaScript, read our <a href="https://stackabuse.com/guide-to-javascripts-foreach-method/" target="_blank">Guide to JavaScript's forEach()</a>.

 </div>
 </div>
 </div>

In this short tutorial, learn how to get the index of an element inside of the `forEach()` method of the JavaScript array class.

Get the Current Array Index in JavaScript's forEach()

In this guide, learn everything you need to know about JavaScript's forEach() Method - loop through array, set or map, sum elements or their fields, variable scope, optional parameters, async/await, how to break out of a forEach()/for loop as well as the difference between forEach() and for.

Guide to JavaScript's forEach() Method

Guide to Creating Charts in JavaScript With Chart.js

Anđela Niketić

Jovana Ninkovic

In this guide, learn the theory and implementation of Breadth-First Search and Breadth-First Traversal (BFS and BFT) in Python, with practical code examples.

Graphs in Python: Breadth-First Search (BFS) Algorithm

<h2 id="introduction">Introduction</h2>
Originating from mathematics, graphs are now widely used data structures in Computer Science. One of the first problems we encounter when constructing any algorithm regarding Graph processing or traversal is how we represent the graph and then, how to traverse that representation.
<blockquote>
Graph traversal is not a trivial problem, and given the difficulty of the task - many algorithms have been devised for efficient (yet not perfect) graph traversal.
</blockquote>
In this guide, 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 <a target="_blank" href="/graphs-in-python-breadth-first-search-bfs-algorithm/">Breadth-First Search (BFS)</a> 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.
<ul>
<li><a target="_blank" href="/graph-theory-and-graph-related-algorithms-theory-and-implementation">Graph Theory and Graph-Related Algorithm's Theory and Implementation</a>
<ul>
<li><a target="_blank" href="/graphs-in-python-representing-graphs-in-code/">Representing Graphs in Code</a></li>
<li>Depth-First Search (DFS)</li>
<li><a target="_blank" href="/graphs-in-python-breadth-first-search-bfs-algorithm/">Breadth-First Search (BFS)</a></li>
<li><a target="_blank" href="/dijkstras-algorithm-in-python/">Dijkstra's Algorithm</a></li>
<li><a target="_blank" href="/basic-ai-concepts-a-search-algorithm/">A* Search</a></li>
<li><a target="_blank" href="/boruvkas-algorithm-in-python-theory-and-implementation">Minimum Spanning Trees - Borůvka's Algorithm</a></li>
<li><a target="_blank" href="/graphs-in-python-minimum-spanning-trees-prims-algorithm">Minimum Spanning Trees - Prim's Algorithm</a></li>
<li><a target="_blank" href="/graphs-in-python-minimum-spanning-trees-kruskals-algorithm/">Minimum Spanning Trees - Kruskal's Algorithm</a></li>
</ul>
</li>
</ul>
<h2 id="depthfirstsearchtheory">Depth-First Search - Theory</h2>
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.
<h2 id="thedfsalgorithm">The DFS Algorithm</h2>
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>
 
 <div class="w-full">
 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>
 </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.
<h3 id="pseudocode">Pseudocode</h3>
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.
<h2 id="depthfirstsearchimplementation">Depth-First Search - Implementation</h2>
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>
 
 <div class="w-full">
 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>
 </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.
<h2 id="runningdfs">Running DFS</h2>
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 <a target="_blank" href="/graphs-in-python-representing-graphs-in-code/">article</a> 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>
 
 <div class="w-full">
 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>
 </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.
<h2 id="conclusion">Conclusion</h2>
In this article, we've explained the theory behind the Depth-First Search algorithm. We've depicted the widely-used recursive Python implementation, and went over the borderline cases for which the algorithm will not work properly.

In this guide, we've gone over the theory and implementation of Depth-First Search (DFS) in Python.

Graphs in Python: Depth-First Search (DFS) Algorithm

In this guide - learn how to represent graphs in Python, as an adjacency matrix, adjacency list and list of edges, with practical code examples and pros and cons.