Contenido del curso
Representación de Grafos: Matriz y Lista de Adyacencia
Un grafo consta de:
Las cuatro formas más comunes de representar un grafo son:
La matriz de adyacencia es una matriz 2D de tamaño n x n donde n es el número de nodos de un grafo. Sea la matriz 2D matriz[][], una casilla matriz[i][j] = 1 indica que hay una relación del nodo i al nodo j. La matriz de adyacencia también se utiliza para representar grafos con algún peso, entonces si matriz[i][j] = p, entonces hay una relación del nodo i al nodo j con peso wp.
Esta representación es más fácil de implementar y seguir. Eliminar una arista es O(1) porque solo se reemplaza el valor en la casilla correspondiente. Sin embargo, consume O(n^2) en espacio. Incluso si el gráfico es disperso y contiene pocas relaciones, se consume el mismo espacio. Además, añadir un nuevo nodo es consume O(n^2) y encontrar los nodos adyacentes a un nodo es O(n).
Para la lista de adyacencia se utiliza un arreglo o hash table. El tamaño de este es igual al número de nodos. Sea el arreglo un array[]. Una entrada array[i] representa la lista de nodos adyacentes al nodo i-esimo.
A partir de la próxima clase vamos a implementar algoritmos de búsqueda. ¡Nos vemos allá!
Luz Amanda Quilindo Celis
student
Alan Moncada
student
Maria Paulina Aristizabal Pelaez
student
Juan Pablo Sanchez
student
Bryan Castano
student
Santiago García Rincón
studentsegún entendí las dos primeras representaciones serian asi
La notación O(n^2) se refiere a la complejidad temporal de un algoritmo. Se usa para describir cómo el tiempo de ejecución o el espacio requerido crece con respecto al tamaño de la entrada n.
Para crear esta fórmula, se analiza el algoritmo y se determina cuántas operaciones se realizan en función de n. Por ejemplo, en un algoritmo de ordenamiento como burbuja, se comparan pares de elementos en un bucle anidado, lo que resulta en n * n operaciones, o O(n^2).
Entender la complejidad te ayudará a optimizar tus soluciones al trabajar con estructuras de datos como grafos y árboles en tus proyectos.
La matriz de incidencia es otra forma de representar un grafo. En esta representación, se utiliza una matriz donde las filas corresponden a los nodos y las columnas a las aristas. Cada celda de la matriz indica la relación entre un nodo y una arista.
Por ejemplo, si una arista conecta los nodos A y B, la matriz tendrá un valor en las filas de A y B correspondiente a esa arista. Es útil en grafos no dirigidos y puede incluir pesos en las aristas.
Esta representación permite analizar las conexiones entre nodos de manera eficiente, aunque su uso puede ser menos común que las matrices de adyacencia o listas de adyacencia.
Matriz de Adyacencia: | | A | B | C | | A | 0 | 1 | 1 | | B | 1 | 0 | 0 | | C | 1 | 0 | 0 |
Lista de Adyacencia: A -> B -> C B -> A C -> A
Matriz de Incidencia: | | E1 | E2 | | A | 1 | 1 | | B | 1 | 0 | | C | 0 | 1 |
Lista de Incidencia: A -> E1 -> E2 B -> E1 C -> E2
Genial ! , se debe tener presente el tipo de Grafo que vamos a Representar : SI G sea un Grafo disperso con pocas connexiones entre verticies 'aristas' se es mejor una Lista de Adyacencia ps si nosvamos por una Matrix de Adyacencia A[N][N] estariamos desperdiciando mucho espacio de Meoria en posiciones A[i][j] = 0 ; lo cual no es optimo, se debe tener buen criterio para saber cuando implementar una estructura representativa del Grafo que tenemos a Modelar y Optimizar Re<cursos de nuestro Algoritmo en RAM , Este Mundo de los Graphos , Spanning Trees , Heaps y AVL Treess es realmente increible y Fantasitco. \nDeja Volar tu mente para Asimilar lo Abstracto del Asunto aqui presente. \n printf("Graphs Rules the IT World \n");
En este caso, lista de adyacencia es una lista que contiene listas , donde cada una de esas listas, representan las conexiones de esos nodos :)
