Grafos y búsqueda de caminos — Informática, 14–17
Un grafo representa cosas y las conexiones entre ellas. Cuando un problema se dibuja así, un ordenador puede explorar rutas, conexiones o dependencias, en vez de tratar cada situación como un caso especial.
Cosas y conexiones
En un grafo, un vértice representa una cosa y una arista representa una relación o ruta entre cosas. Las ciudades pueden ser vértices y las carreteras, aristas; las personas pueden ser vértices y las amistades, aristas. Las aristas pueden tener dirección o peso, como un trayecto de un solo sentido o una distancia.
¿Por qué dibujar un grafo?
Muchos problemas reales tratan de conexiones: repartir paquetes, dirigir mensajes, sugerir amigos u ordenar tareas con requisitos previos. Las listas de datos aislados ocultan esas conexiones. Los grafos ofrecen al ordenador una forma común de representar estos problemas, útil para carreteras, sitios web o dependencias.
Elegir la ruta más corta
Supón que A conecta con B en 4 km, A con C en 1 km, C con B en 2 km y B con D en 3 km. De A a B, la ruta directa mide 4 km, pero A–C–B mide 1 + 2 = 3 km, así que es más corta. De A a D pasando por C y B, el total es 1 + 2 + 3 = 6 km.
Menos pasos no siempre es la ruta más corta
Es natural contar solo cuántas conexiones usa una ruta: dos carreteras parecen mejores que tres. Pero las conexiones pueden tener longitudes, retrasos o precios muy distintos. Una ruta con tres aristas de 1 km puede ganar a otra con dos de 10 km, así que el grafo debe registrar lo que realmente importa.
Grafos fuera del aula
Las aplicaciones de navegación usan grafos de carreteras con distancias y tiempos de tráfico. Las plataformas sociales usan grafos de cuentas y relaciones, mientras que un buscador puede seguir enlaces entre páginas. En cada caso, el resultado depende de qué sea una conexión y qué peso importe: distancia, tiempo, coste o relevancia.
Sigue explorando
Otros idiomas
Cargando MyLeoNes™…