Embedded Files
Tipos de grafos
Tipos de grafos
Un grafo puede tener diferentes características según la forma en que se conectan sus nodos.
Un grafo no dirigido tiene conexiones sin dirección. Si el nodo A está conectado con el nodo B, también se entiende que B está conectado con A.
Un grafo dirigido tiene conexiones con una dirección específica. Esto significa que una arista puede ir de A hacia B, pero no necesariamente de B hacia A.
Un grafo ponderado tiene valores o pesos en sus aristas. Estos pesos pueden representar distancia, costo, tiempo o dificultad.
Un grafo no ponderado no tiene valores asociados a sus conexiones. Solo importa si existe o no una conexión.
Representación de grafos en programación
Representación de grafos en programación
Para trabajar con grafos en código, es necesario representarlos de una forma que la computadora pueda entender.
Las representaciones más comunes son:
Matriz de adyacencia
Matriz de adyacencia
La matriz de adyacencia usa una tabla para indicar si existe conexión entre dos nodos.
Si existe una conexión, se coloca un 1.
Si no existe conexión, se coloca un 0.
Esta representación es fácil de entender, pero puede ocupar mucha memoria cuando el grafo tiene muchos nodos y pocas conexiones.
Lista de adyacencia
Lista de adyacencia
La lista de adyacencia utiliza un arreglo (o vector) donde cada posición representa un nodo del grafo. En cada posición, se guarda una lista con los nodos a los que está directamente conectado.
A diferencia de la matriz, aquí solo registramos las conexiones que realmente existen.
Esta representación es mucho más eficiente en memoria cuando el grafo tiene muchos nodos pero pocas conexiones (lo que se conoce como un grafo disperso).
Page updated
Google Sites
Report abuse