Graphs and finding paths — Computing, 14–17 years
A graph represents things and the links between them. Once a problem is drawn this way, a computer can explore routes, connections or dependencies instead of treating each situation as a special case.
Things and links
In a graph, a vertex stands for a thing and an edge stands for a relationship or route between things. Cities can be vertices and roads edges; people can be vertices and friendships edges. Edges may have directions or weights, such as one-way travel or a distance in kilometres.
Why draw a graph?
Many real problems are really about connections: delivering parcels, routing messages, suggesting friends or ordering tasks with prerequisites. Lists of isolated facts hide those connections. Graphs give the computer a common shape for these problems, so one method can work on roads, websites or dependencies.
Choosing the shortest route
Suppose A connects to B in 4 km, A to C in 1 km, C to B in 2 km, and B to D in 3 km. From A to B, the direct route is 4 km, but A–C–B is 1 + 2 = 3 km, so it is shorter. From A to D through C and B, the total is 1 + 2 + 3 = 6 km.
The fewest steps is not always shortest
It is natural to count only how many links a route uses: two roads look better than three. But links can have very different lengths, delays or prices. A route with three edges of 1 km may beat a route with two edges of 10 km, so the graph must record the quantity that actually matters.
Graphs outside the classroom
Navigation apps use road graphs with distances and traffic times. Social platforms use graphs of accounts and relationships, while a web search can follow links between pages. In each case, the result depends on what counts as a connection and what weight matters: distance, time, cost or relevance.
Keep exploring
Other languages
Loading MyLeoNes™…