UNIVESP - 2020 - Exercícios de apoio - Semana 7_ ESTRUTURAS DE DADOS - EID001

Prévia do material em texto

EXERCÍCIOS DE APOIO
Apenas para praticar. Não vale nota.
Modifique as funções para Busca em Profundidade em um grafo (além de qualquer outra
estrutura que necessite de mudança) de modo que, em vez de uma caminhada, elas
efetivamente busquem por uma chave presente em um nó. Ou seja, sua busca deve parar
quando tiver visitado todos os nós ou um nó contendo a chave procurada. Ela, então, deve
retornar true se encontrar o nó contendo a chave, ou false caso a chave não esteja no grafo.
Primeiro, faz-se necessário modificar a definição do vértice para acomodar a chave:
 
typedef struct vertice {
 int chave;
 ADJACENCIA *cab;
} VERTICE;
 
Depois, precisamos criar um grafo em que os vértices têm chaves. Uma possibilidade é:
 
GRAFO *criaGrafo(int v, int *chaves) {
 GRAFO *g = (GRAFO *)malloc(sizeof(GRAFO));
 g->vertices = v;
 g->arestas = 0;
 g->adj = (VERTICE *)malloc(v*sizeof(VERTICE));
 int i;
 for (i=0; i<v; i++) {
 g->adj[i].chave = chaves[i];
 g->adj[i].cab = NULL;
 }
 return(g);
}
 
Em seguida, modificamos as funções para busca, para que retornem o que é pedido:
 
bool visitaP(GRAFO *g, int u, int *cor, int chave) {
 bool achou = false;
1.
 
 if (g->adj[u].chave == chave) return(true);
 cor[u] = AMARELO;
 ADJACENCIA *v = g->adj[u].cab;
 while (v) {
 if (cor[v->vertice] == BRANCO) {
 achou = visitaP(g,v->vertice,cor,chave);
 if (achou) return(true);
 }
 v = v->prox;
 }
 cor[u] = VERMELHO;
 return(false);
}
 
bool profundidade(GRAFO *g, int chave) {
 bool achou = false;
 int cor[g->vertices];
 
 int u;
 for (u=0; u<g->vertices; u++) {
 cor[u] = BRANCO;
 }
 for (u=0; u<g->vertices; u++) {
 if (cor[u] == BRANCO) {
 achou = visitaP(g,u,cor,chave);
 if (achou) return(true);
 }
 }
 return(false);
}
 
Estas podem, então, ser testadas assim (o restante das funções e estruturas permaneceram
inalterados):
 
int main() {
 int chaves[] = {1,12,5,3,7};
 GRAFO * gr = criaGrafo(5,chaves);
 criaAresta(gr,0,2,0);
 criaAresta(gr,0,1,0);
 criaAresta(gr,1,3,0);
 criaAresta(gr,2,3,0);
 criaAresta(gr,3,4,0);
 
 printf("%d\n",profundidade(gr,14));
}
 
 
Considere a representação por matriz de adjacências, conforme o que segue:
 
#define true 1
#define false 0
typedef int bool;
typedef int TIPOPESO;
 
typedef struct grafo {
 int vertices;
 int arestas;
 /* Matriz de adjacências (com pesos) */
 TIPOPESO **adj;
} GRAFO;
 
Implemente a seguinte função, usando essa representação:
 
/*
 Cria um grafo com v vértices e 0 arestas, retornando
 seu endereço na memória.
*/
2.
GRAFO *criaGrafo(int v);
 
 
Uma possível implementação é:
 
GRAFO *criaGrafo(int v) {
 GRAFO *g = (GRAFO *)malloc(sizeof(GRAFO));
 g->vertices = v;
 g->arestas = 0;
 // cria o arranjo que representará as linhas
 g->adj = (TIPOPESO **)malloc(v*sizeof(TIPOPESO *));
 // cria cada uma das linhas
 int i;
 for (i=0; i<v; i++){
 g->adj[i] = (TIPOPESO *)malloc(v*sizeof(TIPOPESO));
 // mostra não haver aresta (uso -1 para ausência)
 int j;
 TIPOPESO *p = g->adj[i];
 for (j=0; j<v; j++) {
 p[j] = -1;
 }
 }
 return(g);
}
 
 
Considere a representação por matriz de adjacências e a função implementada na questão
2. Implemente a seguinte função, usando essa representação:
 
