Project 8: Graph Algorithms Visualizer

Build a graph library and visualize BFS, DFS, Dijkstra, and topological sort.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 2 weeks
Language C (Alternatives: Rust, Python)
Prerequisites Projects 1-7
Key Topics Graph modeling, traversals, shortest paths, DAGs

1. Learning Objectives

By completing this project, you will:

  1. Implement graphs with adjacency lists and matrices.
  2. Build BFS and DFS traversals with visualization.
  3. Implement Dijkstra’s algorithm using a priority queue.
  4. Perform topological sort on DAGs.

2. Theoretical Foundation

2.1 Core Concepts

  • Vertices and edges: Model relationships between entities.
  • Adjacency list vs matrix: Sparse vs dense trade-offs.
  • BFS vs DFS: Level-order vs depth exploration.
  • Shortest paths: Dijkstra finds shortest weighted paths with non-negative edges.
  • DAGs: Topological order resolves dependencies.

2.2 Why This Matters

Graphs represent networks, maps, dependency systems, and social structures. They are central in CS and real-world problem solving.

2.3 Historical Context / Background

Graph theory dates to Euler’s bridges problem (1736) and has since become a foundational mathematical language for networks.

2.4 Common Misconceptions

  • “DFS finds shortest path”: Only BFS guarantees shortest in unweighted graphs.
  • “Adjacency matrix is always better”: It wastes memory for sparse graphs.

3. Project Specification

3.1 What You Will Build

  • A graph representation supporting directed/undirected edges.
  • BFS and DFS traversal visualizer.
  • Dijkstra’s shortest path implementation.
  • Topological sort for DAGs.

3.2 Functional Requirements

  1. Create graphs with weighted edges.
  2. Traverse graph with BFS/DFS from any node.
  3. Compute shortest paths with Dijkstra.
  4. Output topological order for DAG input.

3.3 Non-Functional Requirements

  • Performance: O(V+E) for BFS/DFS.
  • Reliability: Detect invalid nodes and cycles for DAGs.
  • Usability: Visual output of traversal order and distances.

3.4 Example Usage / Output

$ ./graph_demo
BFS from 0: 0 1 2 3 4
DFS from 0: 0 2 4 3 1
Shortest path 0 -> 4: 7 (0-2-4)
Topological order: 5 2 3 1 0 4

3.5 Real World Outcome

You run the demo with a sample graph file. The program prints traversal order with timestamps, shows shortest paths with distances, and prints a topological build order for dependency graphs. You can toggle adjacency list vs matrix and see different memory usage reported.

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐     ┌──────────────────┐     ┌────────────────┐
│ Graph Core   │────▶│ Algorithms       │────▶│ Visualizer     │
└──────────────┘     └──────────────────┘     └────────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Graph struct Store vertices/edges List vs matrix
Traversals BFS/DFS Queue vs recursion
Shortest path Dijkstra Min-heap or linear scan
Visualizer Print paths ASCII traces

4.3 Data Structures

typedef struct Edge {
    int dest;
    int weight;
    struct Edge* next;
} Edge;

typedef struct {
    Edge** adj;
    int num_vertices;
    int directed;
} Graph;

4.4 Algorithm Overview

Key Algorithm: BFS

  1. Push start node into queue.
  2. Pop node, visit neighbors, enqueue unvisited.
  3. Track distance and parent for path reconstruction.

Complexity Analysis:

  • Time: O(V + E) BFS/DFS, O(E log V) for Dijkstra with heap
  • Space: O(V + E)

5. Implementation Guide

5.1 Development Environment Setup

