Overview

A graph is a flexible non-linear structure for modeling relationships. Maps, social networks, computer networks, recommendation engines, and flight routes can all be represented as objects connected to one another.

Key concepts

• Vertices represent objects or locations
• Edges represent connections between vertices
• Graphs may be directed, undirected, weighted, or unweighted
• Unlike trees, graphs may contain cycles and multiple paths

What is a Graph?

A graph is a collection of vertices—also called nodes—connected by edges.

      A
     /     B---C
           D

A, B, C, and D are vertices. The lines are edges. A graph can have several routes between vertices and may contain loops.

Why do we need Graphs?

Consider cities connected by roads. Cities become vertices and roads become edges. The resulting graph can answer whether two cities are reachable, which cities are directly connected, and which route is shortest.

Types of Graphs

Undirected Graph

An undirected edge works in both directions. If A is connected to B, B is also connected to A. Mutual friendship is a common example.

A ───── B

Directed Graph

A directed edge has an arrow. A may point to B without B pointing back to A, like following an account on social media.

A ─────→ B

Weighted Graph

A weighted edge stores a value such as distance, cost, time, or capacity. Navigation systems use weights to choose efficient routes.

A ──5── B

Graph Representation

Adjacency List

Each vertex stores its neighbors. Adjacency lists use O(V + E) space and are well suited to sparse graphs.

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

console.log(graph.A); // ["B", "C"]

Adjacency Matrix

A matrix uses a row and column for every pair of vertices. A 1 indicates an edge and 0 indicates no edge.

    A B C
A [ 0 1 1 ]
B [ 1 0 0 ]
C [ 1 0 0 ]

Matrices use O(V²) space but provide O(1) edge checks, making them useful for dense graphs.

Graph Traversal

Traversal visits reachable vertices while tracking those already seen. The visited set prevents infinite loops in cyclic graphs.

Breadth-First Search (BFS)

BFS uses a queue to explore vertices level by level. In an unweighted graph, it can find paths containing the fewest edges.

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

  while (head < queue.length) {
    const vertex = queue[head++];
    console.log(vertex);

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

Depth-First Search (DFS)

DFS uses recursion or a stack to explore one route deeply before backtracking. It supports cycle detection, maze solving, and connected-component discovery.

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

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

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

Time complexity

V is the number of vertices and E is the number of edges. BFS and DFS process each reachable vertex and edge at most a constant number of times.

Real-life examples

In a social network, users are vertices and friendships are edges. The graph can reveal mutual friends, recommend connections, or measure degrees of separation. In navigation, places are vertices and roads are weighted edges.

Advantages of Graphs

• Represent complex relationships naturally
• Model real-world networks
• Support powerful traversal and path algorithms
• Handle many-to-many relationships
• Adapt to directed and weighted connections

Limitations of Graphs

• More complex than linear data structures
• Traversal requires visited-state management
• Large dense graphs can consume substantial memory
• Some advanced graph problems are computationally expensive

Where are Graphs used?

• Maps and GPS navigation
• Social media
• Airline routes
• Computer networks
• Recommendation systems
• Search engines
• Project dependencies
• Artificial Intelligence

Tips for beginners

• Start with vertices and edges
• Draw small graphs by hand
• Learn adjacency lists before matrices
• Always track visited vertices during traversal
• Master BFS and DFS before shortest paths and spanning trees

Key takeaways

• Graphs model connected objects
• Vertices are objects and edges are relationships
• Graphs may be directed, undirected, or weighted
• Adjacency lists and matrices are the main representations
• BFS explores by level
• DFS explores by path
• Adjacency-list traversal takes O(V + E)
• Graphs lead to Dijkstra, Prim, Kruskal, and network-flow algorithms