Graph Theory – Introduction To Search Algorithms 1

At a time when COVID-19 has shaken us so much, we continue to learn new information in order to spend our days efficiently. Almost every day we go on a new discovery, a new knowledge.

And you know that the main purpose of every learned knowledge is to make our knowledge valuable day by day by basically making the structure understandable. I also wanted to explore with certain search algorithms for graphs that are types of data structures without being too boring with you.

There are certain steps that we will take as a priority in almost all studies done on behalf of data science, both in the sections read about computers and in the case of data science.

  1. What Is Data?
  2. Why Is Data Processed?
  3. What Are Data Structures?

Of course, we can produce many more questions that we have to solve. In other articles, we talked about what the data was and why it was processed. Today I came to introduce you to a different data structure. When we first learned to program, we were told about operations on nodes and lists in order to be understood.

Graph Theory

The foundations of this theory, a branch of mathematics that studies graphs, were laid out by Leonhard Euler in 1736. I think the name Euler is unfamiliar to many people! We had the opportunity to meet our uncle Euler very closely in the course of numerical analysis and data structures at the University.

I’ m writing you a biographical link to read his work on mathematics and computer science. Now we’ll start talking a little more technical 🚀

A graph consists of nodes and the edges connecting these nodes. I’m putting a little visual down for you to guide.

As you can see, the nodes are connected with their neighbors by bonds called EDGES. Since you have seen the overall structure, I’ ll recommend a graph site that you can prepare your graph structures online. You can see your graph structures visually and have many advantageous structures!

As a programming language, I prefer the C language to go from the simplest and basic. If you wish, I can recommend Python with many ready-made libraries. Or you can create your own graph and search in many different programming languages.

I have determined the graph structure in the above image according to my choice. You can easily create the graph of the structure you want. Our original graph consists of 6 nodes. In order to create this graph on the code, the hills and edges given by the add_edge( ) function are created within the main function.

First, we will create an empty graph on the CreateNullGraph( ) function. Then we will add the nodes and the edges in order. Let’s examine the function add_edge(G,1,2,0,0). The desired situation is that nodes 1 and 2 on the graph G are created directionless because the next parameter is 0 and weightless because it is 0 again.

At the end of my article, I will have access to the codes via GitHub. For this reason, just understand the logic of the algorithm and the data structure, to begin with, will be enough. Next thing you know, you’re creating the codes yourself!

DFS (Depth-First) SEARCH ALGORITHM

The DFS search algorithm is an algorithm used to search tree or graph data structures. The algorithm goes from the node it started searching to the deepest node it could reach, rewinds when there is no deeper node left to go, and continues to travel by prioritizing the deeper nodes.

After the graph shown in the figure is created with add_edge( ), the DFS search algorithm works with the stack structure in the background. As you can see, a deep priority search will be performed by starting from any node (hill). The starting node for this graph is indicated as 0, as indicated in the following image. This image shows the final invocation of the DFS function.

Working Principle and Flow Chart

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

I have given pseudocode DFS search algorithm function C code for you in the following image gives place. I wrote the comments as a comment line at each step, you can read them with pleasure.

When the DFS function created above is executed, it must first take the sequence Graph* G, vertices, and visited[ ] as parameters. For the DFS algorithm, whose starting node is specified as 0 in the main function, 0 is considered in the stack. Because node 0 is visited, the visited [vertex] directory is changed to 1, which means it is navigated. This change is carried out respectively for the neighbors of the hills as seen in the figure below. I’ve shown the stack structure change one by one in the boxes.

We are temporarily creating a variable called tmp to hold the hills. In order for the selected hills to match the search algorithm, searching must be done until the tmp variable is NULL (no neighbors are found). Each time the DFS function is called repeatedly instead of typing the function, the search will be performed.

Then in the main function, we defined the sequence of visits to start with a loop so that all hills are navigated by the loop as 0. We’ ll call the function as shown below.

You can print to the screen with the printf command to check the navigated peaks and edges.

For those who want to use Python, I want to give a little nuance. In addition to the C programming code, the Python programming language is also created with the graf sequence, followed by the DFS function being called. As in C, the search algorithm is executed with the stack structure, with the hills and neighbors push – pop operation.

As a result of my research, I have obtained a nice Python code, you can examine the link I left.

There are many beautiful resources available for deep priority searches. Before you tell the machines, understand and practice it yourself so that you can tell them the algorithm like a teacher. Once we find out, we’ll take those papers and pencils and solve them with plenty of practice!

If you follow my advice, you’ll see how easy it is. Here you can access the GitHub link which contains the codes I used in this article. We learned the DFS Algorithm, How about learning the BFS algorithm?
So I hope to see you in my next post.

REFERENCES

From Wikipedia, The Free Encyclopedia, “Graph Theory”, https://en.wikipedia.org/wiki/Graph_theory.

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

https://graphonline.ru/en/

https://www.biography.com/scientist/leonhard-euler

Related Posts

Leave a Reply