Graphs - Introduction

November 19, 2025

#graph #data-structures #vertices #edges #graph-theory #algorithms #interviewing

Introduction

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and connections in any direction. Graphs model relationships and networks, making them fundamental to solving real-world problems in social networks, maps, computer networks, and more.

Graphs are one of the most versatile and powerful data structures in computer science. By the end of this tutorial, you’ll understand graph terminology, types of graphs, representation methods, and when to use them.

Review Binary Trees, Arrays, and Hash Tables first if needed.

Graphs model arbitrary relationships between objects, enabling solutions to problems like shortest paths, network flow, social connections, and dependency resolution.

What is a graph?

A graph G = (V, E) consists of:

V: Set of vertices (nodes)
E: Set of edges (connections between vertices)

Example graph:

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

Vertices: {A, B, C, D}
Edges: {(A,B), (A,C), (B,D), (C,D)}

Graph terminology

Basic terms:

Vertex (Node): A point in the graph
Edge: A connection between two vertices
Adjacent vertices: Vertices connected by an edge
Degree: Number of edges connected to a vertex
Path: Sequence of vertices connected by edges
Cycle: Path that starts and ends at the same vertex
Connected graph: Path exists between every pair of vertices

Types of graphs:

1. Directed vs Undirected

Undirected: Edges have no direction (bidirectional)

A --- B  (can go both ways)

Directed (Digraph): Edges have direction (one-way)

A --> B  (can only go A to B)

2. Weighted vs Unweighted

Weighted: Edges have values (costs, distances)

A --5-- B

Unweighted: All edges are equal

A --- B

3. Cyclic vs Acyclic

Cyclic: Contains at least one cycle

A --- B
|     |
C --- D  (A-B-D-C-A is a cycle)

Acyclic: No cycles (DAG = Directed Acyclic Graph)

A --> B
|     |
v     v
C --> D  (no cycles)

4. Dense vs Sparse

Dense: Many edges (close to V²)
Sparse: Few edges (close to V)

Why use graphs?

Choose graphs when:

You need to model relationships between entities
You’re finding shortest paths (navigation, routing)
You’re analyzing social networks (friends, followers)
You’re solving network flow problems
You need dependency resolution (task scheduling)
You’re detecting cycles or connectivity
You’re working with maps, routes, or networks

Avoid graphs when:

You have hierarchical data with no cycles (use trees)
You need simple key-value lookup (use hash tables)
You need sequential access (use arrays or linked lists)

Real-world applications

Graphs are used everywhere:

Social networks: Facebook friends, Twitter followers
Maps & GPS: Road networks, shortest routes
Web: Page rank, link analysis, web crawling
Computer networks: Routing, topology
Recommendation systems: “People who bought X also bought Y”
Dependency management: Package managers (npm, pip)
Biology: Protein interactions, gene networks
Compilers: Call graphs, data flow analysis

Graph representation

1. Adjacency Matrix

A 2D array where matrix[i][j] = 1 if edge exists between vertex i and j.

Vertices: A, B, C, D (indices 0, 1, 2, 3)

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

Matrix:
    A  B  C  D
A [[0, 1, 1, 0],
B  [1, 0, 0, 1],
C  [1, 0, 0, 1],
D  [0, 1, 1, 0]]

Pros: O(1) edge lookup, simple for dense graphs Cons: O(V²) space, inefficient for sparse graphs

2. Adjacency List

An array/hash map where each vertex maps to a list of its neighbors.

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

List:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Pros: O(V + E) space, efficient for sparse graphs Cons: O(degree) edge lookup

Graph implementation

Adjacency List (most common)

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  // Add vertex
  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // Add edge (undirected)
  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  // Add directed edge
  addDirectedEdge(from, to) {
    this.addVertex(from);
    this.addVertex(to);
    this.adjacencyList.get(from).push(to);
  }

  // Remove edge
  removeEdge(v1, v2) {
    if (this.adjacencyList.has(v1)) {
      this.adjacencyList.set(
        v1,
        this.adjacencyList.get(v1).filter(v => v !== v2)
      );
    }
    if (this.adjacencyList.has(v2)) {
      this.adjacencyList.set(
        v2,
        this.adjacencyList.get(v2).filter(v => v !== v1)
      );
    }
  }

  // Remove vertex
  removeVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) return;

    // Remove all edges to this vertex
    for (const neighbor of this.adjacencyList.get(vertex)) {
      this.removeEdge(vertex, neighbor);
    }

    this.adjacencyList.delete(vertex);
  }

  // Get neighbors
  getNeighbors(vertex) {
    return this.adjacencyList.get(vertex) || [];
  }

  // Display graph
  display() {
    for (const [vertex, neighbors] of this.adjacencyList) {
      console.log(`${vertex} -> ${neighbors.join(', ')}`);
    }
  }
}