clang -Wall -Wextra -g -o graph_demo src/*.c

5.2 Project Structure

project-root/
├── src/
│   ├── graph.c
│   ├── bfs.c
│   ├── dfs.c
│   ├── dijkstra.c
│   ├── topo.c
│   └── main.c
├── tests/
│   └── test_graph.c
└── Makefile

5.3 The Core Question You’re Answering

“How do I model relationships and then traverse or optimize across them?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Graph representations
  2. Queue and stack usage in traversal
  3. Priority queues for Dijkstra

5.5 Questions to Guide Your Design

  1. Will you store weights in edges or a separate map?
  2. How will you print path reconstruction?
  3. How will you handle disconnected graphs?

5.6 Thinking Exercise

Given a graph of 6 nodes, run BFS by hand from node 0 and record distances. Then run DFS and compare orders.

5.7 The Interview Questions They’ll Ask

  1. “When do you use BFS vs DFS?”
  2. “Why does Dijkstra fail with negative edges?”
  3. “How do you detect cycles in a directed graph?”

5.8 Hints in Layers

Hint 1: Start with adjacency list It is easiest for traversal and memory efficient.

Hint 2: Add parent arrays They make path reconstruction simple.

5.9 Books That Will Help

Topic Book Chapter
Graphs CLRS Ch. 22-24
Algorithms Algorithms, 4th Edition Graphs section

5.10 Implementation Phases

Phase 1: Foundation (4 days)

Goals:

  • Graph core and traversal

Tasks:

  1. Build adjacency list graph.
  2. Implement BFS/DFS.

Checkpoint: Traversals output expected orders.

Phase 2: Core Functionality (5 days)

Goals:

  • Dijkstra and topological sort

Tasks:

  1. Implement priority queue usage in Dijkstra.
  2. Implement Kahn’s algorithm for topo sort.

Checkpoint: Shortest paths and topo order correct on test graphs.

Phase 3: Polish & Edge Cases (3 days)

Goals:

  • Visualization and file input

Tasks:

  1. Load graph from text file.
  2. Print traversal and distance tables.

Checkpoint: Graph file loads and visual output matches expectations.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Graph storage List, matrix List Efficient for sparse graphs
Dijkstra PQ Binary heap, array Binary heap O(E log V)

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Edge insertion undirected edges
Integration Tests BFS/DFS known graphs
Edge Case Tests Disconnected graph unreachable nodes

6.2 Critical Test Cases

  1. Graph with two components: BFS marks unreachable as -1.
  2. Dijkstra with weights > 0 returns expected distances.
  3. Topo sort detects cycles.

6.3 Test Data

Edges:
0-1(1), 0-2(4), 1-2(2), 2-3(1)

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Forgetting to mark visited Infinite loops Track visited array
Using DFS for shortest paths Wrong distances Use BFS/Dijkstra
Wrong adjacency wiring Missing edges Verify add_edge logic

7.2 Debugging Strategies

  • Print adjacency lists per node.
  • Trace queue contents during BFS.

7.3 Performance Traps

  • Using adjacency matrices for sparse graphs wastes memory.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add undirected/directed toggle.
  • Add BFS tree reconstruction output.

8.2 Intermediate Extensions

  • Implement Bellman-Ford for negative weights.
  • Add connected components detection.

8.3 Advanced Extensions

  • Implement A* pathfinding with heuristics.
  • Add graph visualization export (DOT).

9. Real-World Connections

9.1 Industry Applications

  • Maps: routing and navigation.
  • Build systems: dependency resolution.
  • NetworkX: graph algorithms library.
  • Neo4j: graph database.

9.3 Interview Relevance

  • BFS/DFS and shortest paths appear frequently in interviews.

10. Resources

10.1 Essential Reading

  • CLRS - Ch. 22-24
  • Algorithms, 4th Edition - graphs

10.2 Video Resources

  • “Graph Algorithms” - university lectures

10.3 Tools & Documentation

  • Graphviz: https://graphviz.org/

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain adjacency list vs matrix.
  • I can compare BFS/DFS.
  • I can explain Dijkstra’s constraints.

11.2 Implementation

  • Traversals and shortest paths pass tests.
  • Topo sort detects cycles.

11.3 Growth

  • I can add a new algorithm to the graph library.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Graph representation plus BFS/DFS.

Full Completion:

  • Dijkstra and topological sort.

Excellence (Going Above & Beyond):

  • A* or DOT visualization export.

This guide was generated from DATA_STRUCTURES_FROM_FIRST_PRINCIPLES.md. For the complete learning path, see the parent directory README.