Python Graph Traversal Techniques
Graph Basics
What is a Graph?
Think of a social network. You have people (profiles) and the connections between them (friendships). In mathematics and computer science, we model these kinds of networks using a structure called a graph. A graph is just a collection of points and the lines connecting them.
The points are called vertices, and the lines are called edges. That's it. It’s a simple but powerful idea used to represent everything from road maps and internet connections to the flow of tasks in a project.
Vertex
noun
A fundamental part of a graph, also known as a node. It represents a single entity or point in the network.
Edge
noun
A connection between two vertices in a graph, also known as a link or arc. It represents a relationship between the two entities.
Different Kinds of Connections
Not all connections are created equal. A friendship on social media is usually a two-way street; if I'm friends with you, you're friends with me. But if I follow a celebrity, they probably don't follow me back. This difference is key to understanding the two main types of graphs.
An undirected graph has edges that go both ways. Think of them as handshakes or two-way streets. The relationship is mutual.
A directed graph has edges with a specific direction, like one-way streets. These are often called arcs.
We can add another layer of information: edge weights. Imagine our graph represents a map. An unweighted graph would just show that a road exists between two cities. A weighted graph could tell us the distance, the travel time, or the cost of a toll on that road.
In an unweighted graph, the edges simply represent a connection. In a weighted graph, each edge has a numerical value associated with it, representing its cost or capacity.
How We Store Graphs
To use a graph in a computer program, we need a systematic way to store its vertices and edges. The two most common methods are the adjacency list and the adjacency matrix.
An adjacency list is like a phone's contact list. For each vertex, we keep a list of all the vertices it's connected to. It's very efficient when a graph doesn't have many edges.
A: [B, C]
B: [A, C]
C: [A, B]
The other method is an adjacency matrix. This is a grid (a 2D array) where the rows and columns are both labeled by the vertices. We put a 1 in a cell if an edge exists between the row vertex and column vertex, and a 0 otherwise.
For a weighted graph, instead of a 1, we'd store the edge's weight. Adjacency matrices are useful for dense graphs where many vertices are connected to each other.
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
Here's a visual comparison using the same simple undirected graph.
Understanding these basic structures—what graphs are, their different types, and how we represent them—is the first step. With this foundation, you can start exploring the powerful algorithms that operate on them.