/*
 Adiciona aresta no grafo gr, indo do vértice inicial vi
 ao vértice final vf, com peso p. vf e vi são os índices
3.
 dos respectivos vértices na matriz de adjacências.
 Retorna true se teve sucesso e false se os vértices não
 existirem ou o grafo for null. Cria apenas a aresta
 (vi,vf), ou seja, dirigida.
*/
bool criaAresta(GRAFO *gr, int vi, int vf, TIPOPESO p);
 
 
Uma possível implementação é:
 
bool criaAresta(GRAFO *gr, int vi, int vf, TIPOPESO p) {
 if (!gr) return(false);
 if ((vf<0) || (vf >= gr->vertices)) return(false);
 if ((vi<0) || (vi >= gr->vertices)) return(false);
 
 TIPOPESO *aux = gr->adj[vi];
 aux[vf] = p;
 
 gr->arestas++;
 return(true);
}
 
Caso deseje imprimir o grafo, pode-se usar esta função:
 
void imprime(GRAFO *gr) {
 printf("Vértices: %d. Arestas: %d.\n",gr->vertices,
 gr->arestas);
 int i,j;
 for (i=0; i<gr->vertices; i++)
 printf("\tv%d",i);
 printf("\n");
 for (i=0; i<gr->vertices; i++) {
 printf("v%d:",i);
 TIPOPESO *p = gr->adj[i];
 for (j=0; j<gr->vertices; j++)
 printf("\t%d ",p[j]);
 printf("\n");
 }
}
 
 
Considere o código a seguir:
 
void f2(GRAFO *g, int u, int *aux) {
 aux[u] = 1;
 printf("%d ",u);
 ADJACENCIA *v = g->adj[u].cab;
 while (v) {
 if (aux[v->vertice] == 0)
 f2(g,v->vertice,aux);
 v = v->prox;
 }
 aux[u] = 2;
}
int f1(GRAFO *g) {
 int aux[g->vertices];
 int i;
 for (i=0; i<g->vertices; i++)
 aux[i] = 0;
 f2(g,0,aux);
}
 
O que esse programa imprime se passarmos como parâmetro para f1 o grafo da questão 4,
representado como lá descrito? (Assuma as estruturas para grafos, vistas em videoaula,
para a representação descrita na questão 4)
O programa imprimirá a busca em profundidade, ou seja:
0 1 3 4 6 8 9 10 7 5 2.
4.
 
Redes modelam o espaço geográfico como um conjunto de nós, conectados por arcos, em
que ambos possuem atributos. Um dos atrativos do modelo de redes é o suporte da teoria
de grafos. Um grafo pode ser representado na forma de listas ou de matrizes de
adjacências. Considere o grafo ilustrado na figura a seguir.
 
Após análise do grafo acima, verifica-se que a matriz de adjacências correspondente é a
seguinte:
5.
a.
b.
A resposta correta é: “b” 
c.
d.
e.
Considere o grafo dirigido apresentado na figura a seguir, cuja matriz de adjacências é
apresentada ao lado. A função dist_max (int u, int v, int M[][]) retorna 1 caso exista um
caminho do vértice u ao vértice v composto por uma ou duas arestas. A função recebe como
6.
parâmetro a matriz M, sendo que M[i][j] == 1 se existe uma aresta que liga i a j, ou 0 em
caso contrário. A função dist_max3 int u, int v, int M[][]) utiliza a função dist_max e
responde se existe um caminho de, no máximo, três arestas entre os vértices u e v.
int dist_max (int u, int v, int n, int M[][]) {
 if (M[u][v])
 return 1;
 int i;
 for (i = 0; i < n; i++)
 if (M[u][i] && M[i][v])
 return 1;
 return 0;
}
 
int dist_max3 (int u, int v, int n, int M[][]) {
 if (________________)
 return 1;
 int i;
 for (i = 0; i < n; i++)
 if (M[u][i] && __________________________)
 return 1;
 return 0;
}
 
