Algoritmos

ALGORITMO DFS (Búsqueda en profundidad) Algoritmo de Kruskal

(camino más corto) Sea G= (V, A) un grafo conexo con n vértices, de forma que cada arista a∈A lleva asociado un peso p(a). P1: Hacemosun contador i=0 y elegimos una arista a1 de forma que p(a1) sea mínimo. P2: Si hemos seleccionado las aristas a1,a2,...,ai, seleccionamos la arista ai+1, de forma que p(ai+1) sea mínimo y el subgrafode G, formado por las aristas a0 ,a2,..., ai, ai+1 no contenga ciclos. P3: Reemplazamos i con i+1. Si i=n-1 el subgrafo formado por las aristas a1, a2,..., an-1 es un árbol recubridor de peso mínimo.En caso contrario volvemos al paso 2.

P01: Leer un grafo conexo G=(V,A) P02: V’=φ; A’= φ (vértices y aristas del árbol recubridor) P03: Q={x}, siendo x ∈V un vértice cualquiera del grafo G P04:Marcar x como visitado P05: Añadir el vértice x a V’ P06: Mientras que Q ≠ φ: P07: x= último elemento de Q P08: Si x es adyacente a algún vértice y no visitado P09: Añadir y al final de Q P10: Marcar ycomo visitado P11: Añadir a A’ la arista x – y; añadir a V’ el vértice y P12: En caso contrario P13: Quitar x de la pila Q P14: Retorna el árbol T = (V’,A’)

Algoritmo de Dijkstra
(camino más cortodesde un vértice fijo) Sea G = (V,A) un grafo con n vértices, de forma que cada arista a∈A lleva asociado un peso p(a) y sea v0 un vértice fijo. Esquema del algoritmo: Cada vértice v del grafo llevaráasociado una etiqueta doble (L(v),u). Al final del proceso, L(v) será la distancia del vértice fijo a v, y u será el vértice anterior a v en el camino mínimo v0-v. En un conjunto S se iránintroduciendo los vértices a los que se les haya calculado la distancia a v0. En cada paso del proceso se añadirá un elemento. En cada paso se actualizará la etiqueta de los vértices de S. El proceso terminarácuando en S no queden vértices o los que queden ya no están en la misma componente conexa que v0. Paso 1: Hacemos el contador i=0; S={v0}; u=v0; etiquetamos v0 con (0,-) y el resto de vértices con...