Graph Foundations

Graph Foundations

What is a Graph?

A graph G = (V, E) consists of:

• V: Set of vertices (nodes)
• E: Set of edges (connections between vertices)

Graph Types

Directed vs Undirected

Undirected Graph: Edges have no direction

• Edge (u, v) is the same as (v, u)
• Example: Social networks, road networks

Directed Graph (Digraph): Edges have direction

• Edge (u, v) is different from (v, u)
• Example: Web links, dependencies

Weighted vs Unweighted

Unweighted: All edges have equal weight (usually 1)

Weighted: Edges have associated weights/costs

Graph Terminology

• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at the same vertex
• Connected: Path exists between any two vertices
• Tree: Connected graph with no cycles (n-1 edges for n vertices)
• Forest: Collection of trees
• Degree: Number of edges incident to a vertex
• In-degree: Incoming edges (directed graphs)
• Out-degree: Outgoing edges (directed graphs)

Graph Representations

1. Adjacency List

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1):
        self.adj_list[u].append((v, weight))
        # For undirected: self.adj_list[v].append((u, weight))
    
    def get_neighbors(self, u):
        return self.adj_list[u]

Space: O(V + E)

Check edge: O(degree)

List neighbors: O(degree)

2. Adjacency Matrix

class GraphMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        # For undirected: self.matrix[v][u] = weight
    
    def has_edge(self, u, v):
        return self.matrix[u][v] != 0

Space: O(V²)

Check edge: O(1)

List neighbors: O(V)

3. Edge List

class GraphEdgeList:
    def __init__(self):
        self.edges = []
        self.vertices = set()
    
    def add_edge(self, u, v, weight=1):
        self.edges.append((u, v, weight))
        self.vertices.add(u)
        self.vertices.add(v)

Space: O(E)

Check edge: O(E)

List neighbors: O(E)

When to Use Which?

• Adjacency List: Sparse graphs, most graph algorithms
• Adjacency Matrix: Dense graphs, frequent edge queries
• Edge List: Kruskal's algorithm, edge-based operations

Practice Problems

1. Implement all three representations
2. Convert between representations
3. Count vertices and edges
4. Check if graph is connected
5. Find all isolated vertices