Skip to content
Concept ยท Data Structures and Algorithms

Graph Data Structure Explained: Types, Representation, BFS, DFS and Code in Python and JavaScript

By Younus FardeenUpdated 11 Nov 202612 min read
Short answer

A graph is a data structure made of vertices (nodes) and edges, the links between them. It can be directed or undirected, weighted or unweighted, connected or disconnected, cyclic or acyclic. Store it as an adjacency list or matrix and explore it with breadth-first search (BFS) or depth-first search (DFS), both O(V + E).

Graphs appear in DSA (data structures and algorithms) courses, college exams and most coding interviews. This page covers the terms people search for (graph in DSA, disconnected graph, cyclic graph, acyclic graph) and then the code.

Every code block was run on Python 3.9 and Node 24 on 11 November 2026 and the output shown is the real output. Complexity figures were checked against Wikipedia's graph, BFS and DFS pages on the same date.

  1. 1Model itdecide what the vertices and edges are
  2. 2Store itadjacency list in most cases
  3. 3Traverse itBFS for nearest first, DFS for deep first
  4. 4Answer itpath, cycle, components or order
Most graph problems follow the same four steps.

What a graph is, and the types of graph

A graph is a set of vertices (also called nodes) joined by edges, written G = (V, E). Cities joined by roads, people joined by friendships and web pages joined by links are all graphs: the cities, people and pages are vertices, and the roads, friendships and links are edges.

TermMeaningExample
Vertex (node)One point in the graphA city
EdgeA link between two verticesA road
DegreeNumber of edges at a vertex (in-degree and out-degree in a directed graph)A person with 120 friends has degree 120
PathA sequence of vertices where each consecutive pair is joined by an edgeDelhi, Jaipur, Ahmedabad
CycleA path that ends where it startedA, B, D, C, back to A
WeightA number stored on an edgeDistance in km

A tree is a special graph: connected, with no cycles. Most of what follows also applies to trees.

Types of graphs

TypeWhat it meansReal example
UndirectedAn edge works both waysFacebook-style friendship
Directed (digraph)An edge has a direction: A to B is not B to AFollows on Instagram, one-way streets
Weighted or unweightedWeighted edges carry a cost. In an unweighted graph every edge counts the same, so length means number of edgesRoad length, ticket price, hops between people
ConnectedEvery vertex can reach every other vertexA road network with no cut-off town
DisconnectedSome vertices cannot reach othersTwo islands with no bridge
CyclicContains at least one cycleA ring road
AcyclicContains no cycleA family tree
DAG (directed acyclic graph)Directed edges and no cycleCourse prerequisites, build order

Connected vs disconnected graph

In a connected graph you can walk from any vertex to any other. In a disconnected graph at least one pair has no path between them, and the graph splits into two or more connected components. A traversal from one vertex only visits its own component, so to cover a disconnected graph you loop over all vertices and start a new traversal at each one you have not seen.

Cyclic vs acyclic graph

A cyclic graph has at least one cycle, a path that returns to its starting vertex. An acyclic graph has none. A connected, acyclic, undirected graph is a tree, and a tree with n vertices has exactly n - 1 edges. A DAG is the directed version: you can never follow its edges back to where you began. That makes a DAG fit for tasks with prerequisites, because the tasks can be put in a topological order where each task comes after the ones it needs.

Adjacency list vs adjacency matrix

These are the two standard ways to store a graph in memory. An adjacency list keeps, for each vertex, the list of its neighbours. An adjacency matrix is a V by V grid where a 1 in row u, column v means there is an edge from u to v. This code builds both for the same five-vertex graph:

nodes = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

# adjacency list: each node maps to the list of its neighbours
adj = {n: [] for n in nodes}
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)          # undirected: store the edge both ways

# adjacency matrix: a grid where 1 means "there is an edge"
pos = {n: i for i, n in enumerate(nodes)}
matrix = [[0] * len(nodes) for _ in nodes]
for u, v in edges:
    matrix[pos[u]][pos[v]] = 1
    matrix[pos[v]][pos[u]] = 1

print(adj)
for row in matrix:
    print(row)
print("B-D edge?", "D" in adj["B"], matrix[pos["B"]][pos["D"]] == 1)

Output:

{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C', 'E'], 'E': ['D']}
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 0, 0, 1, 0]
B-D edge? True True
Adjacency listAdjacency matrix
MemoryO(V + E)O(V^2)
Is there an edge between u and v?O(degree of u)O(1)
List all neighbours of uO(degree of u)O(V)
Add an edgeO(1)O(1)
Remove an edgeO(degree of u)O(1)
Visit every vertex and edge (BFS or DFS)O(V + E)O(V^2)
Best forSparse graphs, which is most real dataSmall or dense graphs, or constant-time edge checks

