Depende de cuántos bordes puedan salir de cada vértice y / o con qué frecuencia puede cambiar ese número de bordes. Si hay una pequeña cantidad de bordes, o si la cantidad de bordes puede cambiar con frecuencia, entonces una lista vinculada es probablemente la mejor opción. Existe la sobrecarga del puntero para cada elemento de la lista vinculada y la asignación de memoria (o desasignación) para cada borde que se agrega o elimina. Además, seguir la lista puede agregar una sobrecarga de rendimiento si la lista se alarga.
Si hay una gran cantidad de bordes saliendo de cada vértice, entonces una matriz dinámica puede ser una buena opción. La sobrecarga de memoria para la matriz dinámica es un puntero a la cabeza de la matriz, así como el tamaño máximo y los valores de tamaño utilizados. La asignación de memoria solo debe realizarse una vez para crear la matriz dinámica. El inconveniente es que si la matriz no se llena al tamaño preasignado, puede haber un uso ineficiente de la memoria … y cada vez que necesite más espacio que el tamaño preasignado de la matriz, la matriz debe reasignarse con un tamaño mayor y Los viejos valores copiados.
Desde el punto de vista de la legibilidad y la mantenibilidad del código, la matriz dinámica puede ser conceptualmente más simple … y en algunos casos puede tener un rendimiento excelente. Si esta parte del código no se encuentra en una sección crítica del rendimiento y el número de bordes puede ser significativo, esta puede ser una buena selección.
- ¿Cómo debo codificar el algoritmo en Python?
- Dado un gráfico dirigido, ¿podemos hacer DFS en cada nodo para encontrar el nodo de mayor valor?
- ¿Cuál es el enfoque algorítmico para este problema de hackerrank?
- Tengo un examen de matemáticas discreto y esto está en él. ¿Cuál es la fórmula recursiva de an = an-1 + 2?
- ¿Cuál es el valor de la suma k ^ 2 * C (n, k) 0 a n?
Sin embargo, si no hay muchos bordes para cada vértice (lo cual es común en mi experiencia), o si esta es una sección crítica de rendimiento, tendería a la lista vinculada … o al menos realizaría un experimento probando ambas opciones para comprender mejor el rendimiento características de esta decisión sobre el algoritmo que se ejecuta y la naturaleza estadística de la forma del gráfico.