Assinale a alternativa que preenche adequadamente a função dist_max3 (int u, int v, int n,
int M[][]):
A resposta correta é: dist_max (u,v,n,M), dist_max (u,v,n,M)
M[u][v]), dist_max (u,v,n,M)a.
dist_max (u,v,n,M), dist_max (u,v,n,M)b.
dist_max (u,v,n,M), M[u,v]c.
M[u][v]), M[v][i])d.
M[u][v]), M[i][v])e.
Resolução 
Considere o grafo dirigido apresentado na figura a seguir, cuja matriz de adjacências é
apresentada ao lado. A função dist_max (int u, int v, int M[][]) retorna 1 caso exista um
caminho do vértice u ao vértice v composto por uma ou duas arestas. A função recebe como
parâmetro a matriz M, sendo que M[i][j] == 1 se existe uma aresta que liga i a j, ou 0 em
caso contrário. A função dist_max3 int u, int v, int M[][]) utiliza a função dist_max e
responde se existe um caminho de, no máximo, três arestas entre os vértices u e v.
int dist_max (int u, int v, int n, int M[][]) {
 if (M[u][v])
 return 1;
 int i;
 for (i = 0; i < n; i++)
 if (M[u][i] && M[i][v])return 1;
 return 0;
}
 
int dist_max3 (int u, int v, int n, int M[][]) {
 if (________________)
 return 1;
 int i;
 for (i = 0; i < n; i++)
 if (M[u][i] && __________________________)
 return 1;
 return 0;
}
 
 
 
Considere o grafo a seguir. Deseja-se realizar uma busca pelo vértice 9, partindo do vértice
1. A sequência dos vértices visitados pela busca em largura e profundidade,
respectivamente, é dada por:
A resposta correta é: Busca Largura:1,4,8,0,2,3,5,7,6,9; Busca Profundidade:
1,4,8,0,2,5,6,3,7,9
7.
Busca Largura: 1,4,8,0,2,5,6,3,7,9; Busca Profundidade: 1,8,0,2,3,5,7,6,9a.
Busca Largura:1,4,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,2,5,6,3,7,9b.
Busca Largura: 1,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,2,5,6,3,7,9c.
Busca Largura: 1,4,8,0,5,2,6,3,7,9; Busca Profundidade: 1,8,0,2,3,5,7,6,9d.
Busca Largura: 1,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,5,2,6,3,7,9e.
Considere agora a representação de grafos por listas de adjacências (declaração em
linguagem C) a seguir:
#define MaxNumVertices 1000
typedef int elem;
typedef struct no_lst {
 int v;
 elem peso;
 struct no_lst *prox; } no_lista;
typedef struct {
 no_lista *LAdj[MaxNumVertices + 1];
 int NumVertices; } Grafo;
 
A função peso_aresta(v1,v2) retorna o peso de uma aresta no grafo direcionado, caso ela
exista. Assumimos que os pesos são valores >= 0. Assim, a função deve retornar 0 se a
8.
aresta não existir, retornar o seu peso se ela existir, ou retornar -1 se ocorrer algum erro.
 
int peso (Grafo *G, int V1, int V2) {
 if ((V1 < 1) || (V1 > G->NumVertices) || (V2 < 1) || (V2 > G->NumVertices)) {
 return -1;
 } else {
 no_lista *aux = G->LAdj[V1];
 while (aux != NULL)
 if (_______________)
 return (_____________);
 else aux = aux->prox;
 return (_______________);
 }
 }
 
Assinale a alternativa que completa adequadamente a função peso (Grafo *G, int V1, int
V2):
A resposta correta é: aux->v == V2, aux->peso;0 
Resolução 
int peso_aresta(Grafo *G, int V1, int V2) {
 if ((V1 < 1) || (V1 > G->NumVertices) || (V2 < 1) || (V2 > G->NumVertices)) {
 return -1;
 } else {
 no_lista *aux = G->LAdj[V1];
 while (aux != NULL)
 if (aux->v == V2)
 return (aux->peso);
 else aux = aux->prox;
 return (0);
 }
 }
aux->v == V2, aux->peso;0a.
aux->v == V1, aux->peso;0b.
aux->v == V2, 0, aux->pesoc.
aux->v == V1, 0, aux->pesod.
V2 == V1, aux->peso, 0e.
 
 
Considere o grafo a seguir.
O menor caminho entre A e F obtido pelo Algoritmo de Dijkstra
(https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra) é dado por:
A resposta correta é: Custo igual a 12, Caminho: A, C, B, D, E, F
9.
Custo igual a 12, Caminho: A, C, B, D, E, Fa.
Custo igual a 13, Caminho: A, B, D, E, Fb.
Custo igual a 10, Caminho: A, C, B, D, E, Fc.
Custo igual a 12, Caminho: A, B, D, E, Fd.
Custo igual a 14, Caminho: A, C, E, Fe.
Redes modelam o espaço geográfico como um conjunto de nós, conectados por arcos, em
que ambos possuem atributos. Um dos atrativos do modelo de redes é o suporte da teoria
de grafos. Um grafo pode ser representado na forma de listas ou de matrizes de
adjacências. Considere o grafo ilustrado na figura a seguir.
 
