Understanding Graphs
A graph data structure is constructed of a set of nodes (also called vertices) connected by edges. Unlike trees, edges don't represent a parent-child relationship between nodes. Instead, they connect nodes to create a neighbor relationship.
Key graph concepts:
- Nodes/Vertices: Individual elements in the graph
- Edges: Connections between nodes
- Neighbors: Nodes that are directly connected by an edge
- Path: A sequence of nodes where each pair of nodes in the sequence are neighbors
- Cycle: A path that starts and ends at the same node
- Connected Graph: A graph where all nodes are connected
- Directed Graph: A graph where edges have direction (one-way connections)
- Weighted Graph: A graph where edges have associated weights (costs, distances, etc.)
Graphs are used in many real-world scenarios like:
- Social networks (people as nodes, connections as edges)
- Road maps (cities as nodes, roads as edges)
- Recommendation systems (products as nodes, relationships as edges)
- Workflow diagrams (process steps as nodes, transitions as edges)
Graph Traversal Algorithms
There are two primary methods for traversing (searching) graphs:
Breadth-First Search (BFS)
BFS explores a graph level by level, visiting all immediate neighbors before moving to the next level. It's useful for finding the shortest path between nodes in an unweighted graph.
BFS uses a queue to keep track of nodes to visit:
// Pseudocode for BFS
function BFS(graph, startNode, targetNode) {
let queue = new Queue();
let visited = new Set();
queue.enqueue(startNode);
while (!queue.isEmpty()) {
let currentNode = queue.dequeue();
if (currentNode === targetNode) {
return true; // Found the target
}
if (!visited.has(currentNode)) {
visited.add(currentNode);
// Add all unvisited neighbors to queue
for (let neighbor of graph.getNeighbors(currentNode)) {
if (!visited.has(neighbor)) {
queue.enqueue(neighbor);
}
}
}
}
return false; // Target not found
}
Depth-First Search (DFS)
DFS explores as far as possible along a branch before backtracking. It's useful for detecting cycles and exploring all possible paths.
DFS uses a stack (or recursion) to track nodes to visit:
// Pseudocode for DFS
function DFS(graph, startNode, targetNode) {
let stack = new Stack();
let visited = new Set();
stack.push(startNode);
while (!stack.isEmpty()) {
let currentNode = stack.pop();
if (currentNode === targetNode) {
return true; // Found the target
}
if (!visited.has(currentNode)) {
visited.add(currentNode);
// Add all unvisited neighbors to stack
for (let neighbor of graph.getNeighbors(currentNode)) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
return false; // Target not found
}
When implementing graphs, there are two common representations:
- Adjacency Matrix: A 2D array where matrix[i][j] indicates if nodes i and j are connected
- Adjacency List: An array of lists where each list contains the neighbors of the corresponding node