Introduction to Graph Data Structures

Graph data structures are among the most versatile and expressive tools in all of computer science. Where simpler structures like arrays or linked lists organize data in a linear sequence, and trees impose a strict hierarchical parent-child relationship, graphs impose almost no such constraints. This freedom allows graphs to model an extraordinary range of real-world systems — from the social connections between billions of people, to the routing tables that guide packets across the internet, to the dependency chains that a package manager must resolve before installing software. To work effectively with graphs, you need to understand their fundamental components and the vocabulary used to describe them precisely.

At its core, a graph is a mathematical structure consisting of two things: a set of vertices and a set of edges. Vertices (also called nodes) represent the individual entities in the system being modeled. Edges represent the relationships or connections between those entities. That's it — and yet from this deceptively simple definition emerges a data structure capable of capturing almost any network of relationships imaginable.

Formally, a graph is written as G = (V, E), where V is the set of all vertices and E is the set of all edges. For example, if you had a small graph of three cities — say, Austin, Dallas, and Houston — your vertex set would be V = {Austin, Dallas, Houston}. If Austin is connected to Dallas and Dallas is connected to Houston, your edge set would be E = {(Austin, Dallas), (Dallas, Houston)}. This notation is precise and universal, allowing computer scientists and mathematicians to reason about graphs regardless of what domain they come from.

Vertices (Nodes) are the fundamental units of a graph. A graph can contain any number of vertices. A graph with zero vertices is called an empty graph — a valid but trivial case. In practice, real-world graphs range from a handful of nodes to hundreds of millions. Each vertex typically stores data relevant to the entity it represents. In a social network, a vertex might store a user's name, profile ID, and location. In a road network, a vertex might represent an intersection and store its GPS coordinates. In a dependency graph for software packages, each vertex represents a package and stores its version number and metadata.

The collection of all vertices is denoted V, and the total count of vertices is written |V| (read as "the cardinality of V"). This notation becomes important when analyzing the time and space complexity of graph algorithms, where performance is often expressed in terms of |V| and |E|.

Edges (Connections) are what give graphs their power. An edge connects exactly two vertices, which are called its endpoints. The set of all edges is denoted E, and each edge can be thought of as a pair of vertices. Edges are not required to carry any additional information — a plain edge simply indicates that a relationship exists between two vertices. However, edges can optionally carry weights, labels, or other metadata. A weighted edge between two cities might store the driving distance in miles. A weighted edge in a financial network might store the transaction volume between two institutions. This additional information enables a whole class of algorithms — such as Dijkstra's shortest path algorithm — that depend on edge weights to find optimal routes or costs.

A graph with no edges at all is called an edgeless graph or null graph. In this case, every vertex exists in complete isolation — no relationships connect any of them. This is another valid but trivial case, useful as a base case in recursive or inductive reasoning about graphs.

One of the most important distinctions in graph theory is between directed and undirected graphs. In an undirected graph, every edge is bidirectional. If there is an edge between vertex A and vertex B, it implies that you can travel from A to B and from B to A. The edge has no inherent direction — it simply states that A and B are connected. Friendships on Facebook are a classic example: if Alice is friends with Bob, then Bob is also friends with Alice. The relationship is symmetric.

In a directed graph (often called a digraph), every edge has a specific direction. A directed edge from vertex A to vertex B means you can travel from A to B, but not necessarily from B to A. Directed edges are typically drawn with arrows to make the direction explicit. Twitter's "follow" relationship is a perfect real-world example: Alice can follow Bob without Bob following Alice. The relationship is asymmetric. Other examples include web hyperlinks (a page can link to another page without being linked back), dependency graphs (package A depends on package B, but not vice versa), and circuit diagrams (current flows in a specific direction).

Understanding the distinction between directed and undirected graphs is critical because many algorithms behave differently depending on which type of graph they operate on. A cycle-detection algorithm, for instance, must account for the fact that in an undirected graph, an edge between A and B could be mistakenly interpreted as A pointing back to itself.

With the basic components defined, it is worth carefully reviewing the key vocabulary used throughout graph theory, since these terms appear constantly in algorithm descriptions and technical discussions:

