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
Use Cases
Frequently Asked Questions
From the Blog
Graph Algorithms: BFS and DFS Explained
Breadth-first and depth-first search are the two fundamental ways to explore a graph. Learn how each traverses nodes, when to use it, and how to code both.
Read More AI & TechnologyWhat Is an AI Knowledge Graph?
An AI knowledge graph stores facts as connected entities and relationships, letting machines reason over data, answer complex questions, and ground LLM output.
Read More AI & TechnologyWhat Is a Line Graph and When Should You Use One?
A line graph plots data points connected by straight lines to show how a value changes over a continuous scale, usually time. This guide explains how to read one, when it's the right chart choice, and common mistakes to avoid.
Read More Cloud & CybersecurityNoSQL Data Models: Document, Key-Value, Wide-Column, Graph
The four NoSQL families each optimise for a different access pattern and each has query shapes that make it a poor choice. This guide explains what document, key-value, wide-column and graph stores are actually good at, how to model for them, and the failure modes that only appear once your data grows.
Read More