Download Para el siguiente grafo orientado

1. Para el siguiente grafo orientado:
1
0,4
0,1
0
0,3
4
2
0,5
0,5
0,3
0,5
3
Determinar el arreglo de pesos (wt) del trayecto de peso mínimo entre cada vértice y la
raíz, y el arreglo padres del vértice (st).
a) Para raíz igual al vértice 4.
b) Para raíz igual al vértice 2.
2. Se tiene un grafo definido por un arreglo de elementos.
Edge Elementos[ELEMENTOS]={{0,1,.4},{1,2,.5},{2,3,.5},{3,4,.5},\
{1,4,.1},{0,4,.3},{1,3,.3}};
a) Dibujar el grafo.
b) Determinar el mínimo árbol de cobertura aplicando algoritmo de Kruskal. Indicando
el orden en que se eligen las ramas. Dibujar el árbol.
c) Determinar el mínimo árbol de cobertura aplicando algoritmo de Prim. Indicando el
orden en que se agregan los vértices, y los arreglos de padres y de pesos entre el vértice
y su padre. Dibujar el árbol.
d) Modificar la función de Prim para imprimir el orden en que se eligen los vértices.
3. Se tiene el siguiente arreglo:
10 55 12 42 94 18
Se tiene un algoritmo que ordena en forma ascendente y que imprime luego de cada
etapa la siguiente secuencia:
10 55 12 42 94 18 i= 1
10 12 55 42 94 18 i= 2
10 12 42 55 94 18 i= 3
10 12 42 55 94 18 i= 4
10 12 18 42 55 94 i= 5
a) Determinar el algoritmo usado para ordenar,
b) Determinar solo las modificaciones a éste, para imprimir las líneas anteriores.
4. Se tiene el siguiente arreglo:
31 70 11 7 10
a) Crear un heap basado en el arreglo. Usar los datos en el orden dado, mostrar
paso a paso la inserción de nodos.
b) Ordenar el arreglo usando heapsort. Usar los datos en el orden dado, mostrar
paso a paso el ordenamiento.