Use an adjacency list unless the graph is small and dense. In interviews the input usually arrives as a list of edges, so the first step is building a dictionary of lists, which is the hash map pattern.

BFS and DFS: the two ways to explore a graph

Breadth-first search (BFS) visits the start vertex, then all its neighbours, then their neighbours, and so on, using a queue (see applications of queue). In an unweighted graph it finds the fewest-edges path. Depth-first search (DFS) follows one branch as far as it goes, then backs up, using recursion or a stack (see recursion).

BFSDFS
UsesA queueRecursion or a stack
OrderNearest vertices first, level by levelOne branch to its end, then back up
Good forShortest path by edge count, nearest match, level problemsConnectivity, cycles, components, topological order, backtracking
TimeO(V + E)O(V + E)
Extra memoryO(V), the queue can hold a whole levelO(V), the stack can hold the longest path

Python version. The graph has a second component, G and H, that no search from A can reach:

from collections import deque

graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"],
    "G": ["H"], "H": ["G"],           # G and H are a separate component
}

def bfs(start):
    """Fewest edges from start to every reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

def dfs(node, seen=None, order=None):
    """Visit order of a recursive depth-first search."""
    seen = set() if seen is None else seen
    order = [] if order is None else order
    seen.add(node)
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt, seen, order)
    return order

print(bfs("A"))
print(dfs("A"))

Output:

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
['A', 'B', 'D', 'C', 'E', 'F']

The first line is the BFS distance, in edges, from A. G and H are missing because they are in another component. The second line is the DFS visit order. JavaScript version of the same two searches:

const graph = {
  A: ["B", "C"], B: ["A", "D"], C: ["A", "D", "E"],
  D: ["B", "C", "F"], E: ["C", "F"], F: ["D", "E"],
  G: ["H"], H: ["G"],
};

function bfs(start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {   // index, not shift(), so it stays fast
    const node = queue[head];
    for (const next of graph[node]) {
      if (!dist.has(next)) {
        dist.set(next, dist.get(node) + 1);
        queue.push(next);
      }
    }
  }
  return Object.fromEntries(dist);
}

function dfs(node, seen = new Set()) {
  seen.add(node);                                     // a Set keeps insertion order
  for (const next of graph[node]) {
    if (!seen.has(next)) dfs(next, seen);
  }
  return [...seen];
}

console.log(bfs("A"));
console.log(dfs("A").join(" "));

Output:

{ A: 0, B: 1, C: 1, D: 2, E: 2, F: 3 }
A B D C E F

Count connected components and detect a cycle

These two checks are asked so often that they are worth knowing cold. To count components, start a search from every vertex you have not seen and add one each time. To detect a cycle in an undirected graph, run DFS and report a cycle if you reach an already-seen vertex that is not the one you just came from.

graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"],
    "G": ["H"], "H": ["G"],
}
tree = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}      # 3 nodes, 2 edges, no cycle

def count_components(g):
    seen, count = set(), 0
    for start in g:
        if start in seen:
            continue
        count += 1                         # a node we had not reached: new component
        stack = [start]
        seen.add(start)
        while stack:
            node = stack.pop()
            for nxt in g[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
    return count

def has_cycle(g):
    """Cycle check for a simple undirected graph (no repeated edges)."""
    seen = set()
    def visit(node, parent):
        seen.add(node)
        for nxt in g[node]:
            if nxt == parent:
                continue                   # do not treat the edge we came by as a cycle
            if nxt in seen or visit(nxt, node):
                return True
        return False
    return any(visit(n, None) for n in g if n not in seen)

print(count_components(graph), has_cycle(graph))
print(count_components(tree), has_cycle(tree))

Output:

2 True
1 False

The first graph has two components and a cycle (A, B, D, C). The three-vertex tree has one component and no cycle. For a directed graph the "came from" trick does not work, because an edge back to a seen vertex is not always a cycle. Use Kahn's algorithm instead: repeatedly remove vertices that have no incoming edge. If some vertices can never be removed, the graph has a cycle.

// Directed graph with nodes 0..n-1. Kahn's algorithm: repeatedly remove nodes
// with no incoming edge. If some nodes are never removed, the graph has a cycle.
function hasCycle(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indegree = Array(n).fill(0);
  for (const [u, v] of edges) {
    adj[u].push(v);
    indegree[v]++;
  }
  const queue = [];
  indegree.forEach((d, i) => { if (d === 0) queue.push(i); });
  let removed = 0;
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    removed++;
    for (const v of adj[u]) {
      if (--indegree[v] === 0) queue.push(v);
    }
  }
  return removed < n;
}

console.log(hasCycle(4, [[0, 1], [1, 2], [2, 3]]));          // a chain: no cycle
console.log(hasCycle(4, [[0, 1], [1, 2], [2, 3], [3, 1]]));  // 1 -> 2 -> 3 -> 1

Output:

false
true

The same removal order is a topological order, which the applications of graph page uses for build and dependency ordering.

When to use a graph, and the problem types to expect

Reach for a graph when a problem is about things and the connections between them, or when you can describe it as moves between states. These signals appear again and again in interviews:

Signal in the problemHow to model itUsual technique
Grid of cells: islands, mazes, spreadingEach cell is a vertex, its four neighbours are edgesBFS or DFS
Fewest steps, moves or mutationsEach state is a vertex, each move an edgeBFS
Cheapest or shortest with different costsWeighted edgesDijkstra's algorithm
Tasks with prerequisites, ordering, deadlockDirected edges from need to dependentTopological sort, cycle check
Friends, groups, merging setsUndirected edgesDFS or Union-Find
Split into two teams, two coloursBipartite checkBFS or DFS colouring
Can A reach B?Any graphBFS or DFS

Interview problem families, by name only, so you can read the statements yourself: Number of Islands and Rotting Oranges (grid BFS or DFS), Clone Graph (traversal with a map), Course Schedule and Course Schedule II (cycle detection and topological order), Word Ladder (BFS over states), Network Delay Time (weighted shortest path), Is Graph Bipartite? (colouring) and Redundant Connection (cycle in an undirected graph).

Common mistakes and practice problems

Common mistakes

  • No visited set. Any graph with a cycle sends the search round in circles forever.
  • Assuming one search covers everything. It covers one component. Loop over all vertices for a disconnected graph.
  • Using list.pop(0) as the BFS queue. It shifts every element, which the Python documentation describes as an O(n) cost. Use collections.deque.
  • Marking a vertex visited only when it is dequeued. The same vertex can be queued many times. Mark it when you add it to the queue.
  • Storing an undirected edge in one direction only. Add it to both vertices' lists.
  • Deep recursion. Python stops a recursive function at about 1,000 nested calls by default, so a long path can crash a recursive DFS. Use an explicit stack for big inputs.

Practice problems, in order

  1. Find if Path Exists in Graph (traversal basics)
  2. Number of Provinces (count components)
  3. Number of Islands (grid as a graph)
  4. Clone Graph
  5. Course Schedule (directed cycle)
  6. Rotting Oranges (multi-source BFS)
  7. Pacific Atlantic Water Flow
  8. Word Ladder

Masai's longer guide: Graph Data Structure: Types, Representation, BFS, DFS. Next, see where graphs are used in applications of graph in data structure, then practise on the coding practice websites list or follow the DSA learning path.

Frequently asked questions

What is a graph in data structure?

A data structure made of vertices (nodes) and edges (links between them). It models relationships such as roads between cities or friendships between people, and is usually stored as an adjacency list or an adjacency matrix.

What is a disconnected graph?

A graph in which at least one pair of vertices has no path between them, so it splits into two or more connected components. A search from one vertex reaches only its own component, so start a new search from every unvisited vertex.

What is the difference between a cyclic and an acyclic graph?

A cyclic graph contains at least one cycle, a path that returns to its start. An acyclic graph has none. A directed acyclic graph (DAG) can be ordered so every edge points forward, which is why it is used for task dependencies.

Should I use an adjacency list or an adjacency matrix?

Use an adjacency list for most problems: it takes O(V + E) memory and lists neighbours quickly. Use a matrix only when the graph is small or dense, or when you need O(1) edge checks.

What is the difference between BFS and DFS?

BFS explores level by level with a queue and finds the fewest-edges path in an unweighted graph. DFS follows one branch to the end before backing up, using recursion or a stack, and suits connectivity, cycle detection and topological order. Both run in O(V + E).

How do you detect a cycle in a graph?

In an undirected graph, run DFS and report a cycle if you reach a seen vertex that is not the one you came from. In a directed graph, use Kahn's algorithm: if you cannot remove every vertex by repeatedly taking those with no incoming edge, a cycle exists.

Sources checked

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Continue learning

Concept

Applications of graph

Where graphs are used in real software, with a tiny runnable example each

Open →
Concept

Tree data structure

Binary trees, BST, traversals, height and balance with tested code

Open →
Explainer

Applications of queue

Where queues are used: scheduling, BFS, buffers, with code.

Open →