Date:

Share:

Graph Theory and Graph-Related Algorithm’s Theory and Implementation

Related Articles

introduction

Graphs are a convenient way to store certain types of data. The term is “stolen” from mathematics and appropriated for the purposes of computer science.

There are several ways we can describe what graphs are. Approach the graphs first in a very simple way, then through trees if the reader is familiar with the concept from previous experience, and finally as Mathematical term.

Simplified graphs

Each graph is complex Nodes (Also called vertices) and Edges. We can look at nodes as “data chunks” and edges as “relationships between these data chunks”.

If we wanted to point out that two pieces of data are related to each other in some way – we would connect them with an edge. Nodes are usually represented as circles with an identification mark on them so that we can distinguish between nodes, and edges are represented by lines (or arrows, as we will see below) that connect two nodes.

A form of graph data structure is often used when creating maps for city bus lines. You will see a simple map that shows at which stations (intersections) the bus stops, and the route that connects different stations is what we call the end:

This graph shows what different bus stops we have and how they are connected. For example, we can see it, using this bus line, to get there Bus stop a To Bus stop C We’ll have to move Bus stop B We can not get there in any other way.

Weighted graphs

Graphs are very diverse, which is one of the reasons why they are so popular. Suppose we wanted to add information about how long it took on average (in minutes) to get from one bus stop to another. We will add “weights” to our edges:

