Repaso grafos 2024-3.pptx estructuras de datos

Estructuras de datos

1. Repaso grafos Estructuras de datos

2. Algoritmo de Djkstra 1. Dada la siguiente matriz de adyacencia donde los vértices son: V={0,1,2,3,4,5,6,7} Partiendo del nodo 0, determinar la etiqueta del vértice 5 al final del algoritmo:

3. Algoritmo de Djkstra 2. Dada la siguiente matriz de adyacencia donde los vértices son: V={0,1,2,3,4,5,6,7} Partiendo del nodo 0, Indique la secuencia de nodos para ir de 0 a 7 al final del algoritmo:

4. Algoritmo de Prim 3. Dada la siguiente matriz de adyacencia donde los vértices son: V={0,1,2,3,4,5,6,7} Determine los arcos que forman el árbol de expansión mínima partiendo desde el vértice 0:

5. 4. Se aplica la siguiente función sobre la lista: void func (Origen * cab ){ Origen* aux = cab ; int n=0; while ( aux !=NULL){     n=n+( aux -> sec ->peso);     aux = aux -> sig ; } cout <<n; } ¿Qué valor imprime? Los nodos de las sublistas son de tipo Destino y tienen los atributos: int peso string dato Destino* sig Los nodos de la lista principal son de tipo Origen y tienen los atributos: Origen * sig Destino* sec string dato

6. 5. Se tiene la siguiente función para determinar el grado de entrada de un nodo: Complete la función con las instrucciones faltantes int gradoE (Origen* cab,string busc ){ Origen* temp1= cab ; Destino* temp2; int x=0;       while (temp1!=NULL){          [[1????]]       while (temp2!=NULL){           if ([[2?????]])                  [[3?????]];      temp2=temp2-> sig ; }      [[4??????]];     } return x; }

7. Respuestas 1. [8,2] 2. 0-3-7 3. (0,2) (0,4) (1,6) (2,5) (3,5) (5,7) (6,7) 4. 8 5. Origen* temp1= cab ; Destino* temp2; int x=0; while (temp1!=NULL){ temp2=temp1‑> sec ; while (temp2!=NULL){ if (temp2‑> nom == busc ) x++ ; temp2=temp2-> sig ; } temp1=temp1‑> sig ; } return x; }