• Degree: The degree of a vertex is the number of edges connected to it. A vertex with degree 0 is called an isolated vertex — it has no connections. In an undirected graph, every edge contributes 1 to the degree of each of its two endpoints. In a directed graph, the degree concept is split into two: the in-degree of a vertex is the number of edges arriving at it (incoming edges), and the out-degree is the number of edges leaving it (outgoing edges). For example, in a Twitter graph, a celebrity with millions of followers has a very high in-degree but might follow very few accounts themselves, giving a low out-degree.
• Path: A path is a sequence of vertices in which each consecutive pair is connected by an edge, and no vertex is repeated. For example, in a graph of cities, the sequence Austin → Dallas → Oklahoma City → Kansas City could be a valid path if each of those consecutive connections exists as an edge. The length of a path is typically the number of edges traversed (or, in a weighted graph, the sum of the edge weights along the path).
• Cycle: A cycle is a path that starts and ends at the same vertex, forming a closed loop. For instance, if edges exist between A→B, B→C, and C→A, then A→B→C→A is a cycle. Cycles are critically important in many algorithms. Graphs with no cycles are called acyclic; a directed acyclic graph (DAG) is one of the most useful graph variants in computer science, underpinning topological sorting and many scheduling algorithms.
• Adjacent vertices (Neighbors): Two vertices are called adjacent or neighbors if they are directly connected by an edge. In the graph of cities above, Austin and Dallas are adjacent if there is a direct edge between them. The set of all neighbors of a vertex v is called its adjacency list, a concept central to how graphs are stored in memory.
• Connected graph: An undirected graph is called connected if there exists at least one path between every pair of vertices. Intuitively, a connected graph is "all in one piece" — you can get from any node to any other node by following edges. If a graph is not connected, it is called disconnected, and it consists of two or more separate connected components, each of which is itself a connected subgraph. In a directed graph, the analogous concepts are strongly connected (there is a directed path from every vertex to every other vertex) and weakly connected (the underlying undirected version of the graph is connected).

To make these terms concrete, consider a small example graph with five vertices and six edges:

In this undirected weighted graph: vertex A has degree 2 (connected to B and C); vertex B has degree 3 (connected to A, C, and D); vertex D has degree 3 (connected to B, C, and E); vertex E has degree 1 (connected only to D, making it a leaf). The sequence A → C → D → E is a valid path of length 3 (or total weight 2+3+7=12 if we count weights). The sequence A → B → C → A is a cycle. The entire graph is connected because you can reach any vertex from any other vertex.

In code, a graph is often represented in one of two fundamental ways. An adjacency matrix uses a 2D array where position [i][j] stores 1 (or the edge weight) if an edge exists between vertex i and vertex j, and 0 otherwise. An adjacency list uses an array of lists, where each index corresponds to a vertex, and the list at that index contains all of its neighbors. Here is a simple adjacency list representation in Python for the undirected graph above:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D']
}

This concise representation already encodes all the connectivity information of the graph and is the starting point for algorithms like breadth-first search (BFS) and depth-first search (DFS), which systematically explore the graph by following edges from vertex to vertex.

The real-world applications of graphs are vast and span nearly every field of computer science and beyond:

• Social networks: Platforms like Facebook, LinkedIn, and Twitter model their users as vertices. Friendships, connections, or follows are edges. Graph algorithms power features like friend recommendations ("people you may know"), community detection, and influence analysis. With billions of users, these are among the largest graphs ever constructed.
• The World Wide Web: Every web page is a vertex, and every hyperlink from one page to another is a directed edge. Google's foundational PageRank algorithm treats the web as a directed graph and ranks pages by analyzing the structure of incoming links — a page linked to by many other high-authority pages is itself considered authoritative.
• Navigation and mapping: Road networks are undirected (or sometimes directed, for one-way streets) weighted graphs. Intersections are vertices, roads are edges, and weights represent distances or travel times. Algorithms like Dijkstra's and A* find the shortest path between two locations, powering GPS navigation systems.
• Dependency resolution: Package managers (like npm, pip, or apt) must install software packages in an order that respects dependencies — if package A depends on package B, then B must be installed first. This problem is modeled as a directed acyclic graph and solved using topological sort.
• Network routing: The internet's routers use graph algorithms to determine the best path for data packets to travel from source to destination, minimizing latency and avoiding congested or failed links.
• Biology and chemistry: Molecular structures are modeled as graphs where atoms are vertices and chemical bonds are edges. Protein interaction networks, gene regulatory networks, and metabolic pathways are all studied using graph-theoretic tools.
• Scheduling: Scheduling problems, such as assigning time slots to university courses so that no student has a conflict, can be modeled as graph coloring problems — assign a "color" (time slot) to each vertex (course) such that no two adjacent vertices (courses with shared students) share a color.

Understanding the graph as a data structure — its components, its vocabulary, and the distinction between directed and undirected variants — is the essential prerequisite for everything that follows in graph theory and algorithm design. Once you are fluent in this vocabulary, the logic behind traversal algorithms like BFS and DFS, shortest-path algorithms, cycle detection, and minimum spanning trees becomes far more approachable. Every one of those algorithms is ultimately just a strategy for navigating and extracting meaning from the vertices and edges that make up a graph.