Now our graph shows even more information than before, we see how long it takes to get from one station to another. We can deduce from this from Bus stop a To Bus stop C It will take 23 minutes since we will have to “cross” the end of the connector Bus stop a and Bus stop B That he has a Weight Of 15 and the (Bus stop B -> Bus stop Cedge, which weighs 8.

The previous example introduced the concept of weighted Graphs, meaning that edges can have values ​​attached if required.

Intentional and unintentional graphs

Now let’s look at another graph concept – giving directions and Unintentional Graphs. Suppose our bus line did not have the same stops in both directions.

More precisely, when our bus starts from Bus stop a It passes B, third, And ends in D; However, in the other direction it does not pass third But a completely different bus stop God, Before passing B. Maybe we’ll create something like this:

As the spoiler implies in the picture – this approach is incorrect. Just by looking at this graph we can not understand in which bus stops the bus passes in which direction, since nothing stops us from getting there. B To God Although we should be able to reach only from God To B.

This is where directional graphs come into the picture. The edges in the directed graphs are represented by arrows instead of lines, a pointer arrow A To B Means “we can get from A To B But not the other way around. “If we wanted to say we could have both A To B And B To A, We will use a double-sided arrow.

Now, the cycle is no longer vague:

Now it’s clear we can not go B To God Or m D To third, and so’. Obviously we can create as simple or complex graphs as we want. We could go one step further in our example, if for some reason it took a different amount of time to travel between several bus stops depending on the direction we are going.

Graph applications

Here are some examples of data that can be conveniently stored / represented using graphs:

  • Group of people and their affiliation: This can be done using an unintentional graph, since we assume that if a person A Know a person B, The opposite is true. The different people will be represented by nodes, and if a person A Know a person B Will be the connecting end between the two nodes.
  • Website structure: Various pages on this site are nodes, and there is a deliberate edge between a page A And a page B If link to page B Exists on page A. For example e Home The page often has links to the page about us and contact us.
  • Mutually dependent tasks: We can represent which tasks need to be completed before the task A And which tasks cannot be completed beforehand A Completed as follows – if there is a tuned edge from B To A, Then A Can not be completed before B Completed; If there is a pointed edge from A To third, Then third Can not be completed before A Completed:

Here we can see that we can put on glasses, socks, pants and a T-shirt regardless of other clothes. But we can not wear shoes before wearing pants and socks. And we can not go out before we have done everything else, except to wear glasses, because they may not be needed. These types of graphs are easily sorted and we can see a possible order of performing tasks using Topological classification.

A graph can also be Connected and detached. A graph is connected if there is a path (consisting of one or more edges) between each pair of nodes. On the other hand, a graph is disconnected if there is a pair of nodes that cannot be connected in the path of the edges.

Note: A common mistake is that graphs should be connected, or at least each node should be connected to another in some way. This is not true, and we proved it in the previous example. A graph can be composed just as easily from any number of nodes without a single end between them. However, many transition algorithms demand Graphs that need to be connected to work properly.

Graphs compared to trees

Refer to our practical and practical guide to learning Git, with best practices, industry-accepted standards and a cheat sheet included. Stop Google Git commands and actually Learn This!

If you are familiar with trees, it is easy to understand graphs – trees are a special type of graph, meaning graphs with certain restrictions. Every tree is a graph, but not every graph is a tree.

By definition, trees are unintended graphs that:

  • They are acyclic, meaning we will not be able to switch back to any selected start node without backtracking
  • A cycle is created by adding each end to the existing tree
  • The path between each two nodes is unique
  • There is a distinct root junction
  • The graph is connected (there is a path between each two nodes)

Or in very simple words – trees are connected graphs without cycles. As for graphs, we just get rid of all these restrictions and keep to the concept of nodes and edges.

Graphs as a mathematical term

All of the above comes from the mathematical term of a graph. Graph is a neat pair G = (V, E), Where V Is a set of vertices and E Is the group of edges.

Unadjusted Graphs: In case of unintentional graph, E Has the following definition E ⊆ x, y . Sometimes an additional condition is added if we want to avoid edges that have the same starting and ending point (i.e. x ≠ y).

Directed graphs: E ⊆ (x, y) , Here too we can add the condition that x ≠ y If we want to avoid edges that start and end at the same node / vertex.

As we can see in the previous definitions of the edge group E, The only difference is that in the case of directed graphs (x,y) Is an orderly pair, while in graphs the pair is not directed x,y Is not tidy. This means that in an unintentional graph, what matters is x and y Connected, not in “what order”. So we could write y,x instead of x,y While we could No Wrote (y,x) instead of (x,y) For a directed graph.

All of this leads us to a number of important topics when it comes to moving graphs in Java – Representing graphs in code, First width search, Deep-first search, And Dixtra’s algorithm.

Representing graphs in code

When we know what graphs are, we need a way to represent them in code. This is usually done using Adjacent lists and Thick matrices. In the following article we present an in-depth look at these implementations in Java:

First Depth Search (DFS)

Deep-Frist Search (DFS) searches as much as possible along a branch and then returns to the search as far as possible in the next branch. This means that in the advanced graph, it starts with the first neighbor, and continues along the line as much as possible.

Breadth-First Search (BFS)

First width search (BFS) is a graph crossing algorithm, often used to find the shortest path from a start node to a destination node.

BFS audits “layer by layer”. This means that he first visits all the children of the initial node (the root). These children are considered the “second tier,” and then criticize their children in the same way.

Dixtra’s algorithm

Dixtra’s algorithm Is a graph crossing algorithm very well known for finding the shortest path from a given node / vertex to another.

There are several applications of this algorithm and some even use different data structures and have different applications.

Dixtra works differently from previous algorithms. Instead of starting at the root junction, it starts at the goal junction and returns on its way to the start junction.

A * Algorithm

Minimum Trees (MST)

DFS vs. BFS

A question that probably came to mind when you read about DFS and BFS was:

“What’s the practical difference?”

The theory is clear; BFS first visits the nodes closest to our starting node while DFS goes as deep as possible into the graph (away from our starting node) before continuing with other nodes close to our starting node.

Let’s go over some examples:

  • If all you want to do is check if two nodes are connected at all in the graph that does not give you a clear reason to prefer one or the other of the transition algorithms in the graph – Every one of them
  • If you “know” that your two nodes are close to each other if they are connected at all – for example looking for family members in an introductory graph – use BFS
  • If you want to count all the possible ways to get from one intersection to another – DFS
  • If you want the shortest path (the path that passes with the least number of nodes) from one node to another – BFS
  • DFS Can also be used for some slightly advanced things, like graph cycle detection, or testing Components are tightly connected (A mathematical term meaning “any node can be reached from any other node”) which can later be used to solve 2-SAT (2-SAT) problems.

Summary

Graphs are a convenient way to store certain types of data. Each graph is complex Nodes (Also called vertices) and Edges. We can look at nodes as “data chunks” and edges as “relationships between these data chunks”.

Graph transition algorithms such as BFS, DFS, Dijkstra’s Algorithm and A * are very commonly used in many branches of data science and machine learning.

Source

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Popular Articles