Árboles y grafos

Estructuras de datos y algoritmos en Python

Miriam Antona

Software engineer

Árboles: definición

Imagen de un árbol con nodos.

  • Estructuras de datos basadas en nodos
  • Cada nodo puede tener enlaces a más de un nodo
Estructuras de datos y algoritmos en Python

Árboles: terminología

Imagen de un árbol con nodos. El nodo raíz está en amarillo.

Estructuras de datos y algoritmos en Python

Árboles: terminología

Imagen de un árbol con nodos. El nodo raíz está en amarillo. Un nodo padre está en naranja.

Estructuras de datos y algoritmos en Python

Árboles: terminología

Imagen de un árbol con nodos. El nodo raíz está en amarillo. Un nodo padre está en naranja y sus hijos en verde.

Estructuras de datos y algoritmos en Python

Árboles: terminología

Imagen de un árbol con nodos.

Estructuras de datos y algoritmos en Python

Árboles: terminología

Imagen de un árbol con nodos y sus distintos niveles.

Estructuras de datos y algoritmos en Python

Árboles: árbol binario

Representación gráfica de un árbol binario.

  • Cada nodo tiene:
    • cero hijos
    • un hijo
    • dos hijos
Estructuras de datos y algoritmos en Python

Árboles: implementación de árbol binario

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

Imagen de un árbol con nodos.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Estructuras de datos y algoritmos en Python

Árboles: usos reales

  • Almacenar relaciones jerárquicas
    • Sistema de archivos de un ordenador
    • Estructura de un documento HTML

  • Ajedrez: posibles jugadas del rival

  • Algoritmos de búsqueda y ordenación

Estructuras de datos y algoritmos en Python

Grafos

Imagen de un grafo con nodos.

  • Conjunto de:
    • nodos/vértices
    • enlaces/aristas
  • Los árboles son un tipo de grafo
Estructuras de datos y algoritmos en Python

Grafos: tipos

  • Grafos dirigidos:
    • Tienen dirección específica

Imagen de un grafo dirigido.

Estructuras de datos y algoritmos en Python

Grafos: tipos

  • Grafos no dirigidos:
    • Las aristas no tienen dirección
    • La relación es mutua

Imagen de un grafo no dirigido.

Estructuras de datos y algoritmos en Python

Grafos: tipos

  • Grafos ponderados:
    • valores numéricos asociados a las aristas
    • pueden ser dirigidos o no dirigidos

Imagen de un grafo no dirigido con nombres de ciudades y sus distancias.

Estructuras de datos y algoritmos en Python

Grafos vs. árboles

Árboles

  • No pueden tener ciclos
  • Todos los nodos deben estar conectados

Imagen de un árbol con nodos.

Grafos

  • Pueden tener ciclos
  • Puede haber nodos no conectados

Imagen de un grafo con nodos.

Estructuras de datos y algoritmos en Python

Grafos vs. árboles

Árboles

  • No pueden tener ciclos
  • Todos los nodos deben estar conectados

Imagen de un árbol con nodos.

Grafos

  • Pueden tener ciclos
  • Puede haber nodos no conectados

Imagen de un grafo con nodos. Hay un nodo que no está conectado con el resto.

Estructuras de datos y algoritmos en Python

Grafos: casos de uso reales

  • Relaciones de usuarios en redes sociales
    • amistad
    • sigue
    • me gusta
    • etc.
  • Ubicaciones y distancias
    • optimizar rutas
  • Bases de datos de grafos
  • Algoritmos de búsqueda y ordenación
Estructuras de datos y algoritmos en Python

Grafos: implementación

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

Imagen de un grafo dirigido.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}
Estructuras de datos y algoritmos en Python

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python

Preparing Video For Download...