Graph Data Structure and Algorithms (Example)

What is a Graph in Data Structure?

A graph is a non-linear data structure that consists of vertices and edges, where vertices contain the information or data, and the edges work as a link between pair of vertices.

It is used to solve real word problems like finding the best route to the destination location and the route for telecommunications and social networks. Users are considered a node in the Graph, and the wires are the edges connecting the users.

If edges are represented as E and vertices are represented as V, then the graph G can be written as the set of vertices and edges, such as G (V, E)

Example of Graph in Data Structure

Here’s a simple example of graph data structure:

Example of Graph in Data Structure

It’s a simple undirected graph (one kind of Graph). Here the set of vertex is: {A, B, C,D,E,F}. Two vertices create an edge. For example, A and B are linked with an edge. However, A and F are not linked with any edges.

Graph Terminologies in Data Structure

The following are some important terms used in graph data structure:

Term Description
Vertex All data element is called a vertex or a node. In the above image, A, B, C, D & E are the vertices.
Edge (Arc) Connecting links between two nodes or vertices are called edge (Arc). It has two ends and is represented as (startingVertex, endingVertex).
Undirected Edge It is a bidirectional edge.
Directed Edge It is a unidirectional edge.
Weighted Edge An edge with value on it.
Degree In Graph, the number of edges connected to a vertex is called a degree.
Indegree The total number of incoming edges connected to a vertex.
Outdegree The total number of outgoing edges connected to a vertex.
Self-loop An edge is called a self-loop if its two endpoints coincide.
Adjacency Vertices are said to be adjacent if an edge is connected.

Types of Graphs in Data Structure

Here is the list of the most common types of graphs in the data structure:

  • Directed Graph
  • Undirected Graph
  • Weighted Graph
  • Bi-Directional Graph
  • Infinite Graph
  • Null Graph
  • Trivial Graph
  • Multi Graph
  • Complete Graph
  • Connected Graph
  • Cyclic Graph
  • Directed Acyclic Graph (DAG)
  • Cycle Graph
  • Bipartite Graph
  • Euler Graph
  • Hamilton Graph

Applications of Graph Data Structure

A graph has many use cases. There are a lot of algorithms that use Graphs a lot. Here’re some of the applications of the Graph:

  • Google Maps uses graphs to find the intersection of two roads and calculate the distance between two locations.
    For example, Dijkstra, for finding the shortest distance between source and destination location.
  • Facebook uses Graphs to find the mutual friend of the users. Its algorithm considers each user as a node of a graph.
  • For resource allocation, DAG (Direct Acyclic Graph) is used. It checks the dependency of the resources.
  • Google Search Engine uses graphs to create the ranking for websites.
  • A mapping device uses the graph data structure.
  • Router and t’s protocol uses the Graph to learn the path of the destination path.