What is a Graph?

Related Banners
prepinsta
prepinsta
Prepinsta Prime
Get Prepinsta Prime

Get all 200+ courses offered by Prepinsta

Explore Prime or check Course List
Check out our instagram

Never Miss an OffCampus Update

Get OffCampus Updates on Social Media from PrepInsta

Follow us on our Media Handles, we post out OffCampus drives on our Instagram, Telegram, Discord, Whatsdapp etc.

Instagram Whatsapp Telegram Linkedin
Get Hiring Updates
Amazon,Google,Delottie & 30+companies are hiring ! Get hiring Updates right in your inbox from PrepInsta
prepinsta
prepinsta
prepinsta
prepinsta

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others.
Get Prime Course List

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others.
Get Prime Course List

Get PrepInsta Prime Subscription

Get access to all the courses that PrepInsta offers, check the out below -

Companies

TCS, Cognizant, Delloite, Infosys, Wipro, CoCubes, KPMG, Amazone, ZS Associates, Accenture, Congnizant & other 50+ companies

See Full list here
Get Prime

Programming

Data Structures, Top 500 Codes, C, C++, Java Python & other 10+ subjects

See Full list here
Get Prime

Skills

Full Stack Web Development, Data Science, Machine Learning, AWS Cloud, & other 10+ skills and 20+ projects

See Full list here
Get Prime

OffCampus Updates

Never Miss OffCampus Updates

Get OffCampus Update from PrepInsta

Follow us on our Social Media Handles

Instagram
Telegram
Whatsapp
LinkedIn

Related Pages

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

June 27, 2023

Comments