Graph Data Structure: Introduction

A Graph is a non-linear data structure used to represent relationships or connections between objects. A graph consists of a collection of vertices, also called nodes, and edges that describe connections between those vertices.

Unlike linear data structures such as arrays, stacks, and queues, graphs do not require elements to be arranged in a single sequence. A vertex can connect to multiple other vertices, making graphs useful for representing complex relationships.

Graphs are used in many areas of software development, including social networks, maps, computer networks, recommendation systems, dependency management, route planning, and search algorithms.

What Is a Graph?

A graph can be represented mathematically as:

G = (V, E)

V = set of vertices
E = set of edges

For example, suppose we have four vertices A, B, C, and D. Connections between them can be represented using edges:

A ----- B
|       |
|       |
C ----- D

Here, A, B, C, and D are vertices, while the lines connecting them are edges.

Vertices and Edges

Vertex

A vertex represents an individual object or entity in a graph. It is also commonly called a node.

In a social network, for example, each user can be represented as a vertex.

Edge

An edge represents a relationship or connection between two vertices.

For example, if two users are connected as friends, an edge can represent that relationship.

Basic Graph Terminology

Directed Graph

In a directed graph, edges have a specific direction. An edge from A to B does not necessarily mean that B can directly reach A.

A ----> B
|
v
C

The edge A → B means that the connection goes from A to B. A separate edge B → A would be required if movement in the opposite direction is allowed.

Directed graphs are useful for modeling one-way relationships such as website links, task dependencies, and one-way roads.

Undirected Graph

In an undirected graph, an edge represents a two-way relationship between vertices.

A ----- B
      |
      |
      C

The edge between A and B means that A is connected to B and B is connected to A.

Weighted Graph

A weighted graph assigns a value to each edge. The weight can represent distance, cost, time, network latency, or another measurable property.

A -- 5 -- B
|
2
|
C

In this example, the cost of traveling from A to B is 5, while the cost from A to C is 2.

Unweighted Graph

An unweighted graph does not assign different numerical costs to its edges. Connections are generally treated as having equal cost. This type of graph is common in problems where the number of connections or steps matters rather than a numerical edge cost.

Self-Loop

A self-loop is an edge that connects a vertex back to itself.

     ┌───┐
     │   │
     ▼   │
     A ──┘

Whether self-loops are allowed depends on the graph model and the problem being solved.

Parallel Edges

A graph can also contain multiple edges connecting the same pair of vertices. These are called parallel edges.

A ===== B
 _____/
  multiple edges

Whether parallel edges are allowed depends on the type of graph being modeled.

Graph Representation

Before working with a graph algorithm, the graph must be represented in a data structure. The two most common representations are the adjacency matrix and adjacency list.

Adjacency Matrix

An adjacency matrix uses a two-dimensional array. The row and column represent vertices, and the value indicates whether an edge exists.

For this graph:

A ----- B
|
C

One possible adjacency matrix is:

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

A value of 1 indicates an edge, while 0 indicates that no direct edge exists. For weighted graphs, the matrix can store edge weights instead.

Adjacency List

An adjacency list stores the neighbors of each vertex. It is particularly useful for sparse graphs because it stores the edges that actually exist rather than reserving space for every possible pair of vertices.

A → B, C
B → A
C → A

In JavaScript, an adjacency list can be represented using an object or a Map.

Creating a Graph with an Adjacency List

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

console.log(graph);

Each property represents a vertex, and its array contains the vertices directly connected to it.

Graph with a Map

A JavaScript Map can also be useful when graph vertices are not simple strings or when explicit key-value semantics are preferred.

const graph = new Map();

graph.set("A", ["B", "C"]);
graph.set("B", ["A", "D"]);
graph.set("C", ["A"]);
graph.set("D", ["B"]);

console.log(graph.get("A"));

Graph Traversal

Graph traversal means visiting vertices in a systematic way. Two fundamental graph traversal algorithms are:

• Breadth-First Search (BFS) visits vertices level by level.
• Depth-First Search (DFS) explores as far as possible before backtracking.

Traversal algorithms are used for searching, connectivity analysis, cycle detection, shortest paths in unweighted graphs, and many other graph problems.

Breadth-First Search

