¿Qué tiempo O(n) nos lleva representar un grafo
dirigido con matrices de adyacencia? ¿ es ventajoso
o no? ¿Qué otro método podemos usar?
La desventaja principal de utilizar una matriz de adyacencias para representar
un grafo (digrafo) es que la matriz requiere un espacio (n^2) incluso si
el grafo (digrafo) es esparso, es decir, si tiene bastante menos de n^2 aristas
(arcos). Sólo leer o examinar la matriz requerirá tiempo O(n^2), en perjuicio de
posibles algoritmos de tiempo O(n) para manipular grafos (digrafos) con O(n)
aristas (arcos). Una alternativa para evitar esta desventaja es utilizar listas para
representar un grafo.
dirigido con matrices de adyacencia? ¿ es ventajoso
o no? ¿Qué otro método podemos usar?
La desventaja principal de utilizar una matriz de adyacencias para representar
un grafo (digrafo) es que la matriz requiere un espacio (n^2) incluso si
el grafo (digrafo) es esparso, es decir, si tiene bastante menos de n^2 aristas
(arcos). Sólo leer o examinar la matriz requerirá tiempo O(n^2), en perjuicio de
posibles algoritmos de tiempo O(n) para manipular grafos (digrafos) con O(n)
aristas (arcos). Una alternativa para evitar esta desventaja es utilizar listas para
representar un grafo.
No hay comentarios:
Publicar un comentario