eda2013-1-P3-TurmaB-Gabarito

Prévia do material em texto

P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 1/7 
Aluno(a):__________________________________________Matrícula:____________ 
 
1a) 2.5 
2a) 2.5 
3a) 2.5 
4a) 2.5 
 10.0 
 
I. A prova é individual e sem consulta. 
II. A interpretação faz parte da questão. Em caso de dúvida escreva a dúvida e a sua 
interpretação na resposta. 
III. O tempo de prova é 1:45 h. 
IV. As respostas devem seguir as questões. Caso precise de rascunho use o verso da folha. 
V. A prova pode ser feita a lápis. 
VI. Se necessário, utilize as funções dos tipos abstratos da última folha. 
 
 
 
P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 2/7 
1) (2.5 pontos) Faça uma explicação textual do algoritmo de percurso por largura (BFS ou Breadth 
First Search). Utilize o grafo representado pela lista de adjacências ilustrada abaixo e detalhe os 
passos do algoritmo neste grafo a partir do nó 0. Caso você utilize alguma estrutura auxiliar tipo 
pilha, fila, heap ou partição dinâmica coloque na ilustração como ela ficaria em cada passo. 
 
Resp.: 
Algoritmo: 
 
a) Inicialize uma fila com o nó inicial: F= {0} e marque todos os nós como não visitados. 
b) Enquanto L não for vazia: 
i) Retire o nó que é o primeiro elemento da fila. 
ii) Visite o nó e marque este nó como visitado. 
iii) Inclua na fila todos os nós adjacentes deste nó que não tenham sido visitados nem que já tenham sido 
incluído na fila. Marque os nós colocados na fila como já incluídos. 
 
Passo a passa no exemplo: 
a) F= {0}; status[i]=não_visitado, i=0...6 
b) Visite 0, marque status[0]=visitado. F = φ. 
c) Inclua na fila 1 e 5. F= {1,5}, status[1]=status[5]=incluído. 
d) Visite 1, status[1]=visitado. F= {5}. 
e) Inclua na fila 2 e 6. F= {5,2,6}, status[2]=status[6]=incluído. 
f) Visite 5, status[5]=visitado. F= {2,6}. 
g) Inclua na fila 4. F= {2,6,4}, status[4]=incluído. 
h) Visite 2, status[2]=visitado. F= {6,4}. 
i) Inclua na Fila 3. F= {6,4,3}, status[4]=incluído 
j) Visite 6, status[6]=visitado. F= {4,3}. 
k) Visite 4, status[4]=visitado. F= {3} 
l) Visite 3, status[3]=visitado. F= φ. 
 
Resp: 0,1,5,2,6,4,3 
 
P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 3/7 
2) (2.5 pontos) Faça uma explicação ilustrada de como funciona o algoritmo de Kruskal para 
calcular uma árvore geradora mínima, MST(Minimum Spanning Tree), do grafo mostrado na 
figura abaixo. 
 
Resp: 
a) Crie uma partição dinâmica onde cada vértice é um conjunto isolado. 
Pd={{0},{1},...{7},{8},{9}}. 
 
b) Adicione uma aresta leve (de menor peso dentre as disponíveis). Ao inserir uma aresta faça uma união 
dos dois conjuntos correspondentes aos vértices dela. Pd={{0},{1},...{7,8},{9}}. 
 
c) Continue adicionando uma aresta leve desde que sua inserção não forme ciclos na árvore que está 
sendo gerada. Ou seja, que seus vértices não estejam numa mesma partição. 
Pd={{0},{1},...{6,7,8},{3,9}}. 
 
d) Note que a aresta (7,9) apesar de ser leve não pode ser inserida, pois forma um ciclo (detectado pelo 
fato de 3 e 9 estarem na mesma partição. Pd={{0,1},...{6,7,8,3,9}}.) 
 
e) O algoritmo segue e encontra uma situação onde duas arestas leves tem o mesmo peso e são 
excludentes e daí bifurca para duas soluções equivalentes. 
P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 4/7 
 e 
f) Dai resultam as duas soluções de custo total 37 mostradas abaixo. 
 e 
 
P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 5/7 
3) (2.5 pontos) Um TAD de grafos é implementado com base nas estruturas abaixo. 
typedef struct _grafo Grafo; 
 
