Introduction to Graphs

A graph is a non-linear data structure that consists of a collection of nodes (or vertices) and a set of links (or arcs) that connect the vertices. The following is how a graph is defined...

Graph is a collection of vertices and arcs which connects vertices in the graph

Graph is a collection of nodes and edges which connects nodes in the graph

Generally, a graph G is represented as G = ( V , E ), where V is set of vertices and E is set of edges.

Example

The following is a graph with 5 vertices and 6 edges.
This graph G can be defined as G = ( V , E )
Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

We use the following terms in graph data          

structure...

Vertex

• A individual data element of a graph is called as Vertex. Vertex is also known as node. In above example graph, A, B, C, D & E are known as vertices.

Edge

• An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as (startingVertex, endingVertex). For example, in above graph, the link between vertices A and B is represented as (A,B). 
• In above example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D), (B,E), (C,D), (D,E)).

Edges are three types.

1. Undirected Edge - An undirected edge is a bidirectional edge. If there is a undirected edge between vertices A and B then edge (A , B) is equal to edge (B , A).
2. Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A and B then edge (A , B) is not equal to edge (B , A).
3. Weighted Edge - A weighted edge is an edge with cost on it.

Undirected Graph

• A graph with only undirected edges is said to be undirected graph.

Directed Graph

• A graph with only directed edges is said to be directed graph.

Mixed Graph

• A graph with undirected and directed edges is said to be mixed graph.

End vertices or Endpoints

• The two vertices joined by an edge are called the end vertices (or endpoints) of the edge.

Origin

• If an edge is directed, its first endpoint is said to be origin of it.

Destination

• If an edge is directed, its first endpoint is said to be origin of it and the other endpoint is said to be the destination of the edge.

Adjacent

• If there is an edge between vertices A and B then both A and B are said to be adjacent. In other words, Two vertices A and B are said to be adjacent if there is an edge whose end vertices are A and B.

Incident

• An edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge.

Outgoing Edge

• A directed edge is said to be outgoing edge on its origin vertex.

Incoming Edge

• A directed edge is said to be incoming edge on its destination vertex.

Degree

• Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree

• Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree

• Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

• If there are two undirected edges to have the same end vertices, and for two directed edges to have the same origin and the same destination. Such edges are called parallel edges or multiple edges.

Self-loop

• An edge (undirected or directed) is a self-loop if its two endpoints coincide.

Simple Graph

• A graph is said to be simple if there are no parallel and self-loop edges.

Path

• A path is a sequence of alternating vertices and edges that starts at a vertex and ends at a vertex such that each edge is incident to its predecessor and successor vertex.

Height, Depth and Level of a Tree

Edge

Edge – Connection between one node to another.

Path

Path – a sequence of nodes and edges connecting a node with a descendant.

A path starts from a node and ends at another node or a leaf.

Height

Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.

When looking at height:

• Every node has height. So B can have height, so does A, C and D.
• Leaf cannot have height as there will be no path starting from a leaf.
• It is the longest path from the node to a leaf. So A's height is the number of edges of the path to E, NOT to G. And its height is 3.
• The height of the root is 1.

Height of tree –The height of a tree is the number of edges on the longest downward path between the root and a leaf.

Depth

Depth –The depth of a node is the number of edges from the node to the tree's root node.

We don't care about path any more when depth pops in. We just count how many edges between the targeting node and the root, ignoring directions. For example, D's depth is 2.

Recall that when talking about height, we actually imply a baseline located at bottom. For depth, the baseline is at top which is root level. That's why we call it depth.

Note that the depth of the root is 0.

Level

Level – The level of a node is defined by 1 + the number of connections between the node and the root.

Simply, level is depth plus 1.

The important thing to remember is when talking about level, it starts from 1 and the level of the root is 1. We need to be careful about this when solving problems related to level.

Graph

• A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. 
• The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
• Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices. Take a look at the following graph −