// Example usage
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');
graph.display();
// A -> B, C
// B -> A, D
// C -> A, D
// D -> B, C

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        """Add vertex"""
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2):
        """Add edge (undirected)"""
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append(v2)
        self.adjacency_list[v2].append(v1)

    def add_directed_edge(self, from_v, to_v):
        """Add directed edge"""
        self.add_vertex(from_v)
        self.add_vertex(to_v)
        self.adjacency_list[from_v].append(to_v)

    def remove_edge(self, v1, v2):
        """Remove edge"""
        if v1 in self.adjacency_list:
            self.adjacency_list[v1] = [
                v for v in self.adjacency_list[v1] if v != v2
            ]
        if v2 in self.adjacency_list:
            self.adjacency_list[v2] = [
                v for v in self.adjacency_list[v2] if v != v1
            ]

    def remove_vertex(self, vertex):
        """Remove vertex"""
        if vertex not in self.adjacency_list:
            return

        # Remove all edges to this vertex
        for neighbor in self.adjacency_list[vertex]:
            self.remove_edge(vertex, neighbor)

        del self.adjacency_list[vertex]

    def get_neighbors(self, vertex):
        """Get neighbors"""
        return self.adjacency_list.get(vertex, [])

    def display(self):
        """Display graph"""
        for vertex, neighbors in self.adjacency_list.items():
            print(f"{vertex} -> {', '.join(map(str, neighbors))}")

# Example usage
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'D')
graph.display()
# A -> B, C
# B -> A, D
# C -> A, D
# D -> B, C

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjacencyList;

    public Graph() {
        adjacencyList = new HashMap<>();
    }

    // Add vertex
    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    // Add edge (undirected)
    public void addEdge(String v1, String v2) {
        addVertex(v1);
        addVertex(v2);
        adjacencyList.get(v1).add(v2);
        adjacencyList.get(v2).add(v1);
    }

    // Add directed edge
    public void addDirectedEdge(String from, String to) {
        addVertex(from);
        addVertex(to);
        adjacencyList.get(from).add(to);
    }

    // Remove edge
    public void removeEdge(String v1, String v2) {
        if (adjacencyList.containsKey(v1)) {
            adjacencyList.get(v1).remove(v2);
        }
        if (adjacencyList.containsKey(v2)) {
            adjacencyList.get(v2).remove(v1);
        }
    }

    // Remove vertex
    public void removeVertex(String vertex) {
        if (!adjacencyList.containsKey(vertex)) return;

        // Remove all edges to this vertex
        for (String neighbor : adjacencyList.get(vertex)) {
            adjacencyList.get(neighbor).remove(vertex);
        }

        adjacencyList.remove(vertex);
    }

    // Get neighbors
    public List<String> getNeighbors(String vertex) {
        return adjacencyList.getOrDefault(vertex, new ArrayList<>());
    }

    // Display graph
    public void display() {
        for (Map.Entry<String, List<String>> entry :
             adjacencyList.entrySet()) {
            System.out.println(entry.getKey() + " -> " +
                             String.join(", ", entry.getValue()));
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("C", "D");
        graph.display();
        // A -> B, C
        // B -> A, D
        // C -> A, D
        // D -> B, C
    }
}

Weighted graph implementation

class WeightedGraph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2, weight) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).push({node: v2, weight});
    this.adjacencyList.get(v2).push({node: v1, weight});
  }

  display() {
    for (const [vertex, neighbors] of this.adjacencyList) {
      const edges = neighbors.map(n => `${n.node}(${n.weight})`).join(', ');
      console.log(`${vertex} -> ${edges}`);
    }
  }
}

