Graph in Data Structure | Types & Explanation

TL;DR: A graph data structure is used to store connected data. It helps solve problems in maps, social networks, search engines, recommendation systems, computer networks, and AI.

Before learning algorithms like BFS, DFS, shortest path, or network routing, it is important to understand what is a graph in data structure.

A graph is a non-linear data structure. It stores data as nodes and connections. The nodes are called vertices. The connections between them are called edges.

Unlike arrays, stacks, or queues, graphs do not follow a straight order. They show relationships. This makes them useful when data is connected in many ways.

For example, in a social media app, each user can be a vertex. A friendship or follow can be an edge. In Google Maps, each location can be a vertex. Each road can be an edge. Google Maps serves over 2 billion monthly users, which shows how important connected location data has become in real life.

Basic Structure

A graph has two main parts:

• Vertex: A point or node in the graph
• Edge: A connection between two vertices

Example:

A ----- B

|       |

|       |

C ----- D

Here:

• A, B, C, and D are vertices
• A-B, A-C, B-D, and C-D are edges

This simple diagram shows how graphs in data structure can represent connected objects.

Key Terminologies in Graphs

Let us understand the basic terms with simple examples.

1. Vertex

A vertex is a node in a graph. It stores data.

Example:

A

Here, A is a vertex. In a map, a city can be a vertex. On a website, a page can be a vertex.

2. Edge

An edge connects two vertices.

Example:

A ----- B

Here, the line between A and B is an edge. It shows that A and B are connected.

3. Path

A path is a sequence of vertices connected by edges.

Example:

A ----- B ----- C

The path from A to C is:

A → B → C

A path is useful when we want to move from one point to another.

4. Degree

The degree of a vertex means the number of edges connected to it.

Example:

    B

    |

A---C---D

Here, C has three edges. So, the degree of C is 3.

In a directed graph, the degree is divided into:

• In-degree: Number of incoming edges
• Out-degree: Number of outgoing edges

5. Cycle

A cycle happens when a path starts and ends at the same vertex.

Example:

A ----- B

|       |

D ----- C

One cycle is:

A → B → C → D → A

Cycles are important in route planning, dependency checking, and network design.

Learn 45+ in-demand full-stack development skills and tools, including Frontend Development, Backend Development, Version Control and Collaboration, Database Management, and AI Assisted Development, with our AI-Powered Full Stack Developer Course.

Types of Graphs in Data Structure

The major types of graphs in data structures are listed below. Each one is useful for a different kind of problem.

A directed network is one type of graph in data structure where direction matters. For example, if A follows B, it does not always mean B follows A.

Advance Your Full Stack Career!AI-Powered Full Stack Developer ProgramEXPLORE COURSE

Graph Representation in Data Structure

Graph representation means how we store a graph in computer memory.

There are two common methods:

• Adjacency matrix
• Adjacency list

Both store the same graph. But they do it in different ways.

Let us use this graph:

A ----- B

|       |

C ----- D

Edges are:

A-B, A-C, B-D, C-D

Adjacency Matrix Representation

An adjacency matrix is a table that shows connections between vertices.

If two vertices are connected, we write 1. If they are not connected, we write 0.

1. Matrix Example

This matrix shows that:

• A is connected to B and C
• B is connected to A and D
• C is connected to A and D
• D is connected to B and C

2. Structure

An adjacency matrix is a 2D array. For a graph with V vertices, the matrix size is V × V.

For example, if a graph has 5 vertices, the matrix has 25 cells.

Adjacency List Representation

An adjacency list stores each vertex with a list of its connected vertices.

For the same graph:

A ----- B

|       |

C ----- D

List Example

A → B, C

B → A, D

C → A, D

D → B, C

This means:

• A is connected to B and C
• B is connected to A and D
• C is connected to A and D
• D is connected to B and C

Matrix Example Comparison

The same graph can be stored as a matrix or a list. The matrix shows all possible connections. The list shows only existing connections.

This makes adjacency lists better for sparse graphs.

Structure

An adjacency list is usually implemented with an array or a hash map. Each vertex points to a list of neighbors.

Example:

Graph = {

  A: [B, C],

  B: [A, D],

  C: [A, D],

  D: [B, C]

}

Advantages

• It saves memory for sparse graphs
• It is easy to find all the neighbors of a vertex
• It works well for large networks
• It is commonly used in real-world graph problems

Limitations

• Checking whether a direct edge exists can take longer
• It may be less simple for beginners
• It needs extra handling for weighted graphs

Get the Coding Skills You Need to SucceedAI-Powered Full Stack Developer ProgramExplore Program

Graph Traversal Techniques

Graph traversal is the process of visiting each vertex in a graph.

