What is a Graph data structure?
A Graph is a collection of nodes and edges in a way that nodes are connected by an edge.
Vertex or Node
Every individual point that holds or represents some kind of data is called vertex or node.
In fig01 points "A", "B", "C", "D", "E" are vertex/node. node and vertex both are the same terms.
A connection between two nodes is called an edge. In fig01 the connection between node B and node E is edge similarly A-B, A-C, A-C, A-D, B-D, C-D, D-E are edges.
A node that shares a common edge with other nodes is called "Adjacent" node.
Adjacents nodes of "A" mean all the nodes that share common edges with node "A".
so, Adjacent nodes of node "A" are "B", "D", "C".
Adjacent of all nodes respectively.
The degree is the number of edges connected to a node.
for example, in fig03 the node "D" has a degree of 4 while the "E" has a degree of 2.
Types of graph
In a disconnected graph, not all nodes have edges. nodes might be isolated.
If you see the above disconnected graph, there are three isolated regions. these three regions don't have a connection between them.
A graph is connected if all nodes have at least one edge.
An undirected graph has no direction. The edges indicate a two-way relationship, edges can be traversed in both directions.
A good example would be a Facebook friend, When you accept a friend request a connection between you and your friend is undirected.
A directed graph has edges with direction. The edges indicate a one-way relationship, in that each edge can only be traversed in a single direction.
A good example would be Twitter, Instagram where either your friend follows you or you follow your friend or you both follow each other.
A graph is said to be complete if each node have a degree of n-1(n = total nodes)
sound like mathematics, in simple words
A graph is complete if each node has an edge with all other nodes except itself.
A graph can have cycles which means if you traverse through the node, you could get the same node more than once.
A graph is acyclic that means the graph must have at least one node with no targets (called a leaf).
in fig04 acyclic graph, the orange node doesn't have any outgoing edge.
Applications Of Graph
- Social media like Facebook, Linked In, Twitter, Instagram uses graphs that store users, groups, check-ins, likes, and more as nodes. -Google Maps, Apple Maps, Waze use graphs to treat all cities and places as nodes and routes between them as edges.
- Webgraph describes a directed graph between pages of the WWW. Each page is a vertex and the hyperlinks are edges. This is the basic idea behind the Google Page Ranking Algorithm.
- Uber, Ola, Lyft uses a graph to find the shortest and cheapest path for a car from one city to another.
- The graph is also used in a database for representing Entity-Relationship.
- Graph theory is also used to study molecules in chemistry and physics.
Did you find this article valuable?
Support saud chougle by becoming a sponsor. Any amount is appreciated!