const wg = new WeightedGraph();
wg.addEdge('A', 'B', 4);
wg.addEdge('A', 'C', 2);
wg.addEdge('B', 'D', 3);
wg.display();
// A -> B(4), C(2)
// B -> A(4), D(3)
// C -> A(2)
// D -> B(3)

class WeightedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2, weight):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append({'node': v2, 'weight': weight})
        self.adjacency_list[v2].append({'node': v1, 'weight': weight})

    def display(self):
        for vertex, neighbors in self.adjacency_list.items():
            edges = ', '.join(f"{n['node']}({n['weight']})"
                            for n in neighbors)
            print(f"{vertex} -> {edges}")

wg = WeightedGraph()
wg.add_edge('A', 'B', 4)
wg.add_edge('A', 'C', 2)
wg.add_edge('B', 'D', 3)
wg.display()
# A -> B(4), C(2)
# B -> A(4), D(3)
# C -> A(2)
# D -> B(3)

class Edge {
    String node;
    int weight;
    Edge(String node, int weight) {
        this.node = node;
        this.weight = weight;
    }
}

public class WeightedGraph {
    private Map<String, List<Edge>> adjacencyList;

    public WeightedGraph() {
        adjacencyList = new HashMap<>();
    }

    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String v1, String v2, int weight) {
        addVertex(v1);
        addVertex(v2);
        adjacencyList.get(v1).add(new Edge(v2, weight));
        adjacencyList.get(v2).add(new Edge(v1, weight));
    }

    public void display() {
        for (Map.Entry<String, List<Edge>> entry :
             adjacencyList.entrySet()) {
            String edges = entry.getValue().stream()
                .map(e -> e.node + "(" + e.weight + ")")
                .collect(Collectors.joining(", "));
            System.out.println(entry.getKey() + " -> " + edges);
        }
    }
}

Graph algorithms preview

Common graph algorithms (covered in separate tutorials):

Breadth-First Search (BFS): Level-order traversal, shortest path in unweighted graphs
Depth-First Search (DFS): Explore as deep as possible, detect cycles
Dijkstra’s Algorithm: Shortest path in weighted graphs
Bellman-Ford: Shortest path with negative weights
Floyd-Warshall: All-pairs shortest paths
Prim’s/Kruskal’s: Minimum spanning tree
Topological Sort: Ordering of directed acyclic graph
Tarjan’s/Kosaraju’s: Strongly connected components

Complexity analysis

Operation	Adjacency Matrix	Adjacency List
Add vertex	O(V²) (resize)	O(1)
Add edge	O(1)	O(1)
Remove vertex	O(V²)	O(V + E)
Remove edge	O(1)	O(E)
Check if edge exists	O(1)	O(degree)
Get all neighbors	O(V)	O(degree)
Space	O(V²)	O(V + E)

Common pitfalls

Not handling directed vs undirected: Know which you need
Memory issues with dense graphs: Use adjacency matrix
Inefficient sparse graph representation: Use adjacency list
Not detecting cycles: Can cause infinite loops in traversal
Forgetting to mark visited nodes: Leads to infinite loops
Not considering disconnected graphs: Not all graphs are connected

When to prefer other data structures

Hierarchical data without cycles → Use trees
Simple key-value pairs → Use hash tables
Sequential data → Use arrays or linked lists
Priority-based access → Use heaps

Practice problems

Clone a graph
Detect if a cycle exists in an undirected graph
Detect if a cycle exists in a directed graph
Count the number of connected components
Find if a path exists between two vertices
Determine if a graph is bipartite
Find all paths between two vertices
Implement graph coloring
Check if a graph is a tree
Find the number of islands (2D grid graph)
Course schedule problem (detect cycle in directed graph)
Alien dictionary (topological sort)
Network delay time (weighted graph)
Minimum height trees
Reconstruct itinerary (Eulerian path)

Complexity summary

Space:
- Adjacency Matrix: O(V²)
- Adjacency List: O(V + E)
Time: Varies by algorithm (BFS/DFS: O(V + E))

Graphs are the most versatile data structure for modeling relationships. Master graphs and you’ll be able to solve a vast array of real-world problems from social networks to navigation systems.

Table of Contents