In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Graph Data Structure

• Data structures can be used to define mathematical graphs. An array of vertices and a two-dimensional array of edges can be used to represent a graph. Before we go any further, let's make sure we're all on the same page with certain key terminology.
• Vertex − A vertex is a representation of each node in the graph. The labeled circle in the following example represents vertices. As a result, A to G are vertices. As seen in the above image, we can represent them using an array. Index 0 identifies A in this case. Index 1 can be used to identify B, and so forth.
• Edge − A path or a line connecting two vertices is represented by an edge. The lines from A to B, B to C, and so on indicate edges in the following example. As seen in the following graphic, a two-dimensional array can be used to depict an array. AB can be represented as 1 in row 0, column 1, BC in row 1, column 2, and so on, with the rest of the combinations remaining as 0.
• Adjacency − If two nodes or vertices are connected to each other by an edge, they are said to be neighboring. B is adjacent to A in the following example, C is adjacent to B, and so on.
  Path -  Path is a set of edges that connects the two vertices. ABCD depicts a path from A to D in the example below.
• 
  
  

• Basic Operations

• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.
• 1. DFS (Depth First Search)
  2. BFS (Breadth First Search)

Introduction to Basic Data Structures and Algorithms

Introduction to Basic Data Structures and Algorithms

Basic types of Data Structures.

• As previously stated, anything that can store data is referred to as a data structure, hence Integer, Float, Boolean, Char, and so on are all data structures. Primitive Data Structures are what they're called.
• Then there are complicated Data Structures, which are used to store enormous amounts of data that are linked together. The following are some examples of Abstract Data Structure:

Basic types of Data Structures.

1. Linked List
2. Tree
3. Graph
4. Stack, Queue etc.

All of these data structures enable us to execute various data operations. We choose these data structures based on the sort of operation that will be performed. In subsequent courses, we will delve further into these data structures.

Characteristic	Description
Linear	In Linear data structures, the data items are arranged in a linear sequence. Example: Array
Non-Linear	In Non-Linear data structures, the data items are not in sequence. Example: Tree, Graph
Homogeneous	In homogeneous data structures, all the elements are of same type. Example: Array
Non-Homogeneous	In Non-Homogeneous data structure, the elements may or may not be of the same type. Example: Structures
Static	Static data structures are those whose sizes and structures associated memory locations are fixed, at compile time. Example: Array
Dynamic	Dynamic structures are those which expands or shrinks depending upon the program need and its execution. Also, their associated memory locations changes. Example: Linked List created using pointers

What is the definition of an algorithm?

• An algorithm is a finite set of instructions or logic that must be written in a specific order to complete a set goals. An algorithm is not a complete programme or code; rather, it is the basic logic (solution) of a problem, which can be stated in a flowchart or as a high-level description in pseudocode.

The following properties must be met by every algorithm:

1. Input- There should be 0 or more inputs given externally to the algorithm.
2. Output- There should be at least 1 output as a result.
3. Definiteness- Every step of the algorithm should be clear and well defined.
4. Finiteness- The algorithm should have finite number of steps.
5. Correctness- Every step of the algorithm must generate a correct output.

If an algorithm takes less time to perform and requires less memory space, it is said to be efficient and fast. The following properties are used to evaluate an algorithm's performance:

1. Time Complexity.
2. Space Complexity.

Time Complexity.

• The term "time complexity" refers to the amount of time it takes for a programme to operate from start to finish. 
• It's generally a good idea to attempt to minimize the time required to a bare minimum, so that our algorithm runs as quickly as feasible. In the next parts, we will go through Time Complexity in further depth.

NOTE: 

• Before diving into data structures, you should have a solid understanding of programming, whether in C or C++, Java, Python, or another language.

Space Complexity.

• It is the amount of memory space used by the algorithm while it is being executed. For multi-user systems and circumstances with limited memory, space complexity must be regarded seriously.

