Graphs
A Graph is a non-linear data structure consisting of vertices (nodes) and edges (connections). Graphs can represent any relationship between objects.
Graph Terminology
| Term | Definition |
|---|---|
| Vertex (Node) | A point in the graph |
| Edge | Connection between two vertices |
| Directed | Edges have direction (one-way) |
| Undirected | Edges are bidirectional |
| Weighted | Edges have values (costs, distances) |
| Path | Sequence of vertices connected by edges |
| Cycle | Path that starts and ends at same vertex |
| Degree | Number of edges connected to a vertex |
Types of Graphs
Undirected Directed Weighted
A---B AāāāB A--5--B
| | ā ā | |
D---C DāāāC 3 2
| |
D--4--CGraph Representation
1. Adjacency List (Most Common)
Each vertex stores a list of its neighbors.
const graph = {
'A': ['B', 'D'],
'B': ['A', 'C', 'E'],
'C': ['B', 'F'],
'D': ['A', 'E'],
'E': ['B', 'D', 'F'],
'F': ['C', 'E']
};2. Adjacency Matrix
2D array where matrix[i][j] = 1 if edge exists.
// A B C D
// A [ 0, 1, 0, 1 ]
// B [ 1, 0, 1, 0 ]
// C [ 0, 1, 0, 1 ]
// D [ 1, 0, 1, 0 ]
const matrix = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
];Graph Traversals
Breadth-First Search (BFS)
Explores level by level using a queue.
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length > 0) {
const vertex = queue.shift();
result.push(vertex);
for (const neighbor of graph[vertex]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}
// bfs(graph, 'A') ā ['A', 'B', 'D', 'C', 'E', 'F']Depth-First Search (DFS)
Goes as deep as possible using a stack (or recursion).
function dfs(graph, start) {
const visited = new Set();
const result = [];
function explore(vertex) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph[vertex]) {
if (!visited.has(neighbor)) {
explore(neighbor);
}
}
}
explore(start);
return result;
}
// dfs(graph, 'A') ā ['A', 'B', 'C', 'F', 'E', 'D']BFS vs DFS
| Aspect | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack/Recursion |
| Approach | Level by level | Go deep first |
| Shortest Path | Yes (unweighted) | No |
| Memory | O(V) worst | O(V) worst |
| Use Case | Shortest path | Cycle detection |
Complexity
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Add Vertex | O(1) | O(VĀ²) |
| Add Edge | O(1) | O(1) |
| Remove Edge | O(E) | O(1) |
| Query Edge | O(V) | O(1) |
| BFS/DFS | O(V + E) | O(VĀ²) |
| Space | O(V + E) | O(VĀ²) |
Common Graph Algorithms
| Algorithm | Purpose |
|---|---|
| Dijkstra's | Shortest path (weighted) |
| Bellman-Ford | Shortest path (negative weights) |
| Kruskal's/Prim's | Minimum spanning tree |
| Topological Sort | Order dependencies |
| Floyd-Warshall | All pairs shortest path |
Real-World Applications
- Social Networks ā Friends, followers, connections
- Maps & Navigation ā Roads, shortest routes
- Web Crawling ā Pages linked to other pages
- Recommendation Systems ā Product relationships
- Dependency Resolution ā Package managers, build systems
What's Next?
Congratulations! You've completed the core data structures. The final lesson is a comprehensive quiz to test your understanding of everything you've learned.