Graph
A graph is a data structure consisting of a set of nodes (vertices) connected by edges, which may be directed or undirected and weighted or unweighted, used to model relationships and networks such as social connections, road maps, and…
Definition
A graph is a data structure consisting of a set of nodes (vertices) connected by edges, which may be directed or undirected and weighted or unweighted, used to model relationships and networks such as social connections, road maps, and dependency chains. Unlike trees, graphs can contain cycles and allow multiple paths between nodes.
Overview
Graphs are the most general way to represent pairwise relationships between entities. A directed graph's edges have direction (e.g., 'follows' on social media), while an undirected graph's edges are symmetric (e.g., 'friends with'). Weighted graphs attach a cost or value to each edge, useful for representing distance, time, or capacity, while unweighted graphs treat all edges equally. Graphs are typically represented in code as an adjacency list (each node stores a list of its neighbors, efficient for sparse graphs) or an adjacency matrix (a 2D array indicating edge presence/weight between every pair, efficient for dense graphs but O(V²) space). Traversal algorithms include breadth-first search (BFS), which explores level by level using a queue and finds shortest paths in unweighted graphs, and depth-first search (DFS), which explores as far as possible along a branch before backtracking, typically implemented recursively or with a stack. Common graph algorithms solve specific problems: Dijkstra's algorithm finds shortest paths in weighted graphs with non-negative edges; Bellman-Ford handles negative weights; A* adds heuristics for faster pathfinding; topological sort orders nodes in a directed acyclic graph (DAG) respecting dependencies; and union-find (disjoint set) efficiently tracks connected components, often used in Kruskal's minimum spanning tree algorithm. Graphs model an enormous range of real-world systems: social networks, road and transit networks, the web's hyperlink structure, dependency graphs in build systems and package managers, and knowledge graphs behind search and recommendation engines. Graph databases (e.g., Neo4j) store and query this structure natively, optimizing for traversal-heavy queries that relational joins handle poorly at scale.
Key Concepts
- Nodes (vertices) connected by edges, directed or undirected
- Can be weighted (costs on edges) or unweighted
- Represented as adjacency lists (sparse) or adjacency matrices (dense)
- BFS finds shortest paths in unweighted graphs; DFS explores depth-first
- Dijkstra's and A* solve weighted shortest-path problems
- Topological sort orders nodes in a directed acyclic graph
- Can contain cycles, unlike trees, and support multiple paths between nodes