Graphs

Introduction: why graphs matter in computer science

students, imagine trying to model a city’s subway system 🚇, a social network 👥, or the pages connected by links on the web 🌐. A simple list is not enough, because each item can be connected to several other items. That is where graphs come in. A graph is an abstract data structure used to represent relationships between objects. In IB Computer Science HL, graphs are important because they help us model real-world systems where connections matter just as much as the objects themselves.

By the end of this lesson, students, you should be able to:

explain the main ideas and terminology behind graphs;
describe how graphs are used to represent data;
apply basic reasoning about graph structures and operations;
connect graphs to the wider topic of abstract data structures;
use examples to show why graphs are useful in computing.

Graphs are a core example of abstraction. Instead of storing every detail about a real system, we keep only the information needed for the problem. For example, when planning routes between cities, we may store the cities as vertices and the roads as edges. This makes the data easier to work with, analyze, and search.

Graph terminology and core ideas

A graph is made of two main parts:

Vertices (also called nodes) — the objects in the graph;
Edges — the links or connections between vertices.

If a graph is written as $G=(V,E)$, then $V$ is the set of vertices and $E$ is the set of edges. This notation is common in computer science and mathematics.

There are several important types of graphs:

Undirected graph: an edge has no direction, so the connection works both ways.
Directed graph or digraph: each edge has a direction, shown with an arrow.
Weighted graph: each edge has a value, such as distance, time, cost, or capacity.
Unweighted graph: edges simply show whether a connection exists.
Simple graph: no loops and no multiple edges between the same pair of vertices.
Cyclic graph: contains at least one cycle, meaning you can start at a vertex and return to it by following edges.
Acyclic graph: contains no cycles.

A few more useful terms:

The degree of a vertex in an undirected graph is the number of edges connected to it.
In a directed graph, the in-degree is the number of incoming edges and the out-degree is the number of outgoing edges.
A path is a sequence of connected vertices.
A walk may repeat vertices or edges.
A simple path does not repeat vertices.
A graph is connected if there is a path between every pair of vertices.

For example, if a school network shows computers connected by cables, each computer is a vertex and each cable is an edge. If every computer can reach every other computer, the graph is connected. If one computer is isolated, the graph is not connected.

Representing graphs in memory

Computers cannot store a graph as a picture alone; the structure must be represented in memory. Two common methods are adjacency matrix and adjacency list.

Adjacency matrix

An adjacency matrix is a table used to show whether pairs of vertices are connected. If there are $n$ vertices, the matrix is an $n \times n$ grid. The entry at row $i$ and column $j$ is usually $1$ if there is an edge from vertex $i$ to vertex $j$, and $0$ if there is not.

For a weighted graph, the entry may store the weight instead of $1$. If there is no edge, the cell may contain $0$, $\infty$, or another special value.

Advantages:

quick to check whether two vertices are connected;
simple to understand.

Disadvantages:

uses a lot of memory when the graph has many vertices but few edges;
requires $n^2$ space, even if only a few edges exist.

Adjacency list

An adjacency list stores, for each vertex, a list of its neighboring vertices. If the graph is weighted, each neighbor can be paired with a weight.

Advantages:

uses less memory for sparse graphs, where $|E|$ is much smaller than $|V|^2$;
efficient for listing all neighbors of a vertex.

Disadvantages:

checking whether a specific edge exists may take longer than with a matrix.

This is a great example of abstraction in action. The best representation depends on the problem. A social media app might use adjacency lists because each user has only a limited number of connections compared with the total number of users. A route-planning system may use weighted graphs because distances or travel times are essential.

Why graphs are powerful: examples and applications

Graphs are used across computer science and everyday life. Here are some common examples:

Transportation networks: cities are vertices and roads are edges 🚗.
Social networks: users are vertices and friendships or follows are edges 👥.
Web pages: pages are vertices and links are directed edges 🌐.
Computer networks: devices are vertices and communication links are edges 🖧.
Project planning: tasks can be connected by dependency relationships.

A useful real-world example is Google Maps or any route-finding app. The app must determine a path between locations, often with weights such as distance or time. The road network can be modeled as a weighted graph. A shorter path is often better, but the best path may also depend on traffic, road closures, or one-way streets.

