juniorGraph Theory

What is a Graph Data Structure?

Updated Apr 28, 2026

Short answer

A graph is a non-linear data structure used to represent relationships between objects. It consists of vertices (nodes) that represent entities and edges that represent connections between those entities. Graphs are used to model networks such as social connections, maps, computer networks, and dependencies.

Deep explanation

A graph is defined as:

TEXT
Graph = (V, E)

where:

  • V represents the set of vertices (nodes).
  • E represents the set of edges (connections).

For example:

TEXT
A
     / \
    B   C
     \ /
      D

Here:

TEXT
Vertices: A, B, C, D


Edges:
A-B
A-C
B-D
C-D

Each vertex represents an object, and each edge represents a relationship between two objects.

Components of a Graph

Vertices (Nodes)

A vertex is an individual element in a graph.

Examples:

  • A person in a social network.
  • A city in a map.
  • A computer in a network.
  • A web page on the internet.

Example:

TEXT
A

A is a vertex.

Edges

An edge connects two vertices.

Example:

TEXT
A ----- B

The edge represents a relationship between A and B.

Edges can have additional information:

  • Distance between cities.
  • Cost of a network connection.
  • Time required to complete a task.

When edges have values, the graph is called a weighted graph.

Example:

TEXT
A --10-- B

The edge weight is 10.

Types of Graphs

Graphs can be categorized in different ways.

Directed vs Undirected Graphs

An undirected graph has edges without direction.

Example:

TEXT
A ----- B

The relationship works both ways.

Examples:

  • Friendship between users.
  • Two-way roads.

A directed graph has edges with a direction.

Example:

TEXT
A ----> B

The connection goes from A to B, but not necessarily from B to A.

Examples:

  • Following someone on social media.
  • Website links.
  • Task dependencies.

Weighted vs Unweighted Graphs

An unweighted graph only represents connections.

Example:

TEXT
A ----- B

A weighted graph assigns values to edges.

Example:

TEXT
A --5-- B

The weight could represent distance, time, or cost.

Connected vs Disconnected Graphs

A connected graph has a path between every pair of vertices.

Example:

TEXT
A --- B --- C

Every node can reach every other node.

A disconnected graph contains separate groups:

TEXT
A --- B      C --- D

There is no path between the two groups.

Graph Representations

Graphs are commonly stored in two ways.

1. Adjacency List

An adjacency list stores each node and its neighbors.

Example:

Python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

Advantages:

  • Uses less memory for sparse graphs.
  • Efficient for graph traversal.

Space complexity:

TEXT
O(V + E)

2. Adjacency Matrix

An adjacency matrix uses a 2D array where each cell represents whether an edge exists.

Example:

TEXT
A B C
A   0 1 1
B   1 0 0
C   1 0 0

Advantages:

  • Fast edge lookup.

Disadvantage:

  • Requires more memory.

Space complexity:

TEXT
O(V²)

Graph Traversal Algorithms

Graphs are often explored using traversal algorithms.

Breadth-First Search (BFS)

BFS explores nodes level by level using a queue.

Common uses:

  • Shortest path in unweighted graphs.
  • Finding nearby nodes.

Example:

TEXT
A → B → C → D

BFS visits nodes by distance from the starting point.

Depth-First Search (DFS)

DFS explores as deeply as possible before backtracking.

Common uses:

  • Cycle detection.
  • Finding connected components.
  • Topological sorting.

Example:

TEXT
A
|
B
|
C

DFS follows one branch until it cannot continue.

Common Graph Algorithms

Graphs are the foundation for many algorithms:

ProblemAlgorithm
Shortest path (unweighted)BFS
Shortest path (weighted)Dijkstra
Minimum spanning treeKruskal, Prim
Dependency orderingTopological Sort
Cycle detectionDFS
Network connectivityBFS/DFS

Real-world example

A navigation application can model roads as a graph.

  • Cities are vertices.
  • Roads are edges.
  • Distance or travel time is the edge weight.

Example:

Python
roads = {
    "New York": [
        ("Boston", 215),
        ("Philadelphia", 95)
    ],
    "Boston": [
        ("New York", 215)
    ],
    "Philadelphia": [
        ("New York", 95)
    ]
}

This graph allows algorithms to answer questions like:

  • What is the shortest route?
  • Are two cities connected?
  • What is the cheapest path?

For example, Dijkstra's algorithm can use this weighted graph to find the minimum travel distance between cities.

Common mistakes

  • * Thinking graphs are only used for geographic maps.
  • * Confusing graphs with trees, since trees are only a special type of graph.
  • * Forgetting that graphs can contain cycles.
  • * Assuming every graph is connected.
  • * Mixing up directed and undirected relationships.
  • * Choosing an adjacency matrix for a very large sparse graph.
  • * Forgetting to track visited nodes during graph traversal.
  • * Assuming the shortest path always means the path with the fewest edges in weighted graphs.

Follow-up questions

  • What is the difference between a graph and a tree?
  • What is the difference between BFS and DFS?
  • How do you represent a graph in code?
  • What is a cycle in a graph?
  • What is the time complexity of traversing a graph?
  • Why are graphs considered a powerful data structure?

More Graph Theory interview questions

View all →