IPRJ PROJETO E ANÁLISE DE ALGORITMOS  
LISTA DE EXERCÍCIOS 10  
1
) Uma grande festa vai acontecer no Reino das Nuvens! Finn e Jake estão no castelo  
da Princesa Jujuba planejando qual seria a melhor rota para chegar até a festa.  
A figura abaixo ilustra o mapa da Terra de Ooo:  
Responda as questões abaixo considerando "F" como o vértice inicial. Vértices  
sucessores devem ser dispostos em ordem alfabética.  
a) Realize uma busca em largura no grafo e apresente os valores de π e d  
gerados pelo algoritmo.  
b) Realize uma busca em profundidade no grafo e apresente os valores de π, d  
e f gerados pelo algoritmo.  
c) Construa as árvores de busca geradas pelos algoritmos de busca em  
largura e busca em profundidade.  
d) Considerando "K" como vértice objetivo, realize uma busca de caminho  
mínimo utilizando o algoritmo de Dijkstra e apresente os valores de π e g  
gerados pelo algoritmo. Em seguida apresenta o caminho mínimo  
encontrado.  
2
3
) Em uma busca em largura, o valor d[u] atribuído a um vértice u é independente da  
ordem na qual são dados os vértices em cada lista de adjacências. Verdadeiro ou  
Falso? Justifique sua resposta.  
) Após muitos anos pedalando, Geovane já não têm a mesma disposição para  
encarar as diversas subidas de Nova Friburgo. Como sabemos, Nova Friburgo é  
extremamente montanhosa. Por razões sentimentais, ele não quer mudar para  
uma cidade mais plana. Resolveu, então, que tentaria evitar grandes altitudes em  
seus caminhos.  
Para isso, Geovane obteve com o serviço topográfico da prefeitura um mapa de  
Nova Friburgo, em que cada rua do mapa possui a informação da maior altitude  
encontrada quando trafegada. Tudo que ele precisa fazer agora é implementar um  
programa para determinar rotas que minimizem a altura percorrida entre pares  
(
origem, destino).  
a) Defina e ilustre uma estrutura de dados para armazenar e representar o  
mapa fornecido pela prefeitura.  
b) Apresente o pseudocódigo de um algoritmo que receba como parâmetro  
uma origem e um destino. O algoritmo deve retornar um caminho entre a  
origem e o destino que evite passar por grandes altitudes.  
4
) Para instalar o gcc-4.4 é necessário instalar um conjunto de dependências. A figura  
abaixo ilustra estas dependências:  
a) Utilizando o algoritmo de Kahn, apresente uma ordenação topológica  
definindo uma sequência valida para a instalação do gcc-4.4 e suas  
dependências. Justifique sua resposta apresentando o conteúdo do vetor I e  
da pilha L em todas as iterações do algoritmo.  
b) Utilizando  
o algoritmo de ordenação topológica com busca em  
profundidade, apresente uma ordenação topológica definindo uma  
sequência valida para a instalação do gcc-4.4 e suas dependências.  
Justifique sua resposta apresentando o conteúdo do vetor d e f e da lista L  
no final da execução do algoritmo.  
5
6
) Se existe um caminho de u para v em um grafo orientado F, então qualquer busca  
em profundidade deve resultar em d[v] f[u]. Verdadeiro ou Falso? Justifique sua  
resposta.  
) Durante sua campanha eleitoral, o prefeito de Nova Friburgo prometeu que, até o  
fim de seu mandato, os cidadãos conseguiriam se locomover entre os principais  
pontos do município sem passar por nenhum trecho de estrada de terra (quando  
assumiu o cargo, não era possível ir à nenhum lugar sem passar pelo barro).  
A primeira providência que tomou foi finalizar as diversas vias de ligação que  
haviam sido parcialmente construídas, mas não terminadas. Assim que concluiu  
esta etapa, já com o orçamento reduzido, o prefeito precisa determinar se a  
promessa já fora cumprida ou não.  
a) Defina e ilustre uma estrutura de dados para representar este problema.  
b) Apresente o pseudocódigo de um algoritmo que determine se a promessa  
do prefeito já foi cumprida ou não.  
7
) Considerando os seguintes grafos:  
(
a)  
(b)  
Responda as questões a seguir iniciando os algoritmos pelo vértice "A" e dispondo  
os vértices sucessores em ordem alfabética.  
a) Utilizando o algoritmo de Kosaraju, apresente os componentes fortemente  
conectados de cada um dos grafos na ordem em que eles são encontrados  
pelo algoritmo.  
b) Utilizando o algoritmo de Tarjan, apresente os componentes fortemente  
conectados de cada um dos grafos na ordem em que eles são encontrados  
pelo algoritmo.  
8
9
) Dado um grafo orientado representado por uma lista de adjacências, qual a  
complexidade do processo de calcular o grau de saída de um vértice? Justifique sua  
resposta descrevendo o processo.  
) Considerando o seguinte grafo:  
Responda as questões a seguir iniciando os algoritmos pelo vértice "A" e dispondo  
os vértices sucessores em ordem alfabética.  
a) Utilize o algoritmo de Prim para encontrar uma árvore geradora mínima  
para o grafo. Justifique sua resposta apresentando os valores de π e key  
gerados pelo algoritmo.  
b) Utilize o algoritmo de Kruskal com Conjuntos Disjuntos com Florestas para  
encontrar uma árvore geradora mínima para o grafo. Justifique sua  
resposta apresentando a árvore final presente conjunto disjunto.  
1
0) Você é o responsável por substituir e otimizar a rede e os roteadores de uma  
empresa. Os roteadores transmitem os dados entre si através de cabos de rede e os  
dados transmitidos podem trafegar por uma ou mais rotas para serem entregues  
ao destinatário. Considerando o alto preço dos cabos de rede, você deve projetar a  
nova infraestrutura da rede da empresa de forma com que todos os roteadores  
consigam transmitir dados entre si economizando o máximo possível de cabos de  
rede. A figura abaixo mostra a atual infraestrutura de rede da empresa:  
Apresente o pseudocódigo de um algoritmo para otimizar a infraestrutura de rede  
da empresa e descobrir qual será o custo total gasto com cabos de rede.  
1
1) A transposta de um grafo orientado G = (V, A) é o grafo GT = (V, AT), onde AT={(v,u)  
V×V|(u,v) ∈ A}. Desse modo, GT é G com todas as suas arestas invertidas.  
a) Considerando que G é representado por uma lista de adjacências, descreva  
um algoritmo para calcular GT a partir de G. Em seguida, análise a  
complexidade do algoritmo proposto.  
b) Considerando que G é representado por uma matriz de adjacências,  
descreva um algoritmo para calcular GT a partir de G. Em seguida, análise a  
complexidade do algoritmo proposto.  
1
2) Um grafo orientado G=(V, A) é dito "semiconectado" se, para todos os pares de  
vértices u, v ∈ V, temos u v ou v u. Forneça um algoritmo eficiente para  
determinar se G é ou não "semiconectado". Análise a complexidade do algoritmo  
proposto.