Graphs in Python

Vertex (Node)

A vertex represents an entity in the graph (like a person in a social network).

Edge

An edge connects two vertices and represents a relationship.

Directed vs Undirected Graph

• Undirected: edge goes both ways (A — B)
• Directed: edge has direction (A → B)

Example:

• Instagram follow: directed
• Facebook friendship: undirected

Weighted vs Unweighted Graph

• Unweighted: all edges have equal cost
• Weighted: edges have weights (distance, time, cost)

Example:

• Map roads with distance → weighted graph

Degree

• Degree (undirected): number of edges connected to a node
• In-degree (directed): edges coming into node
• Out-degree (directed): edges leaving node

Path

A path is a sequence of vertices connected by edges.

Cycle

A cycle occurs when you can start at a node and return to it by following edges.

Graphs can be stored in different ways. The best choice depends on how dense the graph is and what operations you need.

Adjacency Matrix

A 2D matrix where:

• matrix[u][v] = 1 (or weight) if edge exists
• otherwise 0 (or infinity)

Example:

# 4 nodes: 0,1,2,3
matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

Pros:

• Very fast edge lookup O(1)

Cons:

• Uses O(V^2) memory (bad for large sparse graphs)

Adjacency List (Most common)

Store for each node: list of its neighbors.

Example:

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

Pros:

• Memory efficient for sparse graphs: O(V + E)
• Great for traversals (BFS/DFS)

Cons:

• Edge lookup can be slower than matrix

Using a Dictionary (Adjacency List)

from collections import defaultdict

graph = defaultdict(list)

# Add edges (undirected example)
graph[0].append(1)
graph[1].append(0)

graph[0].append(2)
graph[2].append(0)

Weighted Graph (Adjacency List)

Store pairs: (neighbor, weight)

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("D", 5)],
    "C": [("A", 2), ("D", 1)],
    "D": [("B", 5), ("C", 1)]
}

Traversal means visiting all reachable nodes in a structured way.

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking.

Use cases:

• Cycle detection
• Topological sorting
• Connected components
• Maze solving

DFS (Recursive)

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

    visited.add(start)
    print(start, end=" ")

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

DFS (Iterative using Stack)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

Time complexity: O(V + E)

Breadth-First Search (BFS)

BFS explores level by level using a queue.

Use cases:

• Shortest path in unweighted graphs
• Level order traversal
• Finding minimum edges between nodes

BFS Implementation

from collections import deque

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

    while q:
        node = q.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)

Time complexity: O(V + E)

Shortest path algorithms find the minimum distance between nodes in weighted graphs.

Dijkstra’s Algorithm

Dijkstra finds shortest path from a source node to all others when all weights are non-negative.

Core idea:

• Always expand the node with the smallest known distance
• Use a min-heap (priority queue)

Dijkstra Implementation (Using heapq)

import heapq

def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0

    pq = [(0, start)]  # (distance, node)

    while pq:
        current_dist, node = heapq.heappop(pq)

        if current_dist > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

Time complexity: O((V + E) log V)

When not to use: If graph has negative edges.

Bellman-Ford Algorithm

Bellman-Ford works even if there are negative weights and can detect negative cycles.

Core idea:
Relax all edges V-1 times.

Bellman-Ford Implementation

def bellman_ford(vertices, edges, start):
    dist = {v: float("inf") for v in vertices}
    dist[start] = 0

    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Detect negative cycle
    for u, v, w in edges:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            raise ValueError("Graph contains a negative weight cycle")

    return dist

Time complexity: O(V * E)

• Networking: routing packets between routers
• Social networks: friend/follow relationships
• Maps: shortest route between locations
• Dependencies: build systems, course prerequisites
• Recommendation systems: graph-based suggestions

Graphs represent relationships and power many real-world systems. Adjacency lists are most common in Python. BFS and DFS are fundamental traversals, while Dijkstra and Bellman-Ford solve shortest path problems under different weight constraints.