Graph Theory Basics: Nodes, Edges, and Paths

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects. It has applications in computer networks, social networks, biology, and more.

What is a Graph?

A graph $G = (V, E)$ consists of:

$V$: A set of vertices (or nodes)
$E$: A set of edges connecting pairs of vertices

Types of Graphs

Directed vs Undirected

Undirected: Edges have no direction $(u, v) = (v, u)$
Directed: Edges have direction $(u, v) \neq (v, u)$

Weighted vs Unweighted

Unweighted: All edges are equal
Weighted: Each edge has an associated weight/cost

Graph Representations

Adjacency Matrix

An $n \times n$ matrix where $A[i][j] = 1$ if there's an edge from $i$ to $j$.

# For a graph with 4 vertices
adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

Space: $O(V^2)$

Adjacency List

A list where each index contains a list of adjacent vertices.

adj_list = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2]
}

Space: $O(V + E)$

Important Concepts

Degree

The degree of a vertex is the number of edges connected to it.

$$\sum_{v \in V} deg(v) = 2|E|$$

Paths and Cycles

Path: A sequence of vertices connected by edges
Cycle: A path that starts and ends at the same vertex
Simple path: No repeated vertices

Connectivity

A graph is connected if there's a path between every pair of vertices.

Graph Traversals

Breadth-First Search (BFS)

Explores neighbors level by level.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        print(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Time: $O(V + E)$

Depth-First Search (DFS)

Explores as deep as possible before backtracking.

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()

    visited.add(vertex)
    print(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)