Graph Theory Basics

Graphs are everywhere — social networks, road maps, dependency trees. Here are the essentials.

Definitions

A graph G = (V, E) is a set of vertices V connected by edges E.

• Directed: edges have a direction (like Twitter follows)
• Undirected: edges are bidirectional (like Facebook friends)
• Weighted: edges have a cost or distance
• Cyclic / Acyclic: whether loops exist

BFS vs DFS

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    while queue:
        v = queue.popleft()
        if v not in visited:
            visited.add(v)
            queue.extend(graph[v] - visited)
    return visited

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for n in graph[start] - visited:
        dfs(graph, n, visited)
    return visited

BFS finds shortest paths in unweighted graphs. DFS uses less memory for deep graphs.