# Custom Graph

## About

Graphs are **non-linear data structures** consisting of **vertices (nodes)** and **edges (connections between nodes)**. They can represent **real-world relationships** like **social networks, road maps, and computer networks**.

### **Types of Graph Representation**

There are multiple ways to implement graphs in a computer program, each with its own advantages and trade-offs. The **three most common implementations** are:

1. **Adjacency Matrix**
2. **Adjacency List**
3. **Edge List**

## **Adjacency Matrix Representation**

An **Adjacency Matrix** is a **2D array (V × V matrix)** where **V is the number of vertices**. Each **cell (i, j)** indicates whether there is an **edge** between vertex **i** and vertex **j**.

### **Structure**

* For an **unweighted graph**, the matrix contains **0 (no edge)** or **1 (edge exists)**.
* For a **weighted graph**, the matrix stores the **weight of the edge** instead of 1.

### **Example: Adjacency Matrix for an Undirected Graph**

Consider the following undirected graph:

```
    (A) --1-- (B)
     |       / |
     4    3    | 
     | /       |
    (C) --2-- (D)
```

|   | A | B | C | D |
| - | - | - | - | - |
| A | 0 | 1 | 4 | 0 |
| B | 1 | 0 | 3 | 1 |
| C | 4 | 3 | 0 | 2 |
| D | 0 | 1 | 2 | 0 |

## **Adjacency List Representation**

An **Adjacency List** represents a graph as an **array of linked lists (or lists in general)**. Each **vertex** has a list of all the **adjacent vertices** (neighbors).

### **Structure**

For the same undirected graph:

```
    (A) --1-- (B)
     |       / |
     4    3    | 
     | /       |
    (C) --2-- (D)
```

The adjacency list would look like:

```
A → [(B,1), (C,4)]
B → [(A,1), (C,3), (D,1)]
C → [(A,4), (B,3), (D,2)]
D → [(B,1), (C,2)]
```

For a **directed graph**, the edges point in **one direction only**.

```
    A → B
    A → C
    B → C
    C → D
```

Adjacency List Representation

```
A → [B, C]
B → [C]
C → [D]
D → []
```

## **Edge List Representation**

An **Edge List** is a **list of all edges**, where each edge is represented as a **pair (or triplet for weighted graphs)**.

### **Structure**

For the same undirected graph:

```
    (A) --1-- (B)
     |       / |
     4    3    | 
     | /       |
    (C) --2-- (D)
```

The edge list would look like:

| Edge | Start | End | Weight |
| ---- | ----- | --- | ------ |
| 1    | A     | B   | 1      |
| 2    | A     | C   | 4      |
| 3    | B     | C   | 3      |
| 4    | B     | D   | 1      |
| 5    | C     | D   | 2      |

## **Choosing the Right Implementation**

1. **Use Adjacency Matrix when**
   * The graph is **dense** (i.e., E≈V^2).
   * Fast edge lookup is required O(1).
   * The graph doesn't change frequently.
2. **Use Adjacency List when**
   * The graph is **sparse** (i.e., E≪ V^2E).
   * Space efficiency is a concern.
   * Need to iterate over neighbors frequently.
3. **Use Edge List when**
   * The graph changes dynamically (adding/removing edges frequently).
   * Need a **compact** edge representation.
   * Algorithms like **Kruskal’s Algorithm** (which sorts edges) are required.