Graphs

Graphs: Modeling Complex Relationships

A graph is a data structure that models relationships between objects using vertices (nodes) and edges (connections). Unlike hierarchical structures, graphs allow flexible connections between any entities, making them ideal for modeling complex real-world systems.

Key Components:

• Vertices: Data entities or nodes
• Edges: Connections between vertices
• Flexible topology: No required hierarchy or structure

Common Applications:

• Social networks and friend connections
• Transportation and routing systems
• Computer networks and dependencies
• Pathfinding and optimization problems

Graph Structure Overview

graph LR
    A[Vertex A] --- B[Vertex B]
    A --- C[Vertex C]
    B --- D[Vertex D]
    C --- D

    style A fill:#e3f2fd
    style B fill:#c8e6c9
    style C fill:#c8e6c9
    style D fill:#ffecb3

This diagram shows a simple undirected graph with 4 vertices and 4 edges, demonstrating the basic structure of interconnected nodes.

Graph Types and Classifications

graph TD
    A[Graph Types] --> B[Directed]
    A --> C[Undirected]
    A --> D[Weighted]
    A --> E[Unweighted]

    B --> F[One-way connections]
    C --> G[Two-way connections]
    D --> H[Edges have values]
    E --> I[All edges equal]

    style A fill:#e3f2fd
    style B fill:#ffcdd2
    style C fill:#c8e6c9
    style D fill:#fff3e0
    style E fill:#f3e5f5

This diagram categorizes different graph types based on direction and weight properties, helping you choose the right representation for your problem.

Graph Properties and Characteristics

Essential Properties:

• Directed vs Undirected: One-way vs two-way connections
• Weighted vs Unweighted: Edges with/without values
• Connected vs Disconnected: All vertices reachable vs isolated components
• Cyclic vs Acyclic: Contains loops vs no cycles
• Dense vs Sparse: Many vs few edges relative to possible connections

Graph Representation Methods

graph TD
    A[Graph Representation] --> B[Adjacency List]
    A --> C[Adjacency Matrix]

    B --> D["O(V + E) space"]
    B --> E[Good for sparse graphs]
    B --> F[Fast traversal]

    C --> G["O(V²) space"]
    C --> H[Good for dense graphs]
    C --> I[Fast edge queries]

    style A fill:#e3f2fd
    style B fill:#c8e6c9
    style C fill:#ffecb3

This diagram compares the two main graph representation methods, showing their space complexity and optimal use cases.

Graph Traversal Algorithms

graph TD
    A[Graph Traversal] --> B[Breadth-First Search]
    A --> C[Depth-First Search]

    B --> D[Level by level]
    B --> E[Uses Queue]
    B --> F[Finds shortest path]

    C --> G[Deep first, then backtrack]
    C --> H[Uses Stack/Recursion]
    C --> I[Good for pathfinding]

    style A fill:#e3f2fd
    style B fill:#c8e6c9
    style C fill:#ffecb3

This diagram illustrates the two fundamental graph traversal strategies, showing their exploration patterns and optimal use cases.

Adjacency ListAdjacency Matrix

Adjacency List stores a list of neighbors for each vertex. Uses O(V + E) space and is ideal for sparse graphs.

Key Characteristics:

• Memory efficient (only stores actual edges)
• Fast edge addition: O(1)
• Efficient traversal: O(degree)
• Slower edge queries: O(degree)

Example Graph:

Graph: 1—2—4
       |
       3

JavaKotlinTypeScriptDartSwiftPython

import java.util.*;

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(1, 4));
graph.put(3, Arrays.asList(1));
graph.put(4, Arrays.asList(2));

// Add edge helper
public static void addEdge(Map<Integer, List<Integer>> g, int from, int to) {
    g.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
    g.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
}

val graph = mutableMapOf(
    1 to mutableListOf(2, 3),
    2 to mutableListOf(1, 4),
    3 to mutableListOf(1),
    4 to mutableListOf(2)
)

fun addEdge(g: MutableMap<Int, MutableList<Int>>, from: Int, to: Int) {
    g.getOrPut(from) { mutableListOf() }.add(to)
    g.getOrPut(to) { mutableListOf() }.add(from)
}

const graph: Record<number, number[]> = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
};

function addEdge(g: Record<number, number[]>, from: number, to: number): void {
    g[from] = g[from] || [];
    g[to] = g[to] || [];
    g[from].push(to);
    g[to].push(from);
}

