A graph is made of points and connections. A point is called a vertex or node. A connection is called an edge.
On a map, cities can be nodes and roads can be edges. In a social app, people can be nodes and friendships can be edges.
Edges can tell different stories
An undirected edge works both ways, like a friendship. A directed edge has an arrow, like one person following another. A weighted edge has a number such as distance, price, or time.
Graphs are flexible. A node can connect to many other nodes, and there does not need to be one root.
How do we explore a graph?
Breadth-first search, or BFS, explores like ripples in water. It visits all nearby nodes first, then nodes one step farther away. This can find the path with the fewest edges in an unweighted graph.
Depth-first search, or DFS, follows one path as far as it can. When it reaches a dead end, it walks back and tries another path.
- Use BFS when nearby steps matter.
- Use DFS when you want to explore a whole branch.
- Mark visited nodes so you do not run in circles.
A tiny route example
Home connects to Park and Shop. Park connects to School. Shop also connects to School. There are two routes from Home to School, and a graph keeps both choices.
Navigation, recommendations, computer networks, games, and delivery systems all use graph ideas.
from collections import deque
graph = {
"Home": ["Park", "Shop"],
"Park": ["School"],
"Shop": ["School"],
"School": [],
}
line = deque(["Home"])
visited = {"Home"}
while line:
place = line.popleft()
print(place)
for neighbor in graph[place]:
if neighbor not in visited:
visited.add(neighbor)
line.append(neighbor)Your tiny challenge
Draw five places as circles. Add roads as lines. Can you travel between every pair of places? Which route uses the fewest roads? You are thinking with graphs.