Introduction To Graph Data Structure

Introduction To Graph Data Structure

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.

Graph Terminologies

fig01 terminology.png

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.

Edge

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.

Adjacent

fig02 adjacent.png

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.

NodesAdjacents
ABDC
BADE
CAD
DCABE
EBD

Degree

fig03 degree.png

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

fig04 typesofgraph.png

Disconnected 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.

Connected graph

A graph is connected if all nodes have at least one edge.

Undirected graph

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.

Directed graph

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.

Complete graph

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.

Cyclic graph

A graph can have cycles which means if you traverse through the node, you could get the same node more than once.

Acyclic graph

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.

Don't forget to share and bookmark :) Buy me coffee

Did you find this article valuable?

Support saud chougle by becoming a sponsor. Any amount is appreciated!