Mastering Depth-First Search in Python
Introduction to Graphs
What Is a Graph?
Think of a social network. You have people (profiles) and the connections between them (friendships). A graph is just a formal way to represent this kind of network. It's a structure made of two simple things: points and the lines that connect them.
In computer science, we call the points vertices (or nodes) and the connecting lines edges. That's it. A graph is just a collection of vertices and edges.
This structure is incredibly useful. Graphs can model all sorts of real-world systems, from city maps and airline routes to the internet and the connections between web pages.
Types of Graphs
Not all connections are the same. Sometimes relationships are mutual, and sometimes they go in only one direction. This leads to our first distinction.
An undirected graph has edges that work both ways. If A is connected to B, then B is connected to A. Think of a friendship on Facebook.
A directed graph has edges with a direction, shown as arrows. If A points to B, it doesn't mean B points back to A. Think of following someone on Twitter.
Connections can also have values associated with them. Think of a map. The lines between cities aren't just connections; they represent a distance. This brings us to another key difference.
An unweighted graph simply shows connections. The edges don't have a value.
A weighted graph assigns a number (a weight) to each edge. This weight could represent distance, cost, time, or anything else that measures the strength or cost of a connection.
These types can be combined. For example, a map of airline routes could be a directed, weighted graph. The flights go in one direction (directed) and have a cost or flight time (weighted).
| Graph Type | Edge Direction | Edge Weight | Example |
|---|---|---|---|
| Undirected, Unweighted | No direction | No weight | Facebook friendships |
| Undirected, Weighted | No direction | Has weight | A map of road distances |
| Directed, Unweighted | Has direction | No weight | Following users on Twitter |
| Directed, Weighted | Has direction | Has weight | Airline routes with flight times |
Essential Terms
Finally, let's nail down a couple of terms we use to describe relationships and sequences within a graph.
Adjacency
noun
Two vertices are adjacent if they are connected by an edge. They are direct neighbors.
Path
noun
A sequence of vertices where each adjacent pair in the sequence is connected by an edge.
With these basics—vertices, edges, and the different ways they can be characterized—you have the foundation for understanding how we work with graphs.
In graph theory, what are the two fundamental components that make up a graph?
You are modeling a city's road system, including one-way streets. Which type of graph would be most appropriate for this task?