ANHANGUERA EDUCACIONAL S
FACULDADE ANHANGUERA DE TAUBAT UNIDADE II
ATIVIDADES PRTICAS SUPERVISIONADAS
Estrutura de DadosProf.:
2 Bimestre / 2014
Curso: Cincia da ComputaoSemestre: 3 e 4 - Turma A Ano: 2014
Taubat02 de Dezembro de 2014
ETAPA 4.
Aula-tema: Grafos.
Passo 2 (Equipe).
Fazer a discusso da leitura do captulo do livro texto e do
material de aula, que ser utilizado como base para a implementao de
rotas de voos por meio da estrutura grafo, com destaque para:
1. Representao de Grafos em C.
Os vrtices de um grafo sero representados por nmeros inteiros no
intervalo 0..v-1. O conjunto de vrtices ser, portanto, 0 1 2
3...v-1.Vrtices so representados por objetos do tipo Vertex.
#define Vertex int
Os arcos dos grafos sero representados por structs do tipo Edge.
Um objeto do tipo Edge representa um arco com ponta inicial v e
ponta final w.
typedef struct{Vertex v;Vertex w;} Edge;
Se e um arco ento e.v a ponta inicial e e.w a ponta final do
arco. A construo de arcos ficar a cargo de uma funo EDGE. A funo
EDGE recebe dois vrtices v e w e devolve um arco com ponta inicial
v e ponta final w.
Edge EDGE (Vertex v, Vertex w){Edge e;Teoria dos Grafos 3e.v =
v;e.w = w;return e;}
2. Algoritmo de Menor Caminho.
O algoritmo de Dijkstra identifica, a partir de um vrtice do
grafo, qual o custo mnimo entre esse vrtice e todos os outros do
grafo. No incio, o conjunto S contm somente esse vrtice,
chamadoorigem. A cada passo, selecionamos no conjunto de vrtices
sobrando, o que o mais perto da origem. Depois atualizamos, para
cada vrtice sobrando, a sua distncia em relao origem. Se passando
pelo novo vrtice acrescentado, a distncia fica menor, essa nova
distncia que ser memorizada.Suponhamos que o grafo representado por
uma matriz de adjacncia onde no existe aresta entre dois vrtices.
Suponhamos tambm que os vrtices do grafo so enumerados de 1 atn,
isto , o conjunto de vrtices N= {1, 2, ...,n}. Utilizaremos tambm
um vetorD[2..n]que conter a distncia que separa todo vrtice do
vrtice 1 (o vertce do grafo que o vertice 1 escolhido
arbitrariamente). Eis o algoritmo:
funoDijkstra(L = [1..n, 1..n]:grafo): vetor[2..n]C:= {2,3,...,n}
{ImplicitamenteS=N-C}Parai:= 2atn:D[i]:= L[1,i]Repetirn-2vezes:v:=
Elemento deCque minimizaD[v]C:= C - {v}Paracada elementowde C:D[w]
:= min(D[w],D[v]+ L[v,w])RetornarD
3. Representao por meio de Matriz de Adjacncia.
Seja G = (V, E) um grafo com n vrtices, onde n 1. Supomos que os
vrtices so numerados 1, 2, ..., |V| de alguma maneira arbitrria.
Ento a representao de matriz de adjacncias de um grafo G consiste
em uma matriz |V| |V| A = (aij) tal que A(i,j) = 1 se a borda (vi,
vj)({vi, vj} para um grafo dirigido1) fica em E(G).A matriz de
adjacncias para um grafo no-dirigido2 simtrica, pois a borda (vi,
vj) est em E(G), se a borda (vi, vj) tambm est em E(G). A matriz de
adjacncias de um grafo dirigido no necessita ser simtrica. de n2
bits o espao necessrio para representar um grafo, usando a matriz
de adjacncias.A representao de matriz de adjacncias pode ser usada
no caso de grafos ponderados3. Por exemplo, se G = (V, E) um grafo
ponderado com funo peso de aresta w, o peso w(u, v) da aresta (u,
v) E simplesmente armazenado como a entrada na fila u e na coluna v
da matriz de adjacncias.A simplicidade de uma matriz de adjacncias
pode torn-la prefervel quando os grafos so razoavelmente pequenos.
Em lugar de usar uma palavra de memria de computador para cada
entrada da matriz, a matriz de adjacncias usa somente um bit por
entrada.
4. Caminhamento em Amplitude.
Em uma busca em largura a partir de um vrticev, esperamos que
todos os vizinhos devsejam visitados antes de continuar a busca
mais profundamente. Contrariamente busca em profundidade, o
algoritmo de busca em largura no recursivo. O algoritmo de busca em
largura semelhante ao algoritmo de busca em profundidade. A
principal diferena que usamos um filaFao invs de uma pilha:
procedimentoBusca-Largura(v: vrtice)InicializarFMarcarvcomo
visitadoColocarvno final deFEnquantoFno vazio:u:= primeiro elemento
deFRetirarudeFParacada vrticewadjacente au:Sewno foi
visitado:Marcarwcomo visitadoColocarwno final deF
Neste caso preciso um programa para lanar a busca:
procedimentoBusca(G: Grafo)Paracada vrticevdeG:Marcarvcomo no
visitadoParacada vrticevdeG:Sevno foi visitado:{Busca-Largura ou
Busca-Prof-iter}(v)
5. Caminhamento em Profundidade.
Seja um grafo G = (V,E) que contmnvrtices. Seja tambem uma
representao que indica, para cada vrtice, se ele foi visitado ou
no. Eis uma verso recursiva do algoritmo de busca em profundidade
que visita todos os vrtices:
procedimentoBusca(G: Grafo)ParaCada vrticevde G:Marquevcomo no
visitadoParaCada vrticevde G:Sevno foi
visitado:Busca-Prof(v)procedimentoBusca-Prof(v:vrtice)Marquevcomo
visitadoParaCada vrticewadjacente av:Sewno foi
visitado:Busca-Prof(w)
Note que esse algoritmo funciona com um grafo desconexo. Se j
sabemos que o grafo conexo, podemos chamar diretamente a
funoBusca-Prof, escolhendo arbitrariamento um vrtice inicial.
Passo 3 (Equipe).
#include#include#include
void menu();void selecao();void montargrafo();void
caminhagrafo();
int main(){ menu(); return 0; system("pause");}
void menu(){ system("title Empresa VOEBEM"); printf("\t Empresa
VOEBEM \n"); printf(" ____________________________\n"); printf(" |
Escolha uma opcao abaixo |\n"); printf("
|--------------------------|\n"); printf(" | 1 - Cadastrar cidades
|\n"); printf(" | 2 - Melhor rota |\n"); printf(" | 0 - Sair |\n");
printf(" |__________________________|\n"); selecao();}
void selecao(){ int opcao;
printf("\n Digite uma das opcoes: "); scanf("%i",
&opcao);
switch (opcao) { case 1: montargrafo(); menu(); break;
case 2: caminhagrafo(); menu(); break;
case 0: system("pause"); exit(0); break;
default: printf("\n\nOpcao nao encontrada.\nTente
Novamente\n\n"); system("pause"); system("cls"); menu();
break; }}
//FUNO MONTAR GRAFO (CADASTRO DE CIDADES)void montargrafo(){ int
num,I,J; char cidade[10][10]; char A[10][10]; char B[10][10]; do
{
system("cls"); printf(" 1 - Cadastrar cidades\n\n");
for(I=0; I
