Algorithms
  • Understand what graphs are and their real-world applications
  • Learn different ways to represent graphs in memory
  • Compare adjacency matrix vs adjacency list representations
  • Identify graph types and their properties

Introduction to Graphs and Graph Representations

The Web of Connections: Understanding Graph Theory

Imagine you're trying to map out a city's transportation network, or model how information spreads through social media, or represent the dependencies in a complex software project. All of these scenarios involve relationships between entities, and graphs provide the perfect mathematical framework to model and analyze such interconnected systems.

Graphs are fundamental data structures that capture relationships between objects, forming the backbone of many algorithms in computer science, from network routing to social network analysis.

What is a Graph?

The Basic Building Blocks

A graph G consists of two main components:

  • Vertices (Nodes): The entities being modeled
  • Edges: The connections or relationships between vertices

Example: In a social network, people are vertices and friendships are edges.

Graph Terminology

  • Degree: Number of edges connected to a vertex
  • Path: Sequence of vertices connected by edges
  • Cycle: Path that starts and ends at the same vertex
  • Connected Component: Group of vertices reachable from each other

Types of Graphs

Directed vs Undirected Graphs

Directed Graphs (Digraphs):

  • Edges have direction (one-way relationships)
  • Represented as ordered pairs (u,v)
  • Used for: Web page links, task dependencies, one-way streets
A → B → C
↑     ↓
D ← E ← F

Undirected Graphs:

  • Edges are bidirectional (two-way relationships)
  • Represented as unordered pairs {u,v}
  • Used for: Social networks, road networks, molecular structures
A — B — C
│   │   │
D — E — F

Weighted vs Unweighted Graphs

Weighted Graphs:

  • Edges have associated costs/weights
  • Used for: Distance, time, capacity, cost
  • Example: Road network with distances

Unweighted Graphs:

  • All edges are equal
  • Used for: Simple connectivity, reachability
  • Example: Friendship network

Graph Representations in Memory

Adjacency Matrix

A 2D array where matrix[i][j] represents the edge between vertices i and j.

Characteristics:

  • Space Complexity: O(V²) - always uses full matrix
  • Time Complexity:
    • Edge existence: O(1)
    • Finding neighbors: O(V)
    • Memory usage: High for sparse graphs

When to Use:

  • Dense graphs (many edges)
  • Need fast edge existence checks
  • Small number of vertices
// Adjacency Matrix for undirected graph
boolean[][] adjMatrix = new boolean[V][V];

// Add edge between u and v
adjMatrix[u][v] = true;
adjMatrix[v][u] = true; // For undirected

Adjacency List

An array of lists where each list contains neighbors of a vertex.

Characteristics:

  • Space Complexity: O(V + E) - only stores existing edges
  • Time Complexity:
    • Edge existence: O(degree of vertex)
    • Finding neighbors: O(degree of vertex)
    • Memory usage: Efficient for sparse graphs

When to Use:

  • Sparse graphs (few edges)
  • Need to iterate through neighbors frequently
  • Large number of vertices
// Adjacency List for undirected graph
List<Integer>[] adjList = new ArrayList[V];

// Add edge between u and v
adjList[u].add(v);
adjList[v].add(u); // For undirected

Comparing Representations

Aspect Adjacency Matrix Adjacency List
Space O(V²) O(V + E)
Edge Check O(1) O(degree)
Iterate Neighbors O(V) O(degree)
Add Edge O(1) O(1)
Best For Dense graphs Sparse graphs

Real-World Applications

Social Networks

  • Facebook Graph: Users as vertices, friendships as edges
  • Twitter Network: Users and follower relationships
  • LinkedIn: Professional connections and endorsements

Transportation Networks

  • Road Networks: Intersections as vertices, roads as edges
  • Flight Networks: Airports as vertices, flights as edges
  • Railway Systems: Stations connected by tracks

Computer Networks

  • Internet: Routers and servers as vertices, connections as edges
  • Local Networks: Computers and network devices
  • Web Graph: Web pages as vertices, hyperlinks as edges

Software Engineering

  • Dependency Graphs: Software modules and their dependencies
  • Call Graphs: Functions and their calling relationships
  • Control Flow Graphs: Program statements and execution flow

Biological Networks

  • Protein Interaction Networks: Proteins and their interactions
  • Neural Networks: Neurons and synaptic connections
  • Gene Regulatory Networks: Genes and regulatory relationships

Graph Properties and Classifications

Connectivity

  • Connected Graph: Path exists between every pair of vertices
  • Disconnected Graph: Multiple connected components
  • Strongly Connected: Every vertex reachable from every other (directed)
  • Weakly Connected: Underlying undirected graph is connected

Cycles

  • Acyclic Graph: No cycles (trees are acyclic connected graphs)
  • Cyclic Graph: Contains at least one cycle
  • Directed Acyclic Graph (DAG): Directed graph with no cycles

Special Graph Types

  • Tree: Acyclic connected graph
  • Complete Graph: Every pair of vertices connected
  • Bipartite Graph: Vertices divided into two sets, edges only between sets
  • Planar Graph: Can be drawn without edge crossings

Choosing the Right Representation

For Dense Graphs (E ≈ V²)

  • Use adjacency matrix
  • Fast edge lookups
  • Suitable for: Complete graphs, dense networks

For Sparse Graphs (E << V²)

  • Use adjacency list
  • Memory efficient
  • Suitable for: Social networks, web graphs, sparse networks

For Dynamic Graphs

  • Adjacency list: Easy to add/remove edges
  • Adjacency matrix: Expensive modifications

For Algorithm-Specific Needs

  • BFS/DFS: Both representations work, list often preferred
  • Shortest Paths: Matrix for dense, list for sparse
  • Minimum Spanning Tree: List representation usually better

Common Graph Problems

Traversal Problems

  • Visit all vertices in systematic order
  • Find connected components
  • Detect cycles

Path Finding Problems

  • Shortest path between two vertices
  • All-pairs shortest paths
  • Minimum spanning tree

Matching Problems

  • Maximum matching in bipartite graphs
  • Assignment problems
  • Network flow problems

Key Takeaways

  1. Graphs model relationships between entities using vertices and edges
  2. Choose representation wisely: Matrix for dense graphs, list for sparse graphs
  3. Understand graph types: Directed/undirected, weighted/unweighted, cyclic/acyclic
  4. Real-world applications span social networks, transportation, biology, and computing

Graphs provide a universal language for modeling complex relationships and interconnections. Mastering graph representations and properties forms the foundation for understanding advanced graph algorithms that solve real-world problems in computer science and beyond.