Graph Theory – Introduction to Search Algorithms 2

Hello everyone, we continue to sip our coffees and get new information from our place. We’ re here to study graph theory again. Now that the DFS algorithm has been learned, we can start our new content, the BFS algorithm. So what could be the difference between BFS and DFS algorithms? Let’s take a quick look at the information I’ve gathered with you from different sources, shall we?

BFS (BREADTH-FIRST SEARCH) ALGORITHM

This term, referred to as shallow priority search (transverse search), is an algorithm that searches the nodes of a graph by prioritizing those closer to its starting point. The algorithm adds all the neighbors of the nodes it visits a queue and selects the nodes it visits according to the order in the queue. If the graph is a tree, there is no need to use a tail. But if you’ve noticed, this time in our graph theory, we’re using a queue, not a stack structure.

If you remember in the DFS algorithm, you could identify the node and navigate to the farthest node on the edge of that node and then navigate to the other nodes. However, the BFS algorithm does not work with this logic. Let’s go a little deeper.

In the BFS sorting algorithm, all neighbors of that node are visited by starting from the starting node. Then your neighbor will visit your neighbors. This way all graph is toured.

Working Principle and Flow Diagram

In order to better understand our structure, the solution structure of an example problem with a flow chart according to the BFS search algorithm is given below.

Breadth-First Search Example

The original graph that we used in the project will be used in this article in the same way that it was used in the DFS search algorithm.

The BFS search algorithm works with the queue structure after the edges in the graph are created with add_edge (), as I showed in the content of the DFS search algorithm. Because the BFS algorithm works with queuing, it acts with FIFO (First In First Out) logic. The logic of working with another expression is in the form of the first input first output. Starting from any node (peak), a shallow priority search will be performed, and for this graph, the starting node is specified as 0, as indicated in the figure.

This is completely dependent on the person who wrote the code, so the user can write whatever node he wants. In the C code, I have shown below, 2 nodes are sent as the initial parameter to the BFS function.

In the C code that I just put down, the variables are created by taking the number of peaks of the graph and the distance matrix sequences that are visited until all the peaks in the graph are navigated are assigned as 0.

This image has an empty alt attribute; its file name is Ekran-Resmi-2020-07-29-12.06.47.png
Creation Of The BFS Function

Node 0 in the visited array is sent to the function as not visited(0) at the start, and this peak is now shown as 1 in the visited array, as it suffers from the hill. According to the BFS algorithm, the neighbors of the selected node should be searched.

For example, let the neighbors of node 0 be 1 and 2. After checking whether these hills are on the list, and enqueue must be made. and adjacent peaks 1 and 2 are temporarily held in the tmp variable. Then, when the following figure is examined, tmp != NULL is made to check whether the neighbors are empty or not.

Printing Of Neighbors

The neighbors variable must be printed as follows in order to print the neighbors of Hill 0, Hills 1 and 2. In this way, the neighbors of all the hills will be printed during the search period.

In the BFS function, while checking whether the nodes visited are in the list, the distances between the hills are also updated, and as a result of these changes, the most recent distances are given in the form of the following values.

Updating Distance Variables Throughout The Search
Printing Distance Variable On Screen

Come on, let’s see these distance variables on the console screen and check the chart I drew for you 🚀

This image has an empty alt attribute; its file name is Ekran-Resmi-2020-07-29-12.16.23.png
Shortest Distance Between Hills
This image has an empty alt attribute; its file name is Ekran-Resmi-2020-07-29-12.17.39.png
Shaping The Distance Of Hill Zero To Other Hills

First of all, we have to start by learning graphs well. Once the data structures are well understood, you can switch to writing code.
As a result, that was all I had to say, but no stopping, we continue to work! May you stay well.

REFERENCES

From Wikipedia, The Free Encyclopedia, “Breadth-first search”, https://en.wikipedia.org/wiki/Breadth-first_search.

VivaDifferences, “8 Difference Between DFS (Depth First Search) And BFS (Breadth-First Search) In Artificial Intelligence”, https://vivadifferences.com/difference-between-dfs-and-bfs-in- artificial-intelligence/.

http://web.karabuk.edu.tr/hakankutucu/BLM222notes.html.

Leave a Reply