# 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.pranaypourkar.co.in/the-programmers-guide/algorithm/data-structure-implementation/custom-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.