void main() {
  final graph = <int, List<int>>{
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2],
  };

  void addEdge(Map<int, List<int>> g, int from, int to) {
    g.putIfAbsent(from, () => []).add(to);
    g.putIfAbsent(to, () => []).add(from);
  }

  print(graph);
}

var graph: [Int: [Int]] = [
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
]

func addEdge(_ g: inout [Int: [Int]], from: Int, to: Int) {
    g[from, default: []].append(to)
    g[to, default: []].append(from)
}

from collections import defaultdict

graph = defaultdict(list)
graph[1] = [2, 3]
graph[2] = [1, 4]
graph[3] = [1]
graph[4] = [2]

def add_edge(g, from_vertex, to_vertex):
    g[from_vertex].append(to_vertex)
    g[to_vertex].append(from_vertex)

Adjacency Matrix uses a 2D array where matrix[i][j] = 1 indicates an edge from vertex i to vertex j. Uses O(V²) space and is ideal for dense graphs.

Key Characteristics:

• Consistent memory usage: O(V²)
• Fast edge queries: O(1)
• Fast edge modification: O(1)
• Slower traversal: O(V)

Example Matrix:

Graph: 1—2—4
       |
       3

Vertices: 1, 2, 3, 4
(Index:   0  1  2  3)

Adjacency Matrix:
    0  1  2  3
0   0  1  1  0   # 1 connected to 2, 3
1   1  0  0  1   # 2 connected to 1, 4
2   1  0  0  0   # 3 connected to 1
3   0  1  0  0   # 4 connected to 2

Note: If your vertex labels start from 1, index 0 refers to vertex 1, index 1 to vertex 2, etc.

JavaKotlinTypeScriptDartSwiftPython

public class GraphMatrix {
    private int[][] matrix;

    public GraphMatrix(int vertices) {
        this.matrix = new int[vertices][vertices];
    }

    public void addEdge(int from, int to) {
        matrix[from][to] = 1;
        matrix[to][from] = 1; // Undirected
    }

    public boolean hasEdge(int from, int to) {
        return matrix[from][to] == 1;
    }
}

class GraphMatrix(vertices: Int) {
    private val matrix = Array(vertices) { IntArray(vertices) }

    fun addEdge(from: Int, to: Int) {
        matrix[from][to] = 1
        matrix[to][from] = 1 // Undirected
    }

    fun hasEdge(from: Int, to: Int): Boolean {
        return matrix[from][to] == 1
    }
}

class GraphMatrix {
    private matrix: number[][];

    constructor(vertices: number) {
        this.matrix = Array.from({ length: vertices }, () => Array(vertices).fill(0));
    }

    addEdge(from: number, to: number): void {
        this.matrix[from][to] = 1;
        this.matrix[to][from] = 1; // Undirected
    }

    hasEdge(from: number, to: number): boolean {
        return this.matrix[from][to] === 1;
    }
}

class GraphMatrix {
  List<List<int>> matrix;

  GraphMatrix(int vertices)
      : matrix = List.generate(vertices, (_) => List.filled(vertices, 0));

  void addEdge(int from, int to) {
    matrix[from][to] = 1;
    matrix[to][from] = 1; // Undirected
  }

  bool hasEdge(int from, int to) {
    return matrix[from][to] == 1;
  }
}

class GraphMatrix {
    private var matrix: [[Int]]

    init(vertices: Int) {
        self.matrix = Array(repeating: Array(repeating: 0, count: vertices), count: vertices)
    }

    func addEdge(from: Int, to: Int) {
        matrix[from][to] = 1
        matrix[to][from] = 1 // Undirected
    }

    func hasEdge(from: Int, to: Int) -> Bool {
        return matrix[from][to] == 1
    }
}

class GraphMatrix:
    def __init__(self, vertices):
        self.matrix = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, from_vertex, to_vertex):
        self.matrix[from_vertex][to_vertex] = 1
        self.matrix[to_vertex][from_vertex] = 1

    def has_edge(self, from_vertex, to_vertex):
        return self.matrix[from_vertex][to_vertex] == 1

Algorithm Complexity Comparison

Operation	Adjacency List	Adjacency Matrix
Add vertex	O(1)	O(V²)
Add edge	O(1)	O(1)
Check edge exists	O(n) (n = number of neighbors of vertex)	O(1)
Get all neighbors	O(n)	O(V)
BFS/DFS traversal	O(V + E)	O(V²)

Note: For adjacency lists, "n" refers to the degree (number of neighbors) of the vertex being examined.

BFS vs DFS Comparison

