> For the complete documentation index, see [llms.txt](https://www.pranaypourkar.co.in/the-programmers-guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.pranaypourkar.co.in/the-programmers-guide/algorithm/data-structure-implementation/custom-graph.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.