Introduction to Graphs in Python

A graph is a mathematical structure made up of a set of nodes (or vertices) connected to each other by edges. Graphs are used to model networks of any kind: computer networks, road maps, social networks, routing systems.

Definition and components

• Vertices (nodes): represent the “elements” or “points” of the graph. In a computer network, every device is a node.
• Edges (links): represent the connections between nodes. An edge can be:
  • Directed: the connection has a direction (one-way traffic)
  • Undirected: the connection is bidirectional
• Weights: a value assigned to edges to represent costs or distances (latency, transmission cost, physical distance)

Applications

Representation in Python

The most common approach is to use a dictionary with adjacency lists: keys are nodes, values are lists of tuples (adjacent_node, weight).

graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('A', 5), ('C', 2), ('D', 1)],
    'C': [('A', 1), ('B', 2), ('D', 4), ('E', 8)],
    'D': [('B', 1), ('C', 4), ('E', 3), ('F', 6)],
    'E': [('C', 8), ('D', 3)],
    'F': [('D', 6)],
}

def print_graph(graph):
    for node in graph:
        print(f"{node} -> {graph[node]}")

print_graph(graph)

The adjacency list is efficient for sparse graphs: it stores only existing connections, without wasting memory on unconnected pairs.

Traversal algorithms

DFS — Depth-First Search

DFS explores the graph “in depth”: visits a node, then all its descendants, before backtracking.

Pseudocode:

Procedure DFS(graph, node, visited)
    if node not in visited then
        add node to visited
        for each neighbour in graph[node] do
            DFS(graph, neighbour, visited)
    end if
End Procedure

Python implementation:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node not in visited:
        visited.add(node)
        print(node, end=' ')
        for neighbour, weight in graph[node]:
            dfs(graph, neighbour, visited)
    return visited

dfs(graph, 'A')
# Output: A B C D E F

BFS — Breadth-First Search

BFS explores the graph “level by level”: first all nodes at distance 1 from the start node, then those at distance 2, and so on.

Pseudocode:

Procedure BFS(graph, start_node)
    create empty queue Q
    create visited set
    add start_node to Q and to visited

    while Q is not empty do
        node = remove first element from Q
        for each neighbour in graph[node] do
            if neighbour is not in visited then
                add neighbour to Q and to visited
        end for
    end while
End Procedure

Python implementation:

from collections import deque

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

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbour, weight in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

bfs(graph, 'A')
# Output: A B C D E F

Shortest paths

Bellman-Ford Algorithm

Works with negative weights and detects negative-weight cycles.

Pseudocode:

Procedure BellmanFord(graph, source)
    distance[v] = infinity for every node v
    distance[source] = 0

    for i = 1 to number_of_nodes - 1 do
        for each edge (u, v) with weight w do
            if distance[u] + w < distance[v] then
                distance[v] = distance[u] + w

    for each edge (u, v) with weight w do
        if distance[u] + w < distance[v] then
            report "negative weight cycle"

    return distance
End Procedure

• Complexity: O(V × E) where V = nodes, E = edges
• After V-1 iterations, distances are guaranteed correct
• The final iteration detects negative cycles

Dijkstra’s Algorithm

Optimal for graphs with non-negative weights. Uses a priority queue to always process the node with the smallest distance.

Pseudocode:

Procedure Dijkstra(graph, source)
    distance[v] = infinity for every node v
    distance[source] = 0
    create priority queue Q with (source, 0)

    while Q is not empty do
        (u, dist_u) = extract node with minimum distance from Q
        for each neighbour v of u with weight w do
            if distance[u] + w < distance[v] then
                distance[v] = distance[u] + w
                insert or update (v, distance[v]) in Q

    return distance
End Procedure

Python implementation:

import heapq

def dijkstra(graph, source):
    distance = {node: float('inf') for node in graph}
    distance[source] = 0
    queue = [(0, source)]  # (distance, node)

    while queue:
        dist_u, u = heapq.heappop(queue)
        if dist_u > distance[u]:
            continue
        for v, weight in graph[u]:
            new_dist = distance[u] + weight
            if new_dist < distance[v]:
                distance[v] = new_dist
                heapq.heappush(queue, (new_dist, v))

    return distance

distances = dijkstra(graph, 'A')
for node, dist in distances.items():
    print(f"A → {node}: {dist}")

Visualisation with NetworkX

pip install networkx matplotlib

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()

edges = [
    ('A', 'B', 5), ('A', 'C', 1),
    ('B', 'C', 2), ('B', 'D', 1),
    ('C', 'D', 4), ('C', 'E', 8),
    ('D', 'E', 3), ('D', 'F', 6),
]

for u, v, w in edges:
    G.add_edge(u, v, weight=w)

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True,
        node_color='lightblue', edge_color='gray', node_size=500)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

plt.title("Weighted graph with NetworkX")
plt.show()

NetworkX also includes ready-made algorithm implementations:

# Dijkstra with NetworkX
path     = nx.shortest_path(G, source='A', target='F', weight='weight')
distance = nx.shortest_path_length(G, source='A', target='F', weight='weight')
print(f"Path: {' → '.join(path)}, cost: {distance}")

Connection to network routing

Graphs underlie routing protocols:

In OSPF, each router builds a graph of the entire network (LSDB — Link State Database) and applies Dijkstra to calculate optimal paths to all destinations.