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

What is programming explained in simple words

Hi my dear friends today in this blog post we are going to know what programming is? In simple words I will explain to you programming. Nowadays we are watching real life use of programming. How computers learn to speak, talk and do the specified complex task for us. We are all keen to know what is exactly programming? Programming is the process of creating instructions that a computer can understand and execute. These instructions, also known as code, are written in a programming language that is specific to the task at hand. The history of programming can be traced back to the mid-20th century, with the development of the first electronic computers. The first programming languages were known as machine languages, which were specific to a particular type of computer. As computers became more sophisticated, high-level programming languages were developed, such as FORTRAN and COBOL, which were easier for humans to read and write. These languages allow programmers to write code t
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