A graph is a data structure that represents a collection of interconnected nodes through a set of edges.

This abstract structure is highly versatile and finds applications in various domains, from social network analysis to computer networking.

Core Components

A graph consists of two main components:

1. Nodes: Also called vertices, these are the fundamental units that hold data.
2. Edges: These are the connections between nodes, and they can be either directed or undirected.

Visual Representation

Graph Representations

There are several ways to represent graphs in computer memory, with the most common ones being adjacency matrix, adjacency list, and edge list.

Adjacency Matrix

In an adjacency matrix, a 2D Boolean array indicates the edges between nodes. A value of True at index [i][j] means that an edge exists between nodes i and j.

Here is the Python code:

graph = [
    [False, True, True],
    [True, False, True],
    [True, True, False]
]

Adjacency List

An adjacency list represents each node as a list, and the indices of the list are the nodes. Each node’s list contains the nodes that it is directly connected to.

Here is the Python code:

graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

Edge List

An edge list is a simple list of tuples, where each tuple represents an edge between two nodes.

Here is the Python code:

graph = [(0, 1), (0, 2), (1, 2)]