BFS uses a queue to process vertices in increasing order of their distance from the starting vertex.

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  let index = 0;

  while (index < queue.length) {
    const vertex = queue[index++];

    console.log(vertex);

    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

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

bfs(graph, "A");

Depth-First Search

DFS explores one branch of the graph as deeply as possible before returning to explore another branch.

function dfs(graph, vertex, visited = new Set()) {
  if (visited.has(vertex)) {
    return;
  }

  visited.add(vertex);
  console.log(vertex);

  for (const neighbor of graph[vertex]) {
    dfs(graph, neighbor, visited);
  }
}

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

dfs(graph, "A");

Graph Representation Comparison

Dense and Sparse Graphs

The number of edges compared with the number of possible edges affects which graph representation is more practical.

Dense Graph

A graph is considered dense when it contains a large number of edges relative to the number of vertices. An adjacency matrix can be useful because many vertex pairs have direct connections.

Sparse Graph

A sparse graph has relatively few edges compared with the number of possible edges. An adjacency list usually avoids storing many unnecessary entries.

Connected and Disconnected Graphs

In an undirected graph, a graph is connected if every vertex can be reached from every other vertex.

Connected:

A --- B --- C
      |
      D

A graph is disconnected when it contains separate groups of vertices with no path connecting the groups.

A --- B

C --- D

These separate groups are called connected components.

Paths and Cycles

A path is a sequence of vertices connected by edges.

A → B → C → D

A cycle occurs when a path returns to a vertex that was already part of the route.

A → B → C → A

Cycle detection is an important graph problem and can be solved differently for directed and undirected graphs.

Degree of a Vertex

In an undirected graph, the degree of a vertex is the number of edges connected to it.

    B
    |
A---C---D
    |
    E

Degree(C) = 4

In a directed graph, incoming and outgoing edges are considered separately. They are called in-degree and out-degree.

Common Types of Graphs

Graph Algorithms

Once a graph is represented in memory, different algorithms can be applied depending on the problem.

• BFS: traverses a graph level by level.
• DFS: explores graph branches deeply before backtracking.
• Dijkstra: finds shortest paths with non-negative edge weights.
• Bellman-Ford: supports shortest paths with negative edge weights.
• Floyd-Warshall: finds shortest paths between all pairs of vertices.
• Kruskal: finds a minimum spanning tree by processing edges by weight.
• Prim: builds a minimum spanning tree by expanding from a vertex.
• Topological Sort: orders vertices in a directed acyclic graph according to dependencies.

Real-World Applications of Graphs

Graph Complexity

For graph algorithms, complexity is commonly expressed using the number of vertices and edges.

• V: number of vertices.
• E: number of edges.

A graph stored as an adjacency list requires O(V + E) space because the representation stores the vertices and their connections.

An adjacency matrix requires O(V²) space because it stores a value for every possible pair of vertices.

Common Beginner Mistakes

• Confusing vertices with edges.
• Assuming every graph is directed or every graph is undirected.
• Forgetting that edge direction matters in directed graphs.
• Using an adjacency matrix for a very sparse graph without considering its memory cost.
• Forgetting to track visited vertices during BFS or DFS.
• Confusing a path with a cycle.
• Assuming that every graph is connected.
• Using a shortest-path algorithm without checking whether the graph is weighted.

How to Choose a Graph Representation

The choice between an adjacency list and adjacency matrix depends on the graph and the operations your algorithm needs.

• Use an adjacency list when the graph is sparse or when you frequently need to iterate over neighbors.
• Use an adjacency matrix when direct edge lookup is important or the graph is relatively dense.
• For many graph traversal and shortest-path problems, an adjacency list is a practical choice.

Graph Data Structure in Coding Interviews

Graph questions in coding interviews often describe a graph indirectly. Instead of saying "use a graph," a problem may describe cities connected by roads, users connected by friendships, courses connected by prerequisites, or computers connected through a network.

A useful first step is to identify:

1. What represents a vertex?
2. What represents an edge?
3. Are the edges directed or undirected?
4. Are the edges weighted?
5. Can the graph contain cycles?
6. Is the graph guaranteed to be connected?
7. Which operation or traversal does the problem require?

Key Takeaways

• A graph is a non-linear data structure made up of vertices and edges.
• Vertices represent objects or entities, while edges represent relationships.
• Graphs can be directed or undirected.
• Graphs can be weighted or unweighted.
• An adjacency list stores the neighbors of each vertex.
• An adjacency matrix stores relationships between every pair of vertices.
• Adjacency lists generally require O(V + E) space.
• Adjacency matrices require O(V²) space.
• BFS and DFS are fundamental graph traversal algorithms.
• Graphs can model real-world relationships such as networks, routes, dependencies, and social connections.
• Understanding the graph's direction, weights, connectivity, and cycles is important before choosing an algorithm.