Skip to main content

Graph Data Structure

Graph

Graph data structure

A graph can be defined as a group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent child relationship.

A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following figure.

Directed and undirected graph

A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph does not have any edges in directions. If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B.

In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex A to another vertex B. Node A is called the initial node while node B is called the terminal node.

Graph terminology

  1. Path
  2. Closed Path
  3. Cycle
  4. Connected Graph
  5. Weighted Graph
  6. Digraph
  7. Adjacent Node
  8. Degree of the node
  9. Graph Represention

Path

A path can be defined as the sequence of nodes that are followed in order to reach some terminal node V from the initial node U.

Closed Path

A path will be called a closed path if the initial node is the same as the terminal node. A path will be a closed path if V0=VN.

Simple Path If all the nodes of the graph are distinct with an exception V0=VN, then such path P is called as closed simple path.

Cycle

A cycle can be defined as the path which has no repeated edges or vertices except the first and last vertices.

Connected Graph

A connected graph is the one in which some path exists between every two vertices (u, v) in V. There are no isolated nodes in the connected graph.

Complete Graph

A complete graph is the one in which every node is connected with all other nodes. A complete graph contains n(n-1)/2 edges where n is the number of nodes in the graph.

Weighted Graph

In a weighted graph, each edge is assigned with some data such as length or weight. The weight of an edge e can be given as w(e) which must be a positive (+) value indicating the cost of traversing the edge.

Digraph

A digraph is a directed graph in which each edge of the graph is associated with some direction and the traversing can be done only in the specified direction.

Adjacent Nodes

If two nodes u and v are connected via an edge e, then the nodes u and v are called neighbours or adjacent nodes.

Degree of the Node

A degree of a node is the number of edges that are connected with that node. A node with degree 0 is called an isolated node.

Graph Representation

By Graph representation, we simply mean the technique which is to be used in order to store some graphs into the computer's memory.

There are two ways to store Graph into the computer's memory. In this part of this tutorial, we discuss each one of them in detail.

1. Sequential Representation

In sequential representation We use an adjacency matrix to store the mapping represented by vertices and edges. In the adjacency matrix, the rows and columns are represented by the graph vertices. A graph having n vertices, will have a dimension n x n.

Representation of weighted directed graph

Representation of weighted directed graphs is different. Instead of filling the entry by 1, the Non- zero entries of the adjacency matrix are represented by the weight of respective edges.

Directed graph

In a directed graph, the sum of lengths of all the adjacency lists is equal to the number of edges present in the graph. In the case of weighted directed graphs, each node contains an extra field that is called the weight of the node. The adjacency list representation of a directed graph is shown in the following figure.

Adjacency matrix

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight.

Adjacency multi list

It is represented by M Vertex-1 Vertex-2 List-1 List-2 Where M = Visited Vertex -1 = start vertex of edge (m,n) = m Vertex-2 = start vertex of edge (m,n) = n List -1 = List where vertex 1 is present List -2= List where vertex 2 is present

Graph traversal

Traversing the graph means examining all the nodes and vertices of the graph. There are two standard methods by which we can traverse the graphs. Let's discuss each one of them in detail.

  • Breadth First Search
  • Depth First Search

Breadth first search

Breadth first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes.

The algorithm follows the same process for each of the nearest nodes until it finds the goal. The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all of its neighbours.

In the next step, the neighbours of the nearest node of A are explored and the process continues in the further steps. The algorithm explores all neighbours of all the nodes and ensures that each node is visited exactly once and no node is visited twice.

Breadth first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes.

The algorithm follows the same process for each of the nearest nodes until it finds the goal. The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all of its neighbours.

In the next step, the neighbours of the nearest node of A are explored and the process continues in the further steps. The algorithm explores all neighbours of all the nodes and ensures that each node is visited exactly once and no node is visited twice.

Depth First Search algorithm

is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.

Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backwards on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The DFS algorithm works as follows:

  • Start by putting any one of the graph's vertices on top of a stack.
  • Take the top item of the stack and add it to the visited list.
  • Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
  • Keep repeating steps 2 and 3 until the stack is empty.
Labels:

Comments

Post a Comment

Please give us feedback through comments

Trending⚡