The following components of an algorithm typically demand space:

Instruction Space: 

• This is the amount of space necessary to store the program's executable version. This space is constant, but it varies depending on how many lines of code are in the application.

Data Space: 

• This is the amount of space needed to hold the values of all the constants and variables (including temporary variables).

Environment Space: 

• This is the amount of space needed to store the environmental data required to resume the suspended function.

The Characteristics of Good Algorithms

• Input and output must be well specified.
• Each stage of the algorithm should be simple and straightforward.
• Among the numerous various approaches to address an issue, algorithms should be the most effective.
• Computer code should not be included in an algorithm. Rather, the algorithm should be designed in a way that allows it to be utilized in a variety of programming languages.

Algorithm 1: Add two numbers entered by the user

Step 1: Start

Step 2: Declare variables num1, num2 and sum. 

Step 3: Read values num1 and num2. 

Step 4: Add num1 and num2 and assign the result to sum.

        sum←num1+num2 

Step 5: Display sum 

Step 6: Stop

Algorithm 2: Find the largest number among three numbers

Step 1: Start

Step 2: Declare variables a,b and c.

Step 3: Read variables a,b and c.

Step 4: If a > b

           If a > c

              Display a is the largest number.

           Else

              Display c is the largest number.

        Else

           If b > c

              Display b is the largest number.

           Else

              Display c is the greatest number.  

Step 5: Stop

Algorithm 3: Find Root of the quadratic equation ax2 + bx + c = 0

Step 1: Start

Step 2: Declare variables a, b, c, D, x1, x2, rp and ip;

Step 3: Calculate discriminant

         D ← b2-4ac

Step 4: If D ≥ 0

              r1 ← (-b+√D)/2a

              r2 ← (-b-√D)/2a 

              Display r1 and r2 as roots.

        Else     

              Calculate real part and imaginary part

              rp ← -b/2a

              ip ← √(-D)/2a

              Display rp+j(ip) and rp-j(ip) as roots

Step 5: Stop      

       

Algorithm 4: Find the factorial of a number

Step 1: Start

Step 2: Declare variables n, factorial and i.

Step 3: Initialize variables

          factorial ← 1

          i ← 1

Step 4: Read value of n

Step 5: Repeat the steps until i = n

     5.1: factorial ← factorial*i

     5.2: i ← i+1

Step 6: Display factorial

Step 7: Stop

Algorithm 5: Check whether a number is prime or not

Step 1: Start

Step 2: Declare variables n, i, flag.

Step 3: Initialize variables

        flag ← 1

        i ← 2  

Step 4: Read n from the user.

Step 5: Repeat the steps until i=(n/2)

     5.1 If remainder of n÷i equals 0

            flag ← 0

            Go to step 6

     5.2 i ← i+1

Step 6: If flag = 0

           Display n is not prime

        else

           Display n is prime

Step 7: Stop 

Algorithm 6: Find the Fibonacci series till the term less than 1000

Step 1: Start 

Step 2: Declare variables first_term,second_term and temp. 

Step 3: Initialize variables first_term ← 0 second_term ← 1 

Step 4: Display first_term and second_term 

Step 5: Repeat the steps until second_term ≤ 1000 

     5.1: temp ← second_term 

     5.2: second_term ← second_term + first_term 

     5.3: first_term ← temp 

     5.4: Display second_term 

Step 6: Stop

Few more detail about Data Structure

Time Complexity of an Algorithms

BFS (Breadth First Search)

When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and uses a queue to remember to retrieve the next vertex to start a search.

Initialize the queue.

We start from visiting S (starting node), and mark it as visited.

We then see an unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.

Next, the unvisited adjacent node from S is B. We mark it as visited and enqueue it.

Next, the unvisited adjacent node from S is C. We mark it as visited and enqueue it.

Now, S is left with no unvisited adjacent nodes. So, we dequeue and find A.

From A we have D as unvisited adjacent node. We mark it as visited and enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program is over.

