Graphs 101: A Simple Visual Introduction

2.1 Directed vs Undirected

• A directed graph has edges that point in one direction. It shows a one-way relationship (A → B).

• An undirected graph has edges without direction. It shows a two-way or mutual relationship (A — B).

2.2 Weighted vs Unweighted

• A weighted graph has numbers (weights) on its edges. These weights can represent distance, cost, time, or anything measurable.

• An unweighted graph treats all edges as equal. There is no concept of distance or cost between nodes.

2.3 Cyclic vs Acyclic

• A cyclic graph has at least one cycle. A cycle means you can start at a node, follow edges, and come back to the same node.

• An acyclic graph has no cycles. You can never return to the starting node by following the edges.

2.4 Connected vs Disconnected

• A connected graph has all nodes reachable from one another. There is a path between every pair of nodes.

• A disconnected graph has some nodes or groups of nodes that cannot be reached from others. It has separate components.

3.1 Adjacency List

const graph1 = {
  1: [2],
  2: [3],
  3: [],
};

const graph2 = {
  1: [2],
  2: [1, 3],
  3: [2],
};

When to use Adjacency List?

• Graph has many nodes but fewer edges
• You want efficient traversal (BFS, DFS)
• You want to store real-world networks (maps, social networks, etc.)

3.2 Adjacency Matrix

An adjacency matrix is a 2D grid (N * N) where:

• 1 means an edge exists
• 0 means no edge

It is easy to read but uses more memory.

const matrix1 = [
  // 1  2  3
  [0, 1, 0], // 1
  [0, 0, 1], // 2
  [0, 0, 0], // 3
];

const matrix2 = [
  // 1  2  3
  [0, 1, 0], // 1
  [1, 0, 1], // 2
  [0, 1, 0], // 3
];

When to use Adjacency Matrix?

• Graph is dense (lots of edges)
• You need constant-time edge lookup
• Useful in algorithms like Floyd-Warshall

3.3 Quick Summary

• Adjacency List: stores neighbors, memory efficient
• Adjacency Matrix: grid of 0/1 values, fast edge lookup
• Both describe the same graph but focus on different things