Enhancing the Performance of Graph Algorithms

Enhancing the Performance of Graph Algorithms — Part 1

Introduction to the Graph Algorithms

We use various types of Data Structures according to the need we have. We are going to discuss Graphs and the way of optimizing the graphs as required for our problem definitions.

What is a Graph?

Graphs are widely used nowadays. They are used in economics, aviation, physics, biology (for DNA analysis), mathematics, and other fields. A graph is a non-linear Data Structure with nodes(vertices) and edges in Computer Science that is used to implement the undirected graph as well as directed graph theories from the domain of graph theory within Mathematics.

There are two types of Graphs that are needed to this level.

Directed graph
undirected graph

Graph Algorithms

One of the crucial operations that can be performed on graphs is traversing or searching. There are several algorithms that work on the Graphs. Such as

1 — Dijkstra’s shortest path algorithm

2 — Greedy algorithm

3 —Astar algorithm

4 — Depth-First Search algorithm

5 — Breadth-First Search algorithm

6 — Bellman-Ford algorithm

7 — Floyd cycle detection algorithm

8 — Prim’s algorithm

9 —Kahn’s algorithm

10 — Tarjan’s strongly connected components algorithm

11 — Brent’s algorithm

12 — Kruskal’s algorithm

13 — Kosaraju’s algorithm

14 — Ford-Fulkerson algorithm

15 — Edmonds–Karp algorithm

16 — Dinic’s algorithm

17 — Hopcroft-Karp algorithm

18 — Hungarian algorithm

19 — Blossom algorithm

Time Complexity

The most famous solution for finding the shortest path was first proposed by Dijkstra. Generally, his solution is the most efficient and used in most cases. On average each of N nodes is processed, and for each, all of its neighbors are updated in O(N). Thus the complexity is O(N²).

How to reduce the Time Complexity?

Well, let’s discuss it in the next part. In the meantime, try to implement these Graph Algorithms and understand their core concepts.

Hope this can help. Share your thoughts too.

Comments

Hello World project in ROS on Windows 10

We've seen how to install ROS in Windows 10 in this article, this is the time to start programming. What is the very first thing we do once we setup a new Programming Language? Hello World !!! Lets see how to write Hello World in ROS on Windows machine. Before going into the programming, make sure you've installed Gedit on your Windows machine. You can get it from here. Also, setup the path for Gedit and restart your machine to ensure the path definition works. First open the ROS terminal and check for the working directory. We have to be in the catkin workspace. If you've already created it, go to that directory. Or else, create it like this. Create a src folder inside catkin_ws. Inside that newly created src folder, lets create a new package in it. The command to create a ROS package is as follows. >catkin_create_pkg [PACKAGE_NAME] [DEPENDENT_PACKAGE_1] ....[DEPENDENT_PACKAGE_N] ‘std_msgs’ and ‘roscpp’ were added as optional dependent packages...

SQL Joins

You’ll nearly always need to connect many tables if you want to extract anything useful out of data. A join clause in SQL joins columns from one or more tables into a new table, similar to a join operation in relational algebra. In this article, let’s see how the joins work in SQL. We are going to explore the following SQL Joins. ∘ 1 — (INNER) JOIN ∘ 2 — LEFT (OUTER) JOIN ∘ 3 — RIGHT (OUTER) JOIN ∘ 4 — FULL (OUTER) JOIN AND UNION ∘ When to use it? Also, I’m going to use the following tables for the above-mentioned SQL Joins. 1 — (INNER) JOIN Returns records with values in both tables that are the same. Image from Author As long as the condition is met, the INNER JOIN keyword selects all rows from both tables. This keyword will produce a result-set by merging all rows from both tables that satisfy the criteria, i.e. the common field’s value will be the same. Syntax: SELECT table1.column1,table1.column2,table2.column1,…. FROM table1 INNER JOIN ...

Collection Framework in Java

Data Structure As a definition, the data structure is a specific method of organizing data in a computer so that it may be used efficiently. In this article, we are going to see about the Collection Framework which enables us to implement some important Data Structures available on Java. Topics covered: ∘ Data Structure ∘ Collection Framework ∘ Class vs Interface ∘ Lists ∘ Set ∘ Map ∘ Difference between List, Set, and Map interface in Java Collection Framework A Java collection is a grouping of separate objects that are represented as a single entity. Java collections, like data, provide all actions such as searching, sorting, insertion, modification, deletion, and so on. Java Collections is a fairly broad topic, and as a newbie, it might be tough to find your way around. We’ve covered all you need to know to get started with Java Collections. Image from https://www.geeksforgeeks.org/how-to-learn-java-collections-a-complete-guide/ W...

Decrypt Here

Search This Blog