DEV Community: Gaurav

Data Structures : Graph Traversal (DFS)

Gaurav — Thu, 13 Oct 2022 16:37:57 +0000

Depth First Search (DFS) is a graph traversal technique which is used to visit the nodes in a graph.

Start from one node and visit it's adjacent node and then it's adjacent node, keep doing this until you reach the last node and then start backtracking.
While backtracking visit the rest of the adjacent nodes in the same way.

Let's understand this with an example:

Consider this graph and Node 1 as the starting point.
Now as we can see node 1 has two adjacent nodes, 2 & 3 and we can visit any one we want. In this example we'll start with Node 2.
Again node 2 has two adjacent nodes and we'll pick node 5.
This is an important part of the algorithm because there are no adjacent nodes for 5 which means we can't move forward. At this point we start backtracking and move back to node 2.
We notice that node 2 has another node which we didn't visit yet so we'll do just that, we'll visit Node 6.
Again node 6 doesn't have any adjacent node so we'll backtrack to node 2 and since we have visited all the adjacent nodes of 2 we'll backtrack to node 1.
Using the same steps we'll visit all the remaining nodes i.e. 3, 4, 8 & 7.
Now you might ask that there is an edge between node 7 and 3 so do we visit it again? The answer is No because we've already visited node 3 on our way to node 7 and the same logic applies when we backtrack to node 3. We'll see how this is taken care of in the code.
So we've visited all the nodes in the graph and the path is {1, 2, 5, 6, 3, 4, 8, 7}.

Now it's time to code it up but before that I should explain the situation with already visited nodes. Since we have visited the particular node before we don't have to do that again. Now you might be wondering how do we keep track of which node we have visited and which one we haven't and the simple answer is an Array.

We simply create an array of length equal to the number of vertices in the graph and fill it with 0 or false depending on the array type you want. Now as we visit a node we simply mark that index in the array as visited by setting it as 1 or true.

In the next dfs call we will first check if the node we are on is visited or not by simply checking the value at that index in the array. We will look at the code to better understand this.

Steps to sum up the code:

Visited array and a list are created.
Call the dfs on starting node.
Set vis[node] = true and list.add(node).
For each loop on adjacency list and find the adjacent node.
Check if the adjacent node is visited, if not call dfs on it.
The path is stored in list.

Space Complexity: O(N) + O(N) + O(N) Adjacency list, Array, Auxiliary space.

Time Complexity: O(N) + (2*E) Recursion call for each node + Summation of degrees.

That's it for the DFS traversal. I hope this was helpful.
Thanks for reading.

Data Structures : Introduction to Graphs

Gaurav — Mon, 10 Oct 2022 20:56:27 +0000

You are probably familiar with arrays, stacks and linked lists which are linear data structures because they store the data in a sequence. Graph is a non-linear data structure just like a tree data structure. In fact tree is a special kind of data structure with some restrictions.

Graphs have a lot of real world applications like finding the best routes in navigation apps, creating complex electrical circuits, storing useful user information on social media platforms, etc.

Before moving forward we must know the following terms:

Nodes: These are the vertices of the graph that are used to store the data and are connected by edges.
Edges: Two nodes are connected by a horizontal line called an edge. An edge can be directed or undirected. A directed edge means that we can only traverse the graph in one direction which is shown by the edge whereas an undirected edge lets us traverse in any direction.

Graphs are of two types:

Undirected graph: A type of graph in which the nodes are connected by undirected edges.
Directed graph: A type of graph in which the nodes are connected by directed edges.

Cycle in a Graph

When we start moving from one node and after a few moves end up back at the starting node, this means that there's a cycle in the graph.

If there is a cycle in a graph and the edges are undirected then the graph is called Undirected Cyclic Graph.
Similarly if the graph has a cycle but the edges are directed then it's called a Directed Cyclic Graph.

Degree of a Graph

In case of undirected graphs the number of edges connected to a node is it's degree.
But in Directed graphs:
In-degree: Total number of incoming edges in a node.
Out-degree: Total number of outgoing edges in a node.

Total degree of a graph = 2 x the number of edges in the graph

Weights in a Graph

Weights are used to measure the cost of a traversal in a graph usually represented by edges hence known as weighted edges.
Why do we need them? Well consider this, you have to travel from city A to city B but there are multiple paths that you can use. To make the decision easier we can just calculate the time it'll take for us to reach our destination for each path and then pick the one with lowest time.

That's about the introduction to graphs but there are a lot of interesting and important topics associated with graphs like representing a graph in a language, traversal algorithms, shortest path algorithms, cycle detection algorithms, topological sort, etc.

I hope this article was helpful for you.
Thanks for reading.

How To Increase The Size Of An Array In C ?

Gaurav — Wed, 11 Aug 2021 08:53:11 +0000

To understand this better let's see how you would resize an array in JavaScript with a simple example.



let someArray = [1,2,3,4,5];
console.log(someArray);
someArray.length +=5;
console.log(someArray.length);
console.log(someArray);

Which when executed gives this output:

This was a straight forward and easy example of how you would do that in JavaScript but this is not the case with some other languages like C.

So how would you do that in C?
I'm glad you asked. But first we need to understand what the problem is or why isn't it this simple in C.