DFS (Depth First Search)

Depth First Traversal

When a dead end occurs in any iteration, the Depth First Search (DFS) method traverses a network in a deathwards motion and uses a stack to remember to obtain the next vertex to start a search.

As in the example given above, DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G. It employs the following rules.

1. Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
2. If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
3. Repeat Rule 1 and Rule 2 until the stack is empty.

• 
  
  
• Initialize the stack.
• 
  
  
• Mark S as visited and put it onto the stack. Explore any unvisited adjacent node from S. We have three nodes and we can pick any of them. For this example, we shall take the node in an alphabetical order.
• 
  
  
• Mark A as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both S and D are adjacent to A but we are concerned for unvisited nodes only.
• 
• Visit D and mark it as visited and put onto the stack. Here, we have B and C nodes, which are adjacent to D and both are unvisited. However, we shall again choose in an alphabetical order.
• 
  We choose B, mark it as visited and put onto the stack. Here B does not have any unvisited adjacent node. So, we pop B from the stack.
  
  
• 
  
  
• We check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find D to be on the top of the stack.
• 
  
  
• Only unvisited adjacent node is from D is C now. So we visit C, mark it as visited and put it onto the stack.
• As C does not have any unvisited adjacent node so we keep popping the stack until we find a node that has an unvisited adjacent node. In this case, there's none and we keep popping until the stack is empty.

Searching Algorithms for Array.

Searching Algorithms for Array in Data Structure

• An algorithm is a step-by-step approach or method for a computer to solve a problem in a specific number of steps. 
• Depending on the problem for which the algorithm is being designed, the steps of an algorithm may entail repetition. 
• The algorithm is written in a way that is easy to read and understand. 
• There are two methods for finding an element in an array: linear search and binary search.

---

Linear Search

• The simplest and most basic search algorithm is a linear search. 
• A linear search examines an array for an element or value until the requested element or value is not found, and it does so in order. 
• It compares the element to all of the other items in the list and returns the value index if the element is matched, otherwise it returns -1. 
• When there are fewer elements in a list, Linear Search is used on the unsorted or unordered list.

---

Example with Implementation

• To search element 5 it will go step by step in sequence order.

function findIndex(values, target)
 {
   for(var i = 0; i < values.length; ++i)
     {
       if (values[i] == target) 
         {       
           return i; 
         }
     }
   return -1;
 }
//call the function findIndex with array and number to be searched
findIndex([ 8 , 2 , 6 , 3 , 5 ] , 5) ;

---

Binary Search

• On a sorted array or list, Binary Search is used. In binary search, we compare the value to the elements in the array's middle place. 
• We return the value if the value is matched. If the value is less than or equal to the center element, it must be in the bottom half of the array; if it is more than or equal to the element, it must be in the upper half. 
• On the bottom (or upper) half of the array, we repeat the procedure. 
• When an array contains a huge number of elements, Binary Search comes in handy.

---

Example with Implementation

• To search an element 13 from the sorted array or list.

function findIndex(values, target) 
{
  return binarySearch(values, target, 0, values.length - 1);
};

function binarySearch(values, target, start, end) {
  if (start > end) { return -1; } //does not exist

  var middle = Math.floor((start + end) / 2);
  var value = values[middle];

  if (value > target) { return binarySearch(values, target, start, middle-1); }
  if (value < target) { return binarySearch(values, target, middle+1, end); }
  return middle; //found!
}

findIndex([2, 4, 7, 9, 13, 15], 13);

• We compare the middle number of the list to the target in the previous programme logic, and if they match, we return. If it doesn't, we check to see if the middle value is larger or smaller than the target.
• If the Middle number is bigger than the Target, the binary search is restarted, but this time on the left half of the list, from the beginning to the middle, not beyond.
• If the Middle number is less than the Target, we repeat the binary search, but this time on the right half of the list, from the middle to the finish.