Algoritmos para Grafos

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL 
INSTITUTO DE INFORMÁTICA 
Bacharelado em Ciência da Computação e 
Engenharia da Computação 
INF 01203 – Estruturas de Dados 
Profa. Renata Galante (galante@inf.ufrgs.br ) 
Caminho Mínimo e Máximo e Algoritmos para Grafos 
Nomes:		 ___________________________________________________	
	 ___________________________________________________	
	 ___________________________________________________	
	
1	 –	 Considerando	 o	 algoritmo	 de	 “Caminho	 Mínimo”	 e	 considerando	 como	 ponto	 de	
partida	o	vértice	Porto	Alegre,	responda.	
	
Qual	 é	 o	 valor	 (somatório	 das	 distâncias)	 do	 menor	 caminho	 de	 Porto	 Alegre	 até	
Salvador?		_______________	
	
Em	que	ordem	cada	vértice	do	grafo	é	inserido	na	nuvem	para	a	realização	do	cálculo.		
	
_____________,	_____________,	_____________,	_____________,	_____________	
	
2	–	Dado	um	grafo	G	conexo	e	valorado	é	possível	afirmar	que	o	caminho	mais	 curto	é	
necessariamente	 único?	 Apresente	 argumentos	 a	 favor	 ou	 contra	 a	 afirmação	
apresentada.	
	
	
	
	
3	-		O	grafo	abaixo	ilustra	uma	ferrovia	com	7	pátios	e	suas	respectivas	distâncias:	
	
Para	fins	de	economia	de	custos,	os	carregamentos	devem	ser	transportados	na	ferrovia	
pelos	 menores	 caminhos	 existentes	 possíveis	 entre	 a	 sua	 origem	 e	 o	 seu	 destino.	
Considerando	que	na	notação	[x,y],	x	representa	o	pátio	de	origem	e	y	representa	o	pátio	
de	 destino,	 o	menor	 caminho	 (menor	 custo)	 entre	 x	 e	 y	 é	 apresentado	 por?	Assinale	 a	
alternativa	correta.		
	
(				)		[2,6]	−	Caminho:	2	4	5	3	6.			
(				)		[1,6]	−	Caminho:	1	3	6.			
(				)		[7,1]	−	Caminho:	7	5	3	1.		
(				)		[4,6]	−	Caminho:	4	1	3	6.			
(				)		[6,2]	−	Caminho:	6	3	1	4	2.	
	
	
4	–	Qual	é	a	principal	diferença	entre	o	algoritmo	de	caminho	mínimo	e	o	algoritmo	de	
árvore	geradora	mínima	(visto	na	última	aula).		
	
	
	
	
	
5	–	Explique	sucintamente	o	que	faz	o	código	a	seguir.	
int whatIsHappening(int grafo[num_v][num_v]){ 
 int i,k,c; 
 for(i=0;i<num_v;i++) { 
 c = 0; 
 for(k=0;k<num_v;k++) 
 if (grafo[i][k] == 1) 
 c++; 
 if (c == 0) return 1; 
 } 
 return 0; 
} 
	
	
	
	
6	–	Explique	sucintamente	o	que	faz	o	código	exibe	no	print.	
void whateverItIs (int grafo[num_v][num_v], int v){ 
 int i,respA=0,respB=0; 
 if (v < num_v ) 
 for(i=0;i<num_v;i++) { 
 respA = respA + grafo[v][i]; 
 respB = respB + grafo[i][v]; 
 } 
 printf("%d %d", respA, respB); 
}	
	
	
	
7	–	Explique	sucintamente	o	que	faz	o	código	a	seguir..	
int nothingToSay (int grafo[max+1][max+1], int i, int j) { 
int k, controle; 
 for (k=1; k<=max; k++){ 
 if (grafo[i][k] && (k!=j)) 
 controle = nothingToSay (grafo, k, j); 
 else 
 if (k==j) 
 return 1; 
 } 
 return controle; }