In the grand tapestry of data structures, graphs stand out as particularly versatile and powerful. Think of them as abstract representations of connections. Anywhere you find entities linked by relationships, you're likely dealing with a graph, whether you realize it or not. From social networks where people are nodes and friendships are edges, to road maps with cities as nodes and roads as edges, graphs provide a fundamental way to model and analyze complex systems.
At their core, graphs consist of two main components: vertices (or nodes) and edges. Vertices represent the individual entities or points in our network, while edges represent the relationships or connections between these vertices. These connections can be directional (a one-way street) or non-directional (a two-way street). They can also have associated weights, signifying things like distance, cost, or capacity.
graph TD; A[Vertex A] --> B[Vertex B]; B --> C[Vertex C]; A --> C;
Graphs can be broadly categorized into two types: directed graphs and undirected graphs. In an undirected graph, edges have no direction, meaning if there's an edge between vertex A and vertex B, you can traverse from A to B and from B to A. In contrast, a directed graph has edges with a specific direction, often represented by arrows. If there's a directed edge from A to B, it doesn't necessarily mean you can go from B to A.
graph TD; A --> B; B --> C; C --> A;
Representing graphs computationally is key to working with them. Two common methods are adjacency matrices and adjacency lists. An adjacency matrix is a 2D array where the value at matrix[i][j] indicates whether an edge exists between vertex i and vertex j. For weighted graphs, this value can represent the weight of the edge. An adjacency list, on the other hand, uses a list of lists (or an array of lists). For each vertex, we maintain a list of its adjacent vertices. This is often more space-efficient for sparse graphs (graphs with relatively few edges compared to the number of possible edges).
const graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
};