Hands-on Graph Algorithms

Do you know that almost all kinds of problems in the world can be solved by making some roads and city problems? When graph theory was born, you and I were not even born, and there were no computers in the world! In the late 1700s, Leonard Euler invented graph theory to solve Königsberg’s seven bridges problem. It soon became clear to everyone that no graph algorithm was capable of modeling any problem as a city-road problem. And whenever you can convert a problem into a known problem, it becomes much easier to solve.

Graph algorithms have many applications in practice. For example:

The most common is to find the shortest path. That route can be from one city to another city or from one airport to another airport. You may know that a webpage from the server has to go through many routers to reach your PC, graph theory is used to find the path from one router to another. Google Maps uses graph theory to guide you.

During the war, if some roads of a country are blown up with bombs, the country’s capital will be separated from all the cities, it can also be deduced by graph theory.

You want to build some new flyovers in the city. You have to know where the flyover will be more effective, how it will affect the traffic jam in which part, using graph theory.

We will see many more such uses when looking at various applications of graph algorithms. This chapter is divided into several parts:

In the first part we will learn some definitions that you may not know. If you know a bit about graph theory then you can skip this part.

In the second part we will learn how to store a graph in a computer using a programming language.

Coming in Part 3 we are ready to learn Algorithms. Now we will learn various graph algorithms and solve some related problems.

There is not much to know before learning about graph algorithms. These I will write using C++’s standard template library. If you know about vectors, queues, priority queues etc. then the task becomes easier. You are Java, Python

Or if you know another language, you can use the library there.

Part I: Definitions

What is the graph?

Let’s say we marked 6 cities with 1,2,3,4,5,6. Now I draw a line between the cities that have direct roads to them:

This is a very simple graph showing the roads between some cities. In the language of graph theory, cities are called nodes (Node) or Vertex (Vertex) and roads are called Edge (Edge). A graph is a collection of some nodes and some edges.

A node is an object that can mean many things in a graph, a node may mean a city in a graph, an airport in a graph, or a room on a chess board in a graph! And edge means the relationship between the nodes. An edge in a graph can show the distance between two cities, in a graph it can show the time to go from one airport to another, and if there is a knight in a room on the chess board, it can also show which room can be reached from that room.

The chess board in the picture below is also a graph. Each cell is a node. The edges are shown from the room where the horse is

In short, the job of a node is to represent some kind of object and the job of an edge is to show the relationship between two objects.

B is called an adjacent node of A if there is an edge from node A to node B. Simply put, adjacent nodes are nodes directly connected by edges. A node can have many adjacent nodes.

Directed Graph and Undirected Graph:

In directed graph the edges have arrows, that means the edges are unidirectional, in undirected graph the edges are bidirectional. The following image will make it clear:

The graph on the left is directed, the right is undirected.

Weighted and Unweighted Graph:

Sometimes a graph may have Weight or Cost written in small letters next to the edges:

This weight or cost can mean many things, like how many kilometers are the distance between two cities, or how long does it take to travel through the road, or how many cars can travel along the road, etc. The previous graphs were unweighted, in which case we do not assume that all edges have a weight value of one (1). If all weights are 1, there is no need to write them separately.

path:

Path (Path) is the edges that can go from one node to another node. That is, a sequence of edges.

There can be many paths from one node to another. There are two paths from A to D in the figure. A->B,B->C,C->D is a path, the total weight of this path is 3+4+2=9. Again A->D can also be a path such that the total cost of the path is 10. The path which has the least cost is called the shortest path.

Degree:

In a directed graph, the number of edges entering a node is called indegree, and the number of edges leaving a node is called outdegree. The figure shows the indegree and outdegree of each node:

An undirected graph does not distinguish between indegree and outdegree. The number of adjacent nodes a node has is the degree of the node.

The Handshaking Lemma states that the number of nodes of an odd degree is always even. In the graph above, A and C have degree 3, they are nodes of odd degree. Then there are 2 nodes of odd degree, 2 being an even number. A handshake always takes 2 hands, just like an edge always connects 2 nodes. Just think about it:

Adding 2 even degree nodes with an edge creates 2 new odd degree nodes.

Adding 2 odd degree nodes with an edge reduces 2 odd degree nodes.

Adding 1 even and 1 odd degree node equals the total number of odd degree nodes (decrease on one side, increase on other side).

## Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.

Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free

## Thank You,

Stay with FreeWebsiteCreate.net

Share the post if necessary.

FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.

They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.

To get a free website project code,