Another example is course prerequisites at school. If one course must be completed before another, that relationship can be shown using a directed graph. A course with no prerequisites might have no incoming edges, while an advanced course may have many.

Graphs also help computers solve problems such as:

finding the shortest path;
searching through networks;
detecting cycles;
checking whether a system is connected;
organizing tasks in a valid order.

Common graph procedures and IB-style reasoning

In IB Computer Science HL, it is important to understand the reasoning behind graph operations, even if the exact algorithm details vary by syllabus focus. Two important ideas are traversal and shortest path.

Graph traversal

Traversal means visiting vertices in an organized way. Two standard approaches are:

Breadth-first search $(\text{BFS})$;
Depth-first search $(\text{DFS})$.

In BFS, the graph is explored level by level. This is useful when the shortest path in terms of number of edges is needed in an unweighted graph.

In DFS, the search goes as far as possible down one branch before backtracking. This is useful for exploring structures, checking connectivity, and detecting cycles.

Example: suppose students is tracing friends-of-friends in a social network. BFS would first visit direct friends, then friends of friends, then the next level. That matches a “wave” of exploration.

Shortest path reasoning

In a weighted graph, the goal may be to find the path with the smallest total weight. If edge weights represent distance, then the shortest path gives the least total travel distance. If weights represent time, the shortest path gives the quickest route.

The total weight of a path is the sum of its edge weights. For example, if a path uses edges with weights $4$, $7$, and $3$, then the path cost is $4+7+3=14$.

This kind of reasoning is important in IB because it shows how data structures support problem solving. A graph is not just a picture; it is a model that can be processed by an algorithm.

Cycles and special structures

Some graphs contain cycles, and some do not. A graph with no cycles is called a tree if it is also connected and undirected. Trees are a special kind of graph and are very important in computer science because they support efficient searching and hierarchical organization.

In directed graphs, a cycle can create problems in dependency systems. For example, if task $A$ depends on task $B$, task $B$ depends on task $C$, and task $C$ depends on task $A$, then no valid order exists. Detecting cycles helps avoid such contradictions.

Graphs and abstract data structures

Graphs fit naturally into the HL Extension topic of Abstract Data Structures because they separate the idea of a connection-based system from the details of how it is stored.

This abstraction is valuable because:

it helps programmers model complex relationships clearly;
it allows different storage methods, such as adjacency matrices or adjacency lists;
it supports efficient algorithms for search, routing, and dependency analysis;
it can represent many kinds of real systems with the same basic structure.

Graphs also show the difference between data organization and computation. The way data is organized affects how fast an algorithm can run and how easy it is to write. For example, an adjacency matrix may make edge lookup simple, while an adjacency list may make memory use smaller. Choosing the right representation is part of algorithmic thinking.

For HL students, this is an important idea: abstract data structures are not only about storing information, but also about making computation possible and efficient. A well-chosen graph representation can make a route-finding problem practical instead of impossible.

Conclusion

Graphs are one of the most useful abstract data structures in computer science because they model relationships between objects. students, you have seen that graphs use vertices and edges, can be directed or undirected, weighted or unweighted, and can be stored in different ways depending on the task. They appear in transportation, social media, web links, and many other systems.

In IB Computer Science HL, graphs connect directly to the study of abstraction, efficiency, and data organization. Understanding graph terminology and representation gives you the tools to reason about real problems such as shortest paths, connectivity, and dependencies. Graphs are a powerful example of how an abstract structure can help solve practical computational problems 📘.

Study Notes

A graph is an abstract data structure made of vertices and edges.
A graph can be written as $G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges.
An undirected graph has edges with no direction; a directed graph has arrows.
A weighted graph stores values on edges such as distance, time, or cost.
The degree of a vertex is the number of connected edges in an undirected graph.
In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges.
A path is a sequence of connected vertices; a cycle starts and ends at the same vertex.
A connected graph has a path between every pair of vertices.
Adjacency matrices use more memory but make edge checking fast.
Adjacency lists use less memory for sparse graphs and are efficient for listing neighbors.
BFS explores level by level; DFS explores one branch deeply before backtracking.
Graphs are used in maps, social networks, web links, computer networks, and project planning.
Graphs are important in HL Abstract Data Structures because they show how abstraction supports efficient problem solving.