Graphs Overview
This section contains documentation for graph data structures and their implementations.
Available Graph Implementations
Core Interface
- Graph Interface: Abstract base class defining the common API for all graph implementations
Graph Representations
- Adjacency List Graph: Memory-efficient graph using adjacency lists
- Adjacency Matrix Graph: Fast edge lookup graph using adjacency matrix
- Graph Node: Basic graph node implementation for simple use cases
Graph Types Supported
Both graph implementations support:
- Directed graphs: Edges have direction (A → B is different from B → A)
- Undirected graphs: Edges are bidirectional (A ↔ B)
- Weighted edges: Each edge can have an associated weight/cost
Common Operations
All graph implementations provide:
Basic Operations
- Add/remove vertices and edges
- Check for edge existence
- Get edge weights
- Retrieve neighbors of a vertex
Graph Analysis
- Vertex and edge counting
- Degree calculations (in-degree, out-degree)
- Connectivity checking
- Cycle detection
- Topological sorting (for directed acyclic graphs)
Graph Traversal
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
Performance Comparison
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Add Vertex | O(1) | O(1)* |
| Add Edge | O(1) | O(1) |
| Remove Vertex | O(V + E) | O(V²) |
| Remove Edge | O(V) | O(1) |
| Check Edge | O(V) | O(1) |
| Get Neighbors | O(1) | O(V) |
| Space | O(V + E) | O(V²) |
*Adjacency Matrix has a fixed maximum vertex limit