Publié · en amélioration
Guide Parcours de graphe · 1/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
Graph traversal means visiting every vertex reachable from a starting point, each exactly once, by following edges. Maps, social networks, task dependencies and mazes are all questions of "what is connected to what", and most of them are solved with a traversal. This chapter covers the vocabulary, how to store a graph in code, and the intuition behind the two classic traversals: breadth-first search (BFS) and depth-first search (DFS).
| Term | Meaning |
|---|---|
| Vertex (node) | A point in the graph: a city, a person, a task, a grid cell |
| Edge | A connection between two vertices: a road, a friendship, a dependency |
| Directed graph | Edges have a direction; A→B does not imply B→A |
| Undirected graph | Every edge works both ways |
| Degree | Number of edges touching a vertex; in-degree and out-degree for directed graphs |
| Path | A sequence of vertices joined by edges |
| Cycle | A path that returns to its starting vertex |
| Connected component | A maximal group of vertices that can all reach each other |
| DAG | Directed Acyclic Graph: a directed graph with no cycles |
By convention V is the number of vertices and E the number of edges. Graph algorithm costs are almost always written in terms of these two.
The default choice is an adjacency list: each vertex keeps a list of its neighbors. It uses O(V + E) memory, and iterating over a vertex's neighbors costs only as much as it has neighbors.
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # undirected: add the reverse edge too
print(graph[2]) # [0, 3, 4]An adjacency matrix is a V x V table of 0s and 1s. It answers "is there an edge between u and v?" in O(1), but needs O(V^2) memory, which is wasteful for sparse graphs with many vertices and few edges.
n = 6
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = matrix[v][u] = 1
print(matrix[2][4] == 1) # True: 2 and 4 are neighborsA plain edge list (the edges variable itself) is also a representation. It suits algorithms that sort edges, such as Kruskal's, but finding neighbors means scanning everything, so for traversal you convert it into an adjacency list first.
For a directed graph, add only u→v. When vertices are strings (city names, module names), either use a dictionary or map each name to an integer id and use a list of lists, which is faster and lighter. If the input numbers vertices from 1, size your lists n + 1 or subtract 1 from every id to avoid index errors.
names = ["core", "ui", "app"]
index = {name: i for i, name in enumerate(names)}
adj = [[] for _ in names]
for before, after in [("core", "ui"), ("ui", "app")]:
adj[index[before]].append(index[after]) # one direction only
print(adj) # [[1], [2], []]Mazes and maps given as 2D grids become graphs once you treat each cell as a vertex and connect cells that touch up, down, left or right. These are usually handled as implicit graphs: instead of building an adjacency list, you compute neighbors on the fly.
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbors(grid, r, c):
rows, cols = len(grid), len(grid[0])
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
yield nr, ncBoth depend on a visited marker. Never revisiting a vertex is what makes traversal terminate on graphs with cycles and keeps the total cost at O(V + E).
| Question | Tool |
|---|---|
| Fewest moves from A to B (no weights) | BFS |
| Are two vertices connected? How many groups? | BFS or DFS |
| Does the graph contain a cycle? | DFS with colors, or Kahn's algorithm |
| An order that respects dependencies | Topological sort (Kahn or DFS) |
| Shortest path with different edge weights | Dijkstra and friends (see Shortest paths) |
A graph models relationships with vertices and edges, and traversal follows edges while marking what it has seen. An adjacency list is the default representation, and grids are best treated as implicit graphs. BFS, which grows outward layer by layer, gives unweighted shortest distances; DFS, which dives deep first, is the tool for structure: components, cycles and topological order.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.