Aun no tengo nada

1

B´squeda en Amplitud (BFS) u
BFS genera un ´rbol de descubrimiento de un grafo G, para esto cada v´rtice v tiene los siguientes a e campos: v .α: lista de adyacencia de v. v .color : color parav (blanco, plomo, negro) v .π: padre de v en el ´rbol de descubrimiento a v .d : paso de descubrimiento de v (distancia desde la ra´ del ´rbol de descubrimiento) ız a BFS(G, s) for each u ∈ V (G) −{s} do u.color := blanco u.d := ∞ u.π := nil s.color := plomo s.d := 0 s.π := nil Q.Enqueue(s) while Q.IsEmpty() = false do u := Q.head for each v ∈ u.α do if v .color = blanco then v .color := plomo v.d := u.d +1 v .π := u Q.Enqueue(v) Q.Dequeue() u.color := negro

2

B´squeda en Profundidad (DFS) u
DFS genera un “bosque” de descubrimiento de un grafo G o “grafo predecesor” de G, para estocada v´rtice v tiene los siguientes campos: e v .α: lista de adyacencia de v. v .color : color para v (blanco, plomo, negro) v .π: padre de v (o predecesor de v) en el grafo predecesor v .d : tiempode descubrimiento de v (tiempo en el que por primera vez se visita) v .f : tiempo de finalizaci´n de v (tiempo en el que se han visitados todos los descencientes en o el ´rbol de descubrimiento) aDFS(G) for each u ∈ V (G) do u.color := blanco u.π := nil t := 0 for each u ∈ V (G) do if u.color = blanco then Visita(u) Visita(u) u.color := plomo t := t + 1 u.d := t for each v ∈ u.α do if v .color =blanco then v .π := u Visita(v) u.color := negro t := t + 1 u.f := t

3

´ Arboles de Cobertura de Costo M´ ınimo
Prim(G, w, r) Q := V (G) for each u ∈ Q do u.k := ∞ r .k := 0 r .π := nil whileQ.IsEmpty() = false do u := Q.Extract-Min() for each v ∈ u.α do if v ∈ Q ∧ w(u, v) < v .k then v .π := u v .k := w(u, v) Kruskal(G, w) A := o / for each v ∈ V (G) do Make-Set(v) ordena las aristas enE(G) en orden creciente seg´n el peso w u for each (u, v) ∈ E(G) en el orden anterior do if Find-Set(u) = Find-Set(v) then A := A ∪ {(u, v)} Union(u, v) return A

4

Caminos de M´ ınimo Costo...