typedef struct _aresta Aresta; 
struct _aresta { 
 int no_adjacente; 
 float peso; 
 Aresta* prox; 
}; 
 
struct _grafo { 
 int nnos; /* numero de nos ou vertices */ 
 int* status; /* vetor auxiliar de dimensao nnos */ 
 Aresta** viz; /* viz[i] aponta para a lista de arestas vizinhas do no i */ 
}; 
Programe a função que implementa o algoritmo de percurso por largura (BFS) e que tenha o 
seguinte protótipo: 
void grafoPercorreLargura(Grafo * grafo, int no_inicial); 
Dica: utilize os TADs auxiliares da última pagina. 
Resp: 
 
void grafoPercorreLargura(Grafo * grafo, int no_inicial){ 
 Lista* lst = lstCria(); 
 int i; for (i=0;i<grafo->nnos;i++) grafo->status[i]=0; 
 
 lstInsereInicio(lst,no_inicial); 
 while(!lstEstaVazia(lst)) { 
 int no = lstRemovePrimeiro(lst); 
 Aresta* edg = grafo->viz[no]; /* cabeca da lista de nos vizinhos */ 
 printf("[%d]->", no); 
 grafo->status[no]=2; 
 while(edg!=NULL){ 
 if(grafo->status[edg->no_adjacente]==0) { 
 lstInsereFim(lst,edg->no_adjacente); 
 grafo->status[edg->no_adjacente]=1; 
 } 
 edg=edg->prox; 
 } 
 } 
 printf("NULL\n"); 
} 
 
P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 6/7 
4) (2.5 pontos) Programe a função cujo protótipo é dado abaixo que implementa o algoritmo de 
Dijkstra no TAD descrito na questão anterior. 
void grafoDijkstra(Grafo* graph, int no_origem); 
 
Resp: 
 
static int find_smallest(int n, float* vet, char* visited) { 
 int i,is=-1; 
 float min = FLT_MAX; 
 for (i=0;i<n;i++) { 
 if (!visited[i]&&vet[i]<min) { 
 is = i; 
 min = vet[i]; 
 } 
 } 
 return is; 
} 
 
void grafoMostraDijkstra(Grafo* grafo, int source) { 
 float* dist = (float*) malloc(grafo->nnos*sizeof(float)); 
 int i,current; 
 Aresta* edg; 
 for (i=0; i<grafo->nnos; i++) { 
 dist[i]=FLT_MAX; 
 grafo->cor[i]=0; 
 } 
 current=source; dist[source]=0; 
 while (current!=-1) { 
 grafo->cor[current]=1; 
 for (edg=grafo->viz[current]; edg!=NULL; edg=edg->prox) { 
 float d_novo = dist[current]+edg->peso; 
 if (dist[edg->no_adjacente]>d_novo) 
 dist[edg->no_adjacente]=d_novo; 
 } 
 current=find_smallest(grafo->nnos,dist,grafo->cor); 
 } 
 printf("no (dist) calculados por Dijkstra:\n"); 
 for (i=0; i<grafo->nnos; i++) { 
 printf("%d (%g)\n",i,dist[i]); 
 } 
 free(dist); 
} 
P3 INF1010 - Estruturas de Dados Avançadas 2013.1 
1jul2013 Página 7/7 
TADs – Tipos Abstratos que podem ser utilizados como funções auxiliares. 
 
typedef struct _lista Lista; 
Lista* lstCria (void); 
Lista* lstLibera (Lista* lst); 
int lstInsereInicio (Lista* lst, int info); 
int lstInsereFim (Lista* lst, int info); 
int lstRemovePrimeiro (Lista* lst); 
int lstEstaVazia (Lista* lst); 
void lstMostra (Lista* lst, char* titulo); 
 
typedef struct heap Heap; 
Heap* heap_cria(int max_size); 
Heap* heap_libera(Heap* heap); 
void heap_insere(Heap* heap, int info, float prioridade); 
int heap_remove(Heap* heap); 
 
typedef struct partdin PartDin; 
PartDin* pd_cria(int max); 
int pd_busca(PartDin* pd, int x); 
int pd_union(PartDin* pd, int x, int y); 
void pd_show(PartDin* pd); 
PartDin* pd_libera(PartDin* pd);