Python - Data Structures - Graphs

Data Structures - Graphs in Python

Introduction to Graphs

Graphs are one of the most powerful and flexible data structures used in computer science. They model relationships and connections among a set of entities, making them suitable for representing a wide range of real-world systems such as social networks, transportation grids, web pages, and much more.

A graph is composed of two main components:

• Vertices (Nodes): These represent entities or data points.
• Edges (Links): These represent connections or relationships between pairs of nodes.

Types of Graphs

• Directed Graph (Digraph): Edges have a direction from one vertex to another.
• Undirected Graph: Edges have no direction; the relationship is bidirectional.
• Weighted Graph: Edges carry weights (numerical values), often representing cost, distance, or time.
• Unweighted Graph: Edges do not carry weights.
• Cyclic Graph: Contains at least one cycle (a path from a node back to itself).
• Acyclic Graph: No cycles are present.

Graph Representations in Python

Graphs can be represented in multiple ways in Python. The most common representations are:

1. Adjacency List

This representation uses a dictionary where keys are nodes and values are lists of adjacent nodes.

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': ['F'],
    'E': [],
    'F': []
}

2. Adjacency Matrix

A 2D array (matrix) is used where a cell [i][j] is marked if there is an edge from node i to j.

# For graph with 4 nodes: A, B, C, D
adj_matrix = [
    [0, 1, 1, 0],  # A
    [0, 0, 0, 1],  # B
    [0, 0, 0, 1],  # C
    [0, 0, 0, 0]   # D
]

3. Edge List

This representation uses a list of edges represented as tuples or lists of pairs.

edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('C', 'E'),
    ('D', 'F')
]

Creating a Graph Class in Python

To encapsulate graph operations, it's often useful to create a class:

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

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

Graph Traversal Algorithms

1. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (can be recursive).

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

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

2. Breadth-First Search (BFS)

BFS explores all neighbors of a node before moving to the next level. It uses a queue.

from collections import deque

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

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph.get(node, []))

Cycle Detection in Graphs

1. In Undirected Graph

def has_cycle_undirected(graph, node, visited, parent):
    visited.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle_undirected(graph, neighbor, visited, node):
                return True
        elif neighbor != parent:
            return True
    return False

2. In Directed Graph

def has_cycle_directed(graph):
    visited = set()
    rec_stack = set()

    def visit(node):
        if node in rec_stack:
            return True
        if node in visited:
            return False

        visited.add(node)
        rec_stack.add(node)

        for neighbor in graph.get(node, []):
            if visit(neighbor):
                return True
        rec_stack.remove(node)
        return False

    for node in graph:
        if visit(node):
            return True
    return False

Topological Sorting (Directed Acyclic Graphs)

Topological sort gives a linear ordering of vertices such that for every directed edge u → v, u comes before v.

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        if node not in visited:
            visited.add(node)
            for neighbor in graph.get(node, []):
                dfs(neighbor)
            stack.append(node)

    for node in graph:
        dfs(node)

    return stack[::-1]

Dijkstra's Algorithm (Shortest Path)

Used to find the shortest path in a weighted graph from a source node to all other nodes.

import heapq

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

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

Graph Libraries in Python

1. NetworkX

NetworkX is a popular Python library for creating, manipulating, and studying the structure of graphs.

import networkx as nx

G = nx.DiGraph()
G.add_edge("A", "B")
G.add_edge("B", "C")

print(list(G.nodes))
print(list(G.edges))

# Visualizing
import matplotlib.pyplot as plt
nx.draw(G, with_labels=True)
plt.show()

Applications of Graphs

• Modeling networks (social, transport, electrical).
• Pathfinding algorithms (GPS navigation).
• Web crawling (Google PageRank).
• Dependency resolution (e.g., package managers).
• Job scheduling using topological sort.

Graph Interview Questions

1. Find Connected Components

def connected_components(graph):
    visited = set()
    components = []

    def dfs(node, comp):
        visited.add(node)
        comp.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor, comp)

    for node in graph:
        if node not in visited:
            comp = []
            dfs(node, comp)
            components.append(comp)
    return components

2. Clone a Graph

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

def clone_graph(node, visited=None):
    if not node:
        return None
    if visited is None:
        visited = {}
    if node in visited:
        return visited[node]

    clone = Node(node.val)
    visited[node] = clone

    for neighbor in node.neighbors:
        clone.neighbors.append(clone_graph(neighbor, visited))
    return clone

Graphs are indispensable in the field of computer science, with applications ranging from web search engines to social networks. Understanding how to represent, traverse, and analyze graphs is essential for writing efficient algorithms and solving complex problems. Whether you're using built-in data structures or external libraries like NetworkX, Python offers extensive tools to work with graphs effectively.