The two most common traversal techniques are:

• Breadth-First Search
• Depth-First Search

These are core algorithms. The U.S. Bureau of Labor Statistics projects software developer, QA analyst, and tester jobs to grow 15% from 2024 to 2034. This makes data structures and algorithms useful for learners who want to build strong programming careers. 

BFS Overview

BFS stands for Breadth-First Search.

It visits vertices level by level. It starts from one vertex. Then it visits all its neighbors. After that, it moves to the next level.

Example graph:

    A

   / \

  B   C

 /     \

D       E

If BFS starts at A, the order can be:

A → B → C → D → E

How BFS Works

• Start from a vertex
• Visit it
• Add its neighbors to a queue
• Remove the next vertex from the queue
• Repeat until all reachable vertices are visited

Where BFS Is Used

BFS is used in:

• Shortest path in unweighted graphs
• Social network connection search
• Web crawling
• Level-order search
• Peer-to-peer networks

DFS Overview

DFS stands for Depth-First Search.

It goes deep into one path before coming back.

Using the same graph:

    A

   / \

  B   C

 /     \

D       E

If DFS starts at A, the order can be:

A → B → D → C → E

How DFS Works

• Start from a vertex
• Visit it
• Move to one unvisited neighbor
• Keep going deeper
• Backtrack when there is no unvisited neighbor

Where DFS Is Used

DFS is used in:

• Cycle detection
• Topological sorting
• Maze solving
• Path finding
• Connected component detection

Traversal Diagram

Here is a simple visual comparison.

Graph:

        A

      /   \

     B     C

    / \     \

   D   E     F

BFS order:

A → B → C → D → E → F

DFS order:

A → B → D → E → C → F

BFS spreads out first. DFS goes deeper first.

Design Smarter AI WorkflowsExplore AI Agentic Domain End-to-EndEnroll Now

Real-World Applications of Graphs

Graphs are used in many systems that people use every day.

1. Social Networks

Users are vertices. Friendships, follows, likes, or messages are edges. LinkedIn has more than 1 billion members worldwide. A platform of this scale needs robust methods for understanding connections. 

2. Maps and Navigation

Locations are vertices. Roads are edges. A weighted graph can store distances, travel times, or toll costs.

Navigation apps use graph algorithms to find the best route.

3. Search Engines

Web pages can be vertices. Links between pages can be edges. Search engines use graph-based ideas to understand how pages are connected.

4. Recommendation Systems

Graphs help recommend products, movies, courses, and jobs.

For example:

User → Watched Course

User → Liked Topic

Topic → Related Course

This helps systems suggest better content.

5. Computer Networks

Routers, servers, and devices are vertices. Network links are edges.

Graphs help find efficient routes for data transfer.

6. Fraud Detection

Graphs help detect unusual relationships.

For example, many accounts linked to the same phone number, address, or payment method may show suspicious activity.

7. Knowledge Graphs and AI

Knowledge graphs connect facts and entities. They help AI systems understand relationships between people, places, products, and concepts. Reports by MARKETSANDMARKETS suggest that the knowledge graph market may grow from USD 1.90 billion in 2026 to USD 9.88 billion by 2032.

Now that you have learned graphs in data structures, the next step is applying them to build real AI solutions. Simplilearn's AI Accelerator Program helps you go beyond algorithms by building AI applications, intelligent agents, and automated workflows through 8 weeks of live, hands-on learning. Graduate with a portfolio of 10+ AI projects using industry-standard tools like Claude, LangChain, and n8n.

Key Takeaways

• A graph stores connected data using vertices and edges. It is useful when relationships matter.
• Common graph types include directed, undirected, weighted, unweighted, cyclic, and acyclic graphs.
• BFS visits nodes level by level, and DFS explores one path deeply before backtracking.
• Graphs are used in maps, social media, AI, search engines, networks, and fraud detection.

FAQs

1. What are the types of graphs in data structures?

The common types are directed graphs, undirected graphs, weighted graphs, unweighted graphs, cyclic graphs, acyclic graphs, connected graphs, disconnected graphs, and complete graphs.

2. What is a graph representation in a data structure?

Graph representation means storing a graph in memory. The two most common methods are the adjacency matrix and the adjacency list.

3. What is an adjacency matrix?

An adjacency matrix is a 2D table. It uses 1 to show a connection and 0 to show no connection between vertices.

4. What is an adjacency list?

An adjacency list stores every vertex with a list of its neighbors. It is memory-efficient for large and sparse graphs.

5. What is the difference between directed and undirected graphs?

In a directed graph, edges have direction. For example, A → B. In an undirected graph, edges have no direction. For example, A — B means both vertices are connected equally.