Muestra las diferencias entre dos versiones de la página.
Próxima revisión Ambos lados, revisión siguiente | |||
algoritmos-oia:grafos:arboles [2017/12/08 13:22] sebach creado |
algoritmos-oia:grafos:arboles [2017/12/08 21:25] sebach |
||
---|---|---|---|
Línea 40: | Línea 40: | ||
Subárbol dado por un nodo: Es el árbol que queda formado por el nodo dado, sus hijos, los hijos de sus hijos, y así hasta llegar a las hojas. La raíz del subárbol es el nodo dado. El subárbol de una hoja es simplemente ese mismo nodo. En el árbol de raíz $1$, el subárbol del nodo $5$ son sólo los nodos $5$ y $6$ con la arista que los une. | Subárbol dado por un nodo: Es el árbol que queda formado por el nodo dado, sus hijos, los hijos de sus hijos, y así hasta llegar a las hojas. La raíz del subárbol es el nodo dado. El subárbol de una hoja es simplemente ese mismo nodo. En el árbol de raíz $1$, el subárbol del nodo $5$ son sólo los nodos $5$ y $6$ con la arista que los une. | ||
+ | |||
+ | |||
+ | ===== Cómo recorrer árboles ===== | ||
+ | |||
+ | Bueno, una manera de recorrerlo es simplemente con BFS o DFS, marcando los visitados y todo igual a como hacíamos antes, ya que eso funciona para cualquier grafo. | ||
+ | |||
+ | Otra manera de recorrerlo es desde la raíz hacia abajo, con una función [[algoritmos-oia:recursion|recursiva]] que se mueva a todos los vecinos del nodo excepto a su padre, que será un parámetro de la función. | ||
+ | Entonces el código quedaría: | ||
+ | |||
+ | <code cpp> | ||
+ | |||
+ | void recorrer(int nodo, int padre){ | ||
+ | for(int i=0; i<grafo[nodo].size(); i++){ | ||
+ | if(grafo[nodo][i]!=padre){ | ||
+ | // Codigo aca o despues de llamar a la funcion, que haga algo | ||
+ | recorrer(grafo[nodo][i], nodo); // Ahora el padre del nodo al que vamos es el nodo actual | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | // Para empezar en la raíz sin que se evite ningún nodo, es común hacer: | ||
+ | recorrer(raiz, -1); | ||
+ | </code> | ||