Happy birthday Hardik Pandya | In C programming

  Happy birthday Hardik Pandya . Now you are  28 years old. Great achievement you have. Let's we want to talk more about Hardik pandya. He is great cricketer. Pandya is awesome. In this Blog Post we are going to wish pandya " Happy birthday using C program". Let's tune with us till end. Now we have to wish pandya, so we are going to use printf () function printing message to pandya as " Happy birthday Hardik pandya Now you are 28 years old". Hardik pandya was born on 11 October in 1993. Now we are going to declare a variable called as current_age = 2021 - 1993. It calculate current age Of Hardik pandya. See the "Happy birthday pandya" using c programming. If you liked this Blog Post then don't forget to share with your computer science learning friends. Once again " Happy birthday Hardik Pandya sir". Read also Happy Rakshabandhan wish using C program Friendship day 2021 greetings in C
Post a Comment
Read more

Understanding link.click() in JavaScript

Hey! Today i am going to share with you how to use link.click() function in javascript As a JavaScript developer, you may come across the need to programmatically click a link on a web page. The link.click() method is a commonly used way to do this, and it is important to understand how it works and when to use it. What is link.click()? link.click() is a method that can be used to simulate a click on a link element in JavaScript. It is typically used when you want to trigger a link click event programmatically, rather than requiring the user to physically click the link. How to use link.click() Using link.click() is relatively straightforward. First, you need to select the link element you want to click using a DOM selector such as getElementById() or querySelector(). Then, you can call the click() method on the link element to simulate a click. Here is an example: // select the link element const myLink = document.getElementById('my-link'); // simulate a cl...
Post a Comment
Read more

Best course Recommendation of IT field in 2023

Recommend me best course 🎉50% Discount on registration today itself 🎉! Join Course Now In today's fast-paced digital age, staying updated with the latest technology trends is crucial for professionals looking to advance in their careers. With technology rapidly evolving, it is important to continuously upskill and gain new knowledge to stay relevant in the job market. In 2023, there are several courses in technology that are gaining popularity and are highly recommended for professionals seeking to enhance their skills in data science, analytics, and digital marketing. Data Science: Data science is an interdisciplinary field that combines statistical analysis, machine learning, and computer science to extract insights and knowledge from data. With the increasing amount of data available, data scientists are in high demand across various industries. The best courses in data science for 2023 are th...
Post a Comment
Read more

Define a macro EQUALSTR which accepts two strings and compare equality of both string

Define a macro EQUALSTR which accepts two strings and compare equality of both string #include<stdio.h>  #include<string.h>  #define EQUALSTR(str1,str2) strcmp(str1,str2)?0:1  void main()  {  char str1[10],str2[10];  printf("\n Enter the two strings: ");  gets(str1);  gets(str2);  if(EQUALSTR(str1,str2))  printf("\n Strings are equal");  else  printf("\n Strings are not equal");  } Also Read C program to find largest of two numbers using Structure Predefined Macro program Macros vs Functions Preprocessor Syntax Task Performed by Preprocessor
Post a Comment
Read more

check number is prime or odd or even using c program

Here is the c program to check if the user entered number is prime ,even and odd. These few lines of code solve three problems. In the above program we used integer type num variable for storing user entered numbers. Then we used the IF condition statement. That's all. IF condition for even number In the First IF statement we have a logic. If the number is divided by two then the reminder should be 0 then the number is an even number else not an even number. That simple logic is implemented in the first if statement. IF condition for odd number In the second IF statement we Implemented odd number logic. We identify odd numbers just by making little change in even number logic. If the number is divided by two then the reminder should not be a zero. Then the number is odd. That's simple logic used to identify whether a number is odd or not an odd number. IF condition for prime number In the third IF condition we implemented the logic of the prime number. In this IF ...
Post a Comment
Read more

How to write programs in Bhai language

Bhai Language Bhai language is fun Programming language , with this language you can makes jokes in hindi. Bhai language written in typescript. It's very funny , easy and amazing language. Keywords of this language written in Hindi . Starting and ending of the program Start program with keyword " hi bhai " and end with " bye bhai ". It's compulsory to add this keyword before starting and end on the program. You write your programming logic inside this hi bhai and bye bhai . How to declare variables in Bhai language We use " bhai ye hai variable_name" keyword for declaring variables. In javascript we use var keyword for declaring variables but here you have to use " bhai ye hai " keyword. If you are declaring string then use " " double quotes. You can use Boolean variable like sahi and galat for true and false . How to print output in Bhai language You have to use " bol bhai " keyword for ...
Post a Comment
Read more