Graph Representation

There are several ways to represent a graph in a computer. The choice of representation affects the efficiency of operations.

1. Adjacency Matrix

A 2D matrix where matrix[i][j] = 1 if there is an edge from vertex i to j.

# Graph: A-B, A-C, B-D, C-D
vertices = ['A', 'B', 'C', 'D']
matrix = [
    [0, 1, 1, 0],  # A
    [1, 0, 0, 1],  # B
    [1, 0, 0, 1],  # C
    [0, 1, 1, 0],  # D
]

# Weighted
weighted_matrix = [
    [0, 4, 2, 0],
    [4, 0, 0, 3],
    [2, 0, 0, 5],
    [0, 3, 5, 0],
]

2. Adjacency List

A dictionary where the key is a vertex and the value is a list of neighbors.

# Graph: A-B, A-C, B-D, C-D
adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Weighted
weighted_adj = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 3)],
    'C': [('A', 2), ('D', 5)],
    'D': [('B', 3), ('C', 5)]
}

3. Edge List

A list of all edges as vertex pairs.

# Graph: A-B, A-C, B-D, C-D
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')]

# Weighted
weighted_edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'D', 3), ('C', 'D', 5)]

Comparison

Graph Class Implementation

class Graph:
    def __init__(self, directed=False):
        self.adj_list = {}
        self.directed = directed

    def add_vertex(self, v):
        if v not in self.adj_list:
            self.adj_list[v] = []

    def add_edge(self, v1, v2, weight=1):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adj_list[v1].append((v2, weight))
        if not self.directed:
            self.adj_list[v2].append((v1, weight))

    def get_neighbors(self, v):
        return self.adj_list.get(v, [])

    def get_vertices(self):
        return list(self.adj_list.keys())

g = Graph()
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'D', 3)

print(g.get_neighbors('A'))  # [('B', 4), ('C', 2)]

The adjacency list is the most common representation. Now let's study BFS for level-by-level graph traversal.