Grafos: Representación y Recorridos (DFS y BFS)

Apuntes

Resumen Algo II - Buchwald 1. División y Conquista: - Dividir un problema en mas de una parte (significativamente, por ejemplo /2) - Hacer algo para solucionar cada parte del problema - Juntar todo Usualmente (no se si siempre) es de forma recursiva. Teorema maestro 2. Ordenamientos comparativos 3. Ordenamientos no comparativos 4. TDAs 1. Pila 2. Cola 3. Lista Enlazada 4. Hash - ~ 5. Árboles ~ - - ~ - S - Post rotación IZQ - DER hay que hacer rotación IZQ - IZQ - Post rotación DER - IZQ hay que hacer rotacion DER - DER 6. Heap 7. Grafos 89 B. REPRESENTACION Las siguientes dos son las representaciones más utilizadas de un gráfo. 1. Matriz de adyacencia 2. Lista de adyacencia 3. Matriz de adyacencia La elección de la representación del gráfo es específica de la situación. Depende totalmente del tipo de operaciones que se realizarán y la facilidad de uso. i. Matriz de adyacencia 90 ii. Lista de adyacencia Cada arista posee una lista simplemente enlazada de a qué vértices está unida. Una lista de adyacencia representa un grafo como un arreglo de listas vinculadas (ese arreglo, en vez de ser un arreglo, también puede ser otra lista y cada nodo de la misma, salen otras listas). El tamaño...