Graph
Overview
A Graph is an abstract data type used to represent relationships between entities. It consists of a set of vertices (nodes) connected by edges. Graphs are one of the most expressive data structures, capable of modeling networks, paths, and dependencies.
Basic Components
- Vertex (Node): An entity or point
- Edge: A connection between two vertices
- Weight (optional): Cost or value associated with an edge
Graph Representation
Common Models
- Adjacency List: Each vertex stores a list of connected vertices
- Adjacency Matrix: 2D matrix indicating edge presence
- Edge List: Collection of vertex pairs
Types of Graphs
Tree
A connected, acyclic graph with a root and hierarchical structure.
Heap
A specialized tree-based graph satisfying heap properties.
Directed Graph
Edges have direction (A → B).
Undirected Graph
Edges have no direction (A — B).
Weighted Graph
Edges carry weights (distance, cost, time).
Example
Simple Graph
A --- B
| |
C --- D
Common Graph Operations
| Operation | Description |
|---|---|
| Add Vertex | Insert a new node |
| Add Edge | Create a connection |
| Remove Vertex | Delete node and edges |
| Remove Edge | Delete connection |
| Traverse | Visit nodes (BFS, DFS) |
Traversal Techniques
-
Breadth-First Search (BFS)
- Explores level by level
-
Depth-First Search (DFS)
- Explores as deep as possible
Real-world Applications
- Social networks
- Maps and navigation
- Recommendation systems
- Dependency resolution
- Computer networks
Time Complexity
Depends on representation:
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Add Edge | O(1) | O(1) |
| Check Edge | O(V) | O(1) |
| Traverse | O(V + E) | O(V²) |
Advantages
- Extremely flexible
- Models complex relationships
- Powerful algorithm support
Limitations
- Can be memory intensive
- Algorithm complexity can grow quickly