Após análise do grafo acima, verifica-se que a matriz de adjacências correspondente é a
seguinte:
10.
https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra
a.
b.
c.
d.
e.
Resposta correta:
Considere o grafo dirigido apresentado na figura a seguir, cuja matriz de adjacências é
apresentada ao lado. A função dist_max (int u, int v, int M[][]) retorna 1 caso exista um
caminho do vértice u ao vértice v composto por uma ou duas arestas. A função recebe como
parâmetro a matriz M, sendo que M[i][j] == 1 se existe uma aresta que liga i a j, ou 0 em
caso contrário. A função dist_max3 int u, int v, int M[][]) utiliza a função dist_max e
responde se existe um caminho de, no máximo, três arestas entre os vértices u e v.
int dist_max (int u, int v, int n, int M[][]) {
 if (M[u][v])
 return 1;
 int i;
 for (i = 0; i < n; i++)
 if (M[u][i] && M[i][v])
 return 1;
 return 0;
}
 
int dist_max3 (int u, int v, int n, int M[][]) {
 if (________________)
 return 1;
 int i;
 for (i = 0; i < n; i++)
11.
 if (M[u][i] && __________________________)
 return 1;
 return 0;
}
 
Assinale a alternativa que preenche adequadamente a função dist_max3 (int u, int v, int n,
int M[][]):
Resposta correta: dist_max (u,v,n,M), dist_max (u,v,n,M)
M[u][v]), dist_max (u,v,n,M)a.
dist_max (u,v,n,M), dist_max (u,v,n,M)b.
dist_max (u,v,n,M), M[u,v]c.
M[u][v]), M[v][i])d.
M[u][v]), M[i][v])e.
Considere o grafo a seguir. Deseja-se realizar uma busca pelo vértice 9, partindo do vértice
1. A sequência dos vértices visitados pela busca em largura e profundidade,
respectivamente, é dada por:
Resposta correta: Busca Largura:1,4,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,2,5,6,3,7,9
12.
Busca Largura: 1,4,8,0,2,5,6,3,7,9; Busca Profundidade: 1,8,0,2,3,5,7,6,9a.
Busca Largura:1,4,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,2,5,6,3,7,9b.
Busca Largura: 1,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,2,5,6,3,7,9c.
Busca Largura: 1,4,8,0,5,2,6,3,7,9; Busca Profundidade: 1,8,0,2,3,5,7,6,9d.
Busca Largura: 1,8,0,2,3,5,7,6,9; Busca Profundidade: 1,4,8,0,5,2,6,3,7,9e.
Considere agora a representação de grafos por listas de adjacências (declaração em
linguagem C) a seguir:
#define MaxNumVertices 1000
13.
typedef int elem;
typedef struct no_lst {
 int v;
 elem peso;
 struct no_lst *prox; } no_lista;
typedef struct {
 no_lista *LAdj[MaxNumVertices + 1];
 int NumVertices; } Grafo;
 
A função peso_aresta(v1,v2) retorna o peso de uma aresta no grafo direcionado, caso ela
exista. Assumimos que os pesos são valores >= 0. Assim, a função deve retornar 0 se a
aresta não existir, retornar o seu peso se ela existir, ou retornar -1 se ocorrer algum erro.
 
int peso (Grafo *G, int V1, int V2) {
 if ((V1 < 1) || (V1 > G->NumVertices) || (V2 < 1) || (V2 > G->NumVertices)) {
 return -1;
 } else {
 no_lista *aux = G->LAdj[V1];
 while (aux != NULL)
 if (_______________)
 return (_____________);
 else aux = aux->prox;
 return (_______________);
 }
 }
 
Assinale a alternativa que completa adequadamente a função peso (Grafo *G, int V1, int
V2):
Resposta correta: aux->v == V2, aux->peso;0
aux->v == V2, aux->peso;0a.
aux->v == V1, aux->peso;0b.
aux->v == V2, 0, aux->pesoc.
aux->v == V1, 0, aux->pesod.
V2 == V1, aux->peso, 0e.
Considere o grafo a seguir.14.
 
ESCONDER
GABARITO
O menor caminho entre A e F obtido pelo Algoritmo de Dijkstra
(https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra) é dado por:
Resposta correta: Custo igual a 12, Caminho: A, C, B, D, E, F
https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra