Graphs

Question¶

Define graphs and provide different data structures to represent them.

Graph definition¶

• Graph = vertices + edges.
• Can be directed or undirected.
• Can be weighted or unweighted.

Example graph¶

A -- B
|    |
C -- D

Representation 1: objects and pointers¶

Each node stores references to neighbor nodes.

class GraphNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

a = GraphNode("A")
b = GraphNode("B")
c = GraphNode("C")
a.neighbors = [b, c]
b.neighbors = [a]
c.neighbors = [a]

• Key trick

  • Natural when graph is built as linked objects.

• Trap

  • Harder to map nodes to indices; cloning/cycle handling is tricky.

• Use

  • OO modeling, graph clone problems.
• Do not use
  • When you need compact storage or matrix algorithms.

Representation 2: adjacency matrix¶

matrix[u][v] stores edge existence or weight.

n = 4
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = matrix[1][0] = 1
matrix[0][2] = matrix[2][0] = 1

• Key trick

  • Edge lookup is \(O(1)\).

• Trap

  • Space is \(O(V^2)\), bad for sparse graphs.

• Use

  • Dense graphs, Floyd-Warshall, quick edge checks.

Representation 3: adjacency list¶

Map each node to list of neighbors.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

• Key trick

  • Best default for sparse graphs.

• Trap

  • Edge existence check is not \(O(1)\) unless neighbor sets are used.

• Use

  • Most interview graph problems.

Pytest¶

import pytest

def matrix_has_edge(matrix, u, v):
    return matrix[u][v] != 0

def adj_has_edge(graph, u, v):
    return v in graph.get(u, [])

@pytest.mark.parametrize(
    "u, v, expected",
    [
        (0, 1, True),
        (1, 2, False),
        (0, 2, True),
    ],
)
def test_graph_representations(u, v, expected):
    matrix = [
        [0, 1, 1],
        [1, 0, 0],
        [1, 0, 0],
    ]
    graph = {
        0: [1, 2],
        1: [0],
        2: [0],
    }

    assert matrix_has_edge(matrix, u, v) == expected
    assert adj_has_edge(graph, u, v) == expected