Proyecto 2 de la asignatura de Diseño y Análisis de Algoritmos

Desarrollador :

Yordi Edgardo Delgado Ortiz

Información:

Utilizando la biblioteca de grafos desarrollada en el proyecto 1, se implementaron los algoritmos BFS y DFS (recursivo e iterativo) de tal forma que dado un nodo fuente (s), calcula el árbol inducido por los algoritmos mencionados; es decir, se desarrollaron los métodos en la clase Grafo:

• def dfs(self, s)
• def dfs_i(self, s)
• def dfs_r(self, s)

Imágenes de los Modelos Generadas con gephi

Modelo de Mallas

30 nodos(5x6)

BFS

DFS Iterativo

DFS Recursivo

100 nodos(10x10)

BFS

DFS Iterativo

DFS Recursivo

500 nodos(50x10)

BFS

DFS Iterativo

DFS Recursivo

Modelo de Erdos y Renyi

30 Nodos y 200 Aristas

BFS

DFS Iterativo

DFS Recursivo

100 Nodos y 400 Aristas

BFS

DFS Iterativo

DFS Recursivo

500 Nodos y 2500 Aristas

BFS

DFS Iterativo

DFS Recursivo

Modelo de Gilbert

30 nodos y probabilidad 0.5

BFS

DFS Iterativo

DFS Recursivo

100 nodos y probabilidad 0.3

BFS

DFS Iterativo

DFS Recursivo

500 nodos y probabilidad 0.02

BFS

DFS Iterativo

DFS Recursivo

Modelo Geográfico

30 nodos y distancia 0.5

BFS

DFS Iterativo

DFS Recursivo

100 nodos y distancia 0.3

BFS

DFS Iterativo

DFS Recursivo

500 nodos y distancia 0.15

BFS

DFS Iterativo

DFS Recursivo

Modelo Barabasi

30 nodos y grado 10

BFS

DFS Iterativo

DFS Recursivo

100 nodos y grado 7

BFS

DFS Iterativo

DFS Recursivo

500 nodos y grado 12

BFS

DFS Iterativo

DFS Recursivo

Modelo Dorogovtsev

30 nodos

BFS

DFS Iterativo

DFS Recursivo

100 nodos

BFS

DFS Iterativo

DFS Recursivo

500 nodos

BFS

DFS Iterativo

DFS Recursivo