Suggest an edit

Improve this article

Refine the answer for “What are the ways to store graphs?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

There are **three main ways to store graphs**:

---

### 1. **Adjacency List**

Each vertex stores a list of all the vertices it is connected to.

**Example:**
For a graph with edges A-B, A-C, B-C

```javascript
A: B, C
B: A, C
C: A, B
```

**Pros:**

- Memory-efficient for sparse graphs (few edges).
- Convenient for traversing a vertex's neighbors.

**Cons:**

- Looking up a specific edge can be slower than with a matrix.

---

### 2. **Adjacency Matrix**

Uses a square **n×n** matrix, where **n** is the number of vertices.
Cell `[i][j]` = 1 (or a weight) if there is an edge between i and j, otherwise 0.

**Example:**

```javascript
    A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]
```

**Pros:**

- Fast edge-existence check (O(1)).
- Convenient for dense graphs (many edges).

**Cons:**

- Takes O(n²) memory, even if there are few connections.

---

### 3. **Edge List**

Simply stores a list of all edges as pairs (or triples, if weighted):

```javascript
[(A, B), (A, C), (B, C)]
```

```javascript
[(A, B, 5), (B, C, 3), (A, C, 8)]
```

**Pros:**

- Simple structure.
- Convenient for algorithms that work directly with edges (for example, Kruskal's).

**Cons:**

- Inconvenient for looking up a vertex's neighbors.

---

**Summary:**

| Method | Memory | Convenient for | Example use |
|---|---|---|---|
| Adjacency list | O(V + E) | traversals and pathfinding | Dijkstra, BFS, DFS algorithms |
| Adjacency matrix | O(V²) | fast connection checks | dense graphs |
| Edge list | O(E) | working with edges directly | Kruskal's algorithm |

Markdown · drag & drop images · ⌘B / ⌘I shortcuts279 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.