Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

What is a Graph?

What is a Graph?

 
Graph is one of the most important user defined data structure now-a-days in computer science with whole lot of real life implementations. Unlike array, stack, queue and linked list graph is a non linear data structure (In linear Data structure data is arranged in linear or sequential manner).
 
What is a Graph | PrepInsta

Components of Graph 

It has two major components:-

  •  Nodes:- these are vertices of the graph.
  •  Edges:- these are lines that joins 2 nodes.

Real life implementation of Graph data structure

  1.  Google maps :  graphs are used to built transport mechanism. Where location can be considered as vertex and path that connects two locations are considered as edges.
  2.  Facebook :  here user accounts are considered as vertices and if two users are friends then there will be an edge between them.
  3.  World wide web :  here webpages are considered as nodes and if a page links to another page then there will be an edge between them.

Graph algorithms are are also used in many more various real life scenarios.

Why students should learn graph data structure

  • Graph concepts can be very useful for doing a project. It plays an important role in design, analysis and testing of computer programs, hence specially for developmental works and CSE students.
  • Also graphs are very useful for other branches as well.
  • In Electrical engineering graphs can be used to solve complex electrical circuits where closed loop can be formed by source, wires, load and switches.
  • In architectural point of view graph can show you the shortest path between two places.
  • In short graphs are very useful for many branches of engineering.

Below are some fundamentals regarding graph theory

Weighted graph and unweighted graph

If edges in the graph have values or weight then the graph can be said to be weighted graph, otherwise it will be considered as unweighted graph.

In the image, a, b, c, d, e, f are the respective weights of te edges in the weighted graph.

Directed graph and Undirected graph

 if a graph has edges that contains direction from one node to another node then it is called directed graph. If the edges of a graph do not contain any direction, it is called undirected graph. Actually in undirected graph edges represents a two way relationship between two nodes.

Connected graph and disconnected graph

If any two nodes of a graph are connected by a path then the graph is called connected graph. If there are atleast 2 nodes present in a graph such that there are no path existing between them, the graph is called disconnected graph.

Bipartite graph

If the nodes of a graph can be divided into two disjoint and independent sets such that every edge in the graph connects one node from a set to another node from another set then the graph is called Bipartite graph.

Cycles in graph

if there is a path present in the graph that starts from a node and ends up reaching the same node then that is called a cycle.

  • If an edge is starting from a node and ending in that very node, like a loop , it is also a cycle.

In the picture you will understand it more clearly. 

 

Representation of Graph 

  • Adjacency matrix

For this kind of representation, a square matrix is used to represent a finite graph. Here the elements of the matrix indicate weather a pair of vertices are connected or not. We can also store the weight of each edges in the graph.

For more : Graph Representation by Adjacency Matrix

  • Adjacency list

in this kind of representation and array of unordered list is used to show a graph. Each list describes the set of neighbours of a node in the graph.

For more : Graph Representation by Adjacency List

Article is contributed by Rahit Saha

Comments