Introduction
Welcome to our new module on Graph Algorithms! In the previous modules, we've built a solid foundation by exploring data structures like lists, hash tables, and most recently, trees. We saw that trees are excellent for representing hierarchical relationships, like a file system or an organization chart.
Today, we take a step into a more general and powerful data structure: the graph. Graphs can model almost any kind of network—from social networks and road maps to the very structure of the internet. This lesson will introduce you to the fundamental concepts of graph theory, directly addressing our learning outcome: to define a graph and distinguish between directed, undirected, weighted, and unweighted graphs.
What is a Graph?
At its core, a graph is a way of representing connections between objects. It consists of two main components:
- Vertices (or Nodes): The objects or points in the network.
- Edges (or Links): The connections between the vertices.
You might recall that trees also have nodes and edges. A tree is actually a special, more restrictive type of graph. Unlike trees, graphs don't have rules like a single root or a strict parent-child hierarchy. This flexibility is what makes them so versatile.
To get a clear formal definition and see how graphs compare to trees, let's watch the first part of the following video.
Data structures: Introduction to graphs
The mycodeschool channel provides a great introduction to graphs, starting from the basic definition and explaining the formal notation used to describe them.
Watch from 00:29 to 05:02. Focus on how a graph is formally defined as a pair of sets, G = (V, E), and how this differs from the structure of a tree.
As the video explained, a graph G is formally defined as an ordered pair G = (V, E), where V is the set of vertices and E is the set of edges. This mathematical precision is the foundation for all graph algorithms.
Before we discuss the different types of graphs, it's useful to learn some common terminology. The next video introduces key terms you'll hear often when working with graphs.
Introduction to Graph Theory: A Computer Science Perspective
This clip from the Reducible channel clearly defines essential graph terminology that we will use throughout this module.
Watch from 04:25 to 07:10. Pay attention to the definitions of: neighbors, degree, path, and cycle. You don't need to memorize them all at once, but it's good to get familiar with the language.
Distinguishing Graph Types
Not all relationships or networks are the same. Is a friendship on Facebook the same kind of connection as a one-way street? Is a flight path between two cities the same as a simple "is connected to" link? To model these differences, we classify graphs based on two key properties: direction and weight.
1. Directed vs. Undirected Graphs
The first distinction is about the nature of the connection. Is it a two-way street or a one-way road?
- An undirected graph represents a symmetric, or two-way, relationship. If there's an edge between vertex A and vertex B, the connection goes both ways. Think of a friendship on Facebook: if you are friends with someone, they are also friends with you.
- A directed graph (or digraph) represents an asymmetric, or one-way, relationship. An edge from vertex A to vertex B does not imply there is an edge from B to A. Think of following someone on X (formerly Twitter): you can follow a celebrity, but they don't automatically have to follow you back.
The mycodeschool video you started earlier provides excellent, real-world examples to make this distinction clear.
Data structures: Introduction to graphs
Let's continue with the mycodeschool video to see how directed and undirected graphs are used to model different kinds of networks.
Watch from 05:02 to 13:09. Observe the examples of a social network (undirected) and the World Wide Web (directed) and how the type of edge changes how we model the problem.
2. Weighted vs. Unweighted Graphs
The second distinction is about the cost or value of a connection. Are all connections equal, or do some carry more "weight" than others?
- An unweighted graph assumes all edges are uniform. The only information an edge provides is that a connection exists. A basic social network, where the only state is "friends" or "not friends," is a good example.
- A weighted graph assigns a numerical value, or "weight," to each edge. This weight can represent distance, time, cost, capacity, or any other measurable quantity. For example, in a road map graph, the weight of an edge between two cities could be the distance in kilometers.
Let's watch the final segment of the video, which illustrates this concept perfectly using a map.
Data structures: Introduction to graphs
The last part of the mycodeschool video explains weighted graphs and shows why they are crucial for solving many real-world optimization problems.
Watch from 13:09 to 16:32. Notice how adding weights (distances) to the road network completely changes how you would determine the 'best' route between two cities.
Putting It All Together
The properties of direction and weight are independent. This means you can have four primary combinations of graphs, each suited for modeling different types of problems.
The following article provides a concise textual summary of these graph types. Reading through it will help reinforce what you've learned from the videos.
An Introduction to Graph Theory
The article 'An Introduction to Graph Theory' from DataCamp provides clear, separate definitions for the main graph types, with helpful visuals.
From the article, read the sections under the heading 'Types of Graphs'. Focus on the definitions and applications for 'Weighted Graphs', 'Directed Graphs (Digraphs)', and 'Undirected Graphs'.
To summarize visually, here are examples of the four combinations:
- Undirected & Unweighted: A basic social network (Are A and B friends? Yes/No).
- Directed & Unweighted: A website map (Can you get from page A to page B via a link?).
- Undirected & Weighted: A network of water pipes between locations (What is the capacity of the pipe between A and B?).
- Directed & Weighted: An airline route map (What is the flight time or cost from airport A to airport B?).
Understanding which type of graph to use is the first step in solving any graph-based problem.
Conclusion
In this lesson, we've moved from the hierarchical world of trees to the interconnected networks of graphs. You now have the foundational knowledge to describe and categorize these powerful data structures, which is a key first step for any algorithm involving them.
Key Takeaways:
- A graph is a data structure consisting of a set of vertices (nodes) and a set of edges (connections).
- Graphs are defined by two main properties:
- Direction: Edges can be undirected (two-way) or directed (one-way).
- Weight: Edges can be unweighted (all equal) or weighted (having an associated cost or value).
- The combination of these properties allows us to model a vast range of real-world systems, from social networks to navigation systems.
Preview of the Next Lesson:
Now that we understand the concept of a graph, our next challenge is to figure out how to store one in a computer's memory. In the next lesson, we will learn how to represent a graph using an adjacency list in Python. This is the most common method used in coding interviews and will be the backbone of the graph algorithms we'll build in the lessons to come.