Graphs

Overview

A graph is a data structure used to model relationships between objects. It consists of nodes (also called vertices) and edges (connections between nodes). Graphs are widely used in various fields, such as networking (e.g., the Internet), social networks, and pathfinding algorithms in maps.

Graphs can be:

• Directed: Edges have a direction (A → B).
• Undirected: Edges have no direction (A ↔ B).
• Weighted: Edges have weights (values) representing costs, distances, or capacities.
• Unweighted: Edges have no weights.

Graph Representation

Adjacency Matrix:

• A 2D array where matrix[i][j] indicates whether there is an edge from node i to node j.
• In weighted graphs, the value at matrix[i][j] is the weight of the edge.

0 1 1
1 0 0
1 0 0

Adjacency List:

• A list where each node has a sublist of its neighbors.
• More memory-efficient for sparse graphs.

0: [1, 2]
1: [0]
2: [0]

Graph Traversal

Two primary traversal methods:

Depth-First Search (DFS):

• Explore as far down one branch as possible before backtracking.
• Implemented using recursion or a stack.

Breadth-First Search (BFS):

• Explores all neighbours at the current depth before moving deeper.
• Implemented using a queue.

Implementing Graphs

Using Arrays (Procedural Approach)

Adjacency Matrix

# Create a graph with 3 nodes using an adjacency matrix
graph = [
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
]

def add_edge(matrix, u, v):
    matrix[u][v] = 1
    matrix[v][u] = 1  # For undirected graphs

def remove_edge(matrix, u, v):
    matrix[u][v] = 0
    matrix[v][u] = 0  # For undirected graphs

def traverse_matrix(matrix):
    for i, row in enumerate(matrix):
        print(f"Node {i} is connected to: {', '.join(str(j) for j in range(len(row)) if row[j] == 1)}")

Adjacency List

# Graph using an adjacency list
graph = {
    0: [1, 2],
    1: [0],
    2: [0]
}

def add_edge(adj_list, u, v):
    adj_list[u].append(v)
    adj_list[v].append(u)  # For undirected graphs

def remove_edge(adj_list, u, v):
    adj_list[u].remove(v)
    adj_list[v].remove(u)

def traverse_list(adj_list):
    for node in adj_list:
        print(f"Node {node} is connected to: {adj_list[node]}")

Using Object-Oriented Programming (OOP)

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

    def add_node(self, node):
        if node not in self.adj_list:
            self.adj_list[node] = []

    def add_edge(self, u, v):
        if u in self.adj_list and v in self.adj_list:
            self.adj_list[u].append(v)
            self.adj_list[v].append(u)  # For undirected graphs

    def remove_edge(self, u, v):
        if u in self.adj_list and v in self.adj_list:
            self.adj_list[u].remove(v)
            self.adj_list[v].remove(u)

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=" ")
        for neighbor in self.adj_list[start]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

    def bfs(self, start):
        visited = set()
        queue = [start]
        visited.add(start)
        while queue:
            current = queue.pop(0)
            print(current, end=" ")
            for neighbor in self.adj_list[current]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

Examples

g = Graph()
g.add_node(0)
g.add_node(1)
g.add_node(2)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.dfs(0)  # Output: 0 1 2

g.bfs(0)  # Output: 0 1 2

Note Summary