Introducción
¿Qué es un grafo?
¿Qué es un árbol?
¿Qué es recursión?
Aplicaciones reales de grafos y árboles
Formas de representar un grafo
DFS
Análisis de DFS: algoritmo de búsqueda en profundidad
Programando DFS de forma recursiva
Otras formas de programar DFS
Recorridos y profundidad de un Árbol
Sum Root to Leaf Numbers: análisis del problema
Solución de Sum Root to Leaf Numbers
Playground: Sum Root to Leaf Numbers
Programando Sum Root to Leaf Numbers en Golang
Number of Islands: análisis del problema
Solución de Number of Islands
Playground: Number of Islands
Programando Number of Islands en Python
Ejercicios recomendados de DFS
Ejercicios resueltos de DFS
BFS
Análisis de BFS: algoritmo de búsqueda en anchura
Programando BFS con Python
Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema
Solución de Minimum Knights Moves
Playground: Minimum Knights Moves
Programando Minimum Knights Moves con Python
Rotting Oranges: análisis del problema
Solución de Rotting Oranges
Playground: Rotting Oranges
Rotting Oranges con Java
Shortest Bridge Between Islands: análisis del problema
Solución de Shortest Bridge Between Islands
Playground: Shortest Bridge Between Islands
Programando Shortest Bridge Between Islands con Python
Ejercicios recomendados de BFS
Ejercicios resueltos de BFS
Backtrack
Algoritmo de Backtrack
Letter Combinations of a Phone Number: análisis del problema
Solución de Letter Combinations of a Phone Number
Programando Letter Combinations of a Phone Number con C++
Playground: Letter Combinations of a Phone Number
Restore IP Addresses: análisis del problema
Programando Restore IP Addresses con C++
Playground: Restore IP Addresses
Word Search: análisis del problema
Solución de Word Search
Playgrund: Word Search
Programando Word Search JavaScript
Reto: N Queens Puzzle
Ejercicios recomendados de Backtrack
Ejercicios resueltos de Backtrack
Próximos pasos
¿Qué otros algoritmos y tipos de grafos puedes aprender?
¿Quieres más cursos avanzados de algoritmos?
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Aportes 6
Preguntas 0
El cálculo de los números sin utilizar un string lo realizaría de la siguiente manera:
El número que guardé lo multiplicaría por 10 y luego sumaría el valor actual. Ej.:
valor guardado = 1, nuevo valor = 3 ->
1 * 10 = 10, 10 + 3 = 13
valor guardado = 13, nuevo valor = 5 ->
13 * 10 = 130, 130 + 5 = 135
<
# Función para realizar DFS en un grafo dado
lista = []
def dfs(graph, node, visited, num):
num += str(node)
visited[node] = True
# Recorrer todos los nodos adyacentes al nodo actual
for neighbor in graph[node]:
if not visited[neighbor]:
# Si el vecino no ha sido visitado, realizar DFS en él
dfs(graph, neighbor, visited, num)
if len(graph[node]) == 1:
lista.append(int(num))
return False
# Ejemplo de uso
if __name__ == "__main__":
# Grafo representado como listas de adyacencia
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1,6],
5: [2],
6:[4,7],
7:[6,8],
8:[7]
}
# Inicializar un arreglo para llevar un seguimiento de los nodos visitados
visited = [False] * len(graph)
# Realizar DFS desde el nodo 0
dfs(graph, 0, visited,"")
print(sum(lista))
>
Me imagine como seria la estructura en python
tree = [
{
"v": 1,
"child": [
{
"v": 2,
"child": []
},
{
"v": 3,
"child": [
{
"v": 4,
"child": []
}
]
}
]
},
]
def sum_tree(tree, sum_tree_val:str):
sum_tree_val= sum_tree_val + str(tree['v'])
if tree['child'] is not None:
for child in tree['child']:
return sum_tree(child, str(sum_tree_val))
return sum_tree_val
total = 0
for root in tree:
if root.get('child') is not None:
for child in root['child']:
total=total+int(sum_tree(child,sum_tree_val=str(root.get('v'))))
print(total)
Mi solución al problema numericamente
def sum_root_to_leaf(root, max_height):
total_numbers = []
if root.children[0]:
if check_max_depth(root.children[0]) == 1:
total_numbers.append(root.value * (10**(check_max_depth(root.children[0]))) + root.children[0].value)
else:
for child_number in sum_root_to_leaf(root.children[0], max_height):
total_numbers.append(root.value * (10**(check_max_depth(root.children[0]))) + child_number)
if len(root.children) == 2:
if root.children[1]:
if check_max_depth(root.children[1]) == 1:
total_numbers.append(root.value * (10**(check_max_depth(root.children[1]))) + root.children[1].value)
else:
for child_number in sum_root_to_leaf(root.children[1], max_height):
total_numbers.append(root.value * (10**(check_max_depth(root.children[1]))) + child_number)
if max_height == check_max_depth(root):
return sum(total_numbers)
return total_numbers
Hola 😄, les comparto mi solución en js, siento que no es la mejor solución pero lo logré 😅…
.
excerciseSRLN.js:
var soluciones = [];
// Función
const solSRLN = function (raiz, num) {
if (!raiz) {
return "";
}
num += raiz.valor;
solSRLN(raiz.izquierda, num);
solSRLN(raiz.derecha, num);
if (!raiz.izquierda && !raiz.derecha) {
soluciones.push(num);
}
};
// Árbol
export const arbolSRLN = {
valor: 1,
izquierda: {
valor: 3,
izquierda: {
valor: 5,
izquierda: null,
derecha: null,
},
derecha: {
valor: 8,
izquierda: null,
derecha: null,
},
},
derecha: {
valor: 7,
izquierda: null,
derecha: {
valor: 1,
izquierda: null,
derecha: null,
},
},
};
// Prueba
solSRLN(arbolSRLN, "");
var res = soluciones.reduce((acc, item) => Number(item) + acc, 0);
console.log("La solución es: " + res);
.
Output:
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?