Aspect	BFS	DFS
Pattern	Level by level	Deep first, then backtrack
Data Structure	Queue (FIFO)	Stack/Recursion (LIFO)
Space	O(V)	O(h) - max depth
Shortest Path	Yes (unweighted)	No guarantee
Best For	Shortest paths, level-order	Pathfinding, cycle detection

Graph Traversal Implementation Examples

Production code typically uses graph libraries that provide optimized traversal algorithms along with additional functionality like shortest path finding and cycle detection. The examples below demonstrate how to perform BFS and DFS using established graph libraries in each language.

JavaKotlinTypeScriptDartSwiftPython

import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;

// Using JGraphT library
Graph<Integer, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

// Add vertices and edges
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addEdge(1, 2);
graph.addEdge(1, 3);

// BFS traversal
BreadthFirstIterator<Integer, DefaultEdge> bfsIterator =
    new BreadthFirstIterator<>(graph, 1);
System.out.print("BFS: ");
while (bfsIterator.hasNext()) {
    System.out.print(bfsIterator.next() + " ");
}

// DFS traversal
DepthFirstIterator<Integer, DefaultEdge> dfsIterator =
    new DepthFirstIterator<>(graph, 1);
System.out.print("\nDFS: ");
while (dfsIterator.hasNext()) {
    System.out.print(dfsIterator.next() + " ");
}

import org.jgrapht.graph.*
import org.jgrapht.traverse.*

// Using JGraphT library (Java interop)
val graph = DefaultDirectedGraph<Int, DefaultEdge>(DefaultEdge::class.java)

// Add vertices and edges
graph.addVertex(1)
graph.addVertex(2)
graph.addVertex(3)
graph.addEdge(1, 2)
graph.addEdge(1, 3)

// BFS traversal
val bfsIterator = BreadthFirstIterator(graph, 1)
print("BFS: ")
bfsIterator.forEach { print("$it ") }

// DFS traversal
val dfsIterator = DepthFirstIterator(graph, 1)
print("\nDFS: ")
dfsIterator.forEach { print("$it ") }

import { DirectedGraph } from 'graphology';
import { bfs, dfs } from 'graphology-traversal';

// Using graphology library
const graph = new DirectedGraph();

// Add vertices and edges
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addEdge(1, 2);
graph.addEdge(1, 3);

// BFS traversal
const bfsResult: number[] = [];
bfs(graph, 1, (node) => bfsResult.push(Number(node)));
console.log('BFS:', bfsResult);

// DFS traversal
const dfsResult: number[] = [];
dfs(graph, 1, (node) => dfsResult.push(Number(node)));
console.log('DFS:', dfsResult);

import 'package:graphs/graphs.dart';

// Using graphs package
void main() {
  // Define graph as adjacency list
  final graph = {
    1: [2, 3],
    2: [4],
    3: [4],
    4: <int>[]
  };

  // BFS traversal
  final bfsResult = breadthFirst<int>(graph, 1).toList();
  print('BFS: $bfsResult');

  // DFS traversal
  final dfsResult = <int>[];
  crawlAsync<int>(graph, 1, (node) {
    dfsResult.add(node);
    return [];
  });
  print('DFS: $dfsResult');
}

import SwiftGraph

// Using SwiftGraph library
let graph = UnweightedGraph<Int>(vertices: [1, 2, 3, 4])

// Add edges
graph.addEdge(from: 1, to: 2, directed: true)
graph.addEdge(from: 1, to: 3, directed: true)
graph.addEdge(from: 2, to: 4, directed: true)
graph.addEdge(from: 3, to: 4, directed: true)

// BFS traversal
let bfsResult = graph.bfs(from: 1)
print("BFS: \(bfsResult)")

// DFS traversal
let dfsResult = graph.dfs(from: 1)
print("DFS: \(dfsResult)")

import networkx as nx

# Using NetworkX library
graph = nx.DiGraph()

# Add vertices and edges
graph.add_nodes_from([1, 2, 3, 4])
graph.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4)])

# BFS traversal
bfs_result = list(nx.bfs_tree(graph, source=1).nodes())
print(f"BFS: {bfs_result}")

# DFS traversal
dfs_result = list(nx.dfs_tree(graph, source=1).nodes())
print(f"DFS: {dfs_result}")

Real-World Applications

• Social Networks: BFS for shortest connection paths, DFS for friend group exploration
• Game Development: BFS for pathfinding, DFS for maze generation
• Dependency Management: DFS for topological sorting in build systems