Video courses for company/skill based Preparation
Purchase mock tests for company/skill building
What is a Graph?
What is a Graph?
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
- 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.
- Facebook : here user accounts are considered as vertices and if two users are friends then there will be an edge between them.
- 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.
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