In C we need to understand that memory for an array is allocated at compile time and not at runtime which means we cannot increase it once the array size is declared in the code.
We know to create an array we need a contiguous memory allocation or in simpler terms the next element in an array must be placed adjacent or after the previous one. After specifying the size of an array we can't determine if the memory location adjacent to the last element in an array is empty or not and hence we can't increase the size of the array.I hope that made sense. Now you might be thinking why were we able to do this in JavaScript, then the simple answer is JavaScript arrays are just objects with special properties. JavaScript is a wired language and I love it.

Steps to get the job done:
1.Create an array (lets say p) with n items.
2.Create another array (lets say q) but an empty one which is larger than array p.
3.Now copy the elements of p into q by a simple for loop.
4.Delete the memory held by pointer p using free(p); so that array p no longer exists.
5.Assign the address of array q in p.
6.Assign q the value NULL so that it can't access array q.
7.And that's it. The array size is now increased.

Please read the code for better understanding.
Code



#include<stdio.h>
#include<stdlib.h>
int main(){
//Two pointers for two different arrays
    int *p;
    int *q;

//declaring array at pointer p
    p = (int *)malloc(5*sizeof(int));
    p[0]=1;
    p[1]=3;
    p[2]=5;
    p[3]=7;
    p[4]=9;
//Printing the elements of p
    printf("Array p: \n");
    for(int i=0;i<5;i++){
        printf("%d \n",p[i]);
    }
//declaring array at pointer q
    q=(int *)malloc(7*sizeof(int));
    for(int i=0;i<5;i++){
        q[i]=p[i];//assigning elements of p to q
    }

    free(p);//releasing the memory held by pointer p

    p=q; //assigning the address held by q to p for the array
    q=NULL; //removing the address of array from q

//printing the elements of p
    printf("Array q converted to p: \n");
    for(int i=0;i<7;i++){
        printf("%d \n",p[i]);
    }

    return 0;
}

Output

So we can clearly see that the array p in the beginning was of size 5 but after all that code its increased to 7.
The 0 at the end of the array after size increase is added by C automatically if no data is entered at that index.

Let's understand with this example.
Let a guy named P has a car (array 1). But now he has kids due to which he needs a bigger car. He has a friend named Q who is moving to a different country and wants to sell his car (array 2). P realizes that his friend's car will be just the perfect size for him so he makes his friend Q an offer and buys his car (array2) and Q leaves the country q=NULL;. Now P has 2 cars and since he doesn't need his old car (array 1) he gets rid of it free(p);.

I hope this was clear and easy to understand. Thanks for your time.

The This Keyword in JavaScript

Gaurav — Mon, 09 Aug 2021 06:57:05 +0000

To understand this keyword let’s take an example of the word “this” in the English language with the help of the following images.

From the above two images what I’m trying to explain is that the This keyword refers to the object it belongs to. Its value depends on where it is used.

This keyword will take the value of the owner of the function and point to the owner of the function. The value of this keyword is not static, it depends on the way the function is called.

If we'll do a simple console.log(this) in the browser, the output will be the global object(window object) which shows that the this keyword will point to the object that called the function.

A function can be called commonly in 4 ways(there are other ways):

As a method: In the following code example, the this keyword points to the detail object because it’s the detail object that is called the function and hence is the owner object.

'use strict'
const detail = {
  name: "samurai",
  year: "2020",
  calcAge: function () {
    return 2077 - this.year;
  },
};
detail.calcAge();//57

As a simple function call in strict mode.

'use strict'
function sum() {
  let add = 2 + 2;
  console.log("sum of two numbers is" + add);
  console.log(this);
}
sum();

For a normal function, this keyword will point to the window object but if strict mode is used then it will be undefined.

Arrow functions: They don't get their own this keyword. Instead, the surrounding or parent function is the one that gets pointed by the this keyword due to lexical scope.
As an event listener: In this case, the this keyword points to
the handler function attached to the event.

An important point we have to remember that this keyword will not point to the function we are using it in but to the object which called the function.

Summary
1.This refers to the owner object or the object that called the function.
2.The value of this keyword depends on where it is used.
3.If 'use strict' is in the code then this will point to undefined else to the window object for a simple function call.

Framework VS Library

Gaurav — Sun, 08 Aug 2021 06:52:39 +0000

Let us start with the similarity between the two that is they both are reusable code written to solve a common problem and make sure the code is DRY. Assume some developer who encountered a particular problem with the program and realized that it is a very common issue and requires a lot of time and effort to resolve, so he created a library or a framework to solve the issue once and for all.

Now to the main difference between the two can be explained with the term Inversion of Control (IoC) which simply means who controls who during the development process or in simpler words it defines the relationship between the library, framework, and code.

Code Controls Library

A piece of code that you require multiple times, but you must use the library to keep your code DRY. Most programming languages support libraries like React in the case of JavaScript. With a library, you can choose where to use it in your code and adjust it according to your code.

Compare this library to an actual library where you can go and pick up any book that you want and read it. In the same way, you can choose any library that suits your need and use it in your code by calling specific functions.

Framework Controls Code

A framework defines the architecture for your program and uses the code when needed. It is a collection of libraries that work together. Angular is an example of a JavaScript framework.
A framework provides most tools required to build an application and tells you where to put your code.

We can understand it by thinking of a blueprint for a building as a framework. The blueprint is how the building is planned to be constructed and the people who are going to live in it have to adjust according to it.

Basically, it controls your code which means it is in charge.

To sum it up

There may be other small differences between the two but the main difference we need to know is the inversion of control i.e. who controls who.

Code controls library
Framework controls code