cap09ED FILA PILHA E APONTADOR

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Estrutura de Dados
José Marcos Barbosa da Silveira
jmarcosbs@hotmail.com
*
Grafos
Grafos são uma forma de representar elementos de um conjunto e relações entre estes elementos de forma sucinta
Exemplos :
Grafos de Amizade
*
Grafos
Maria, Pedro, Joana e Luiz são os elementos do conjunto.
Uma relação de amizade representada no “grafo” acima é: Maria é amiga de Pedro e Joana, mas não é amiga de Luiz.
Problema de Transporte (Ex 02)
Grafos em problemas que envolvem transportes de carga ou pessoas.
Neste tipo de problema, os pontos de parada,
embarque e desembarque são os vértices e
as estradas entre os pontos são as arestas.
*
Grafos: Exemplo
*
Grafos (Problemas de transporte)
Podemos então formular questões que podem ser resolvidos com os algoritmos de grafos :
Problema de Conectividade :
dadas as direções das vias, é possível ir da cidade A até a cidade B, sem andar na contramão ?
Problema de Fluxo Máximo :
dada a capacidade de fluxo em cada via, quanta mercadoria podemos mandar de uma cidade A a uma cidade B ?
Problema de Menor Caminho :
Dados os comprimentos de cada via, qual o percurso mais rápido para sair de uma cidade A e chegar a uma cidade B?
*
Grafos (outros problemas)
Redes
Cada computador seria um vértice (nó) e a ligação entre eles seriam as arestas.
Podemos então construir algoritmos para responder questões como : 
Qual a quantidade mínima de ligações entre os computadores? O que devemos fazer para que a falha de, digamos 10%, deles não comprometa a capacidade de comunicação entre os restantes ?
Qual maneira devemos ligar os computadores para que a distância entre dois deles não ultrapasse um certo valor (rede, anel, estrela) ?
Planaridade
Na construção de redes de água, luz e comunicações, é
desejável o menor número de cruzamentos possíveis, a
fim de evitar que um acidente em uma tubulação comprometa as demais.
*
Grafos :Conceitos Básicos
Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde:
V - conjunto não vazio: os vértices ou nodos do grafo; 
A - conjunto de pares ordenados a = (v,w), v e w.
V: as arestas do grafo.
Seja, por exemplo, o grafo G(V,A) dado por:
V={p | p é uma pessoa }
A= { (v,w) | < v é amigo de w >}
*
Grafos :Conceitos Básicos
Esta definição representa toda uma família de grafos.
Um exemplo de elemento desta família (grafo G1) é dado por:
V= {Maria, Pedro, Joana, Luiz }
A={(Maria, Pedro) ,(Joana, Maria) ,(Pedro, Luiz) ,(Joana, Pedro) }
Neste exemplo estamos considerando que a relação
<v é amigo de w> é uma relação simétrica, ou seja, se < v é amigo de w> então <w é amigo de v>.
Como conseqüência, as arestas que ligam os vértices não possuem qualquer orientação.
*
Grafos :Conceitos Básicos
DIGRAFO (Grafo Orientado)
V={p | p é uma pessoa da família Castro }
A={(v,w) |<v é pai/mãe de w>}
Um exemplo de deste grafo (grafo G2) é:
V= {Renata, Emerson, Antonio, Isadora, Alfredo, Cecília }
A={(Isadora, Emerson),(Alfredo, Emerson),(Cecília, Antonio), (Alfredo, Antonio), (Antonio, Renata)}
*
Grafos :Conceitos Básicos
A relação definida por A não é simétrica pois se <v é pai/mãe de w>, não é
o caso de <w é pai/mãe de v>. Há, portanto, uma orientação na relação, com um correspondente efeito na representação gráfica de G.
O grafo acima é dito ser um grafo orientado (ou dígrafo), sendo que as conexões entre os vértices são chamadas de arcos. Grafo G2
*
Grafos 
ORDEM (cardinalidade)
A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G.
Nos exemplos abaixo:
*
Grafos 
Vértices Conexos
possuem uma relação de adjacência,
Dados dois vértices x e y, existe um nodo x1 que é adjacente a x, outro x2 que é adjacente a x1, e assim sucessivamente.
*
Grafos 
Cadeia
É um conjunto qualquer de linhas de um grafo.
Para o exemplo abaixo, são cadeias DAB, CB.
*
Grafos 
CAMINHO
Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados.
A seqüência de vértices (x1, x2, x5, x6, x3) é um exemplo de caminho no Grafo G6.
*
Grafos 
CIRCUITO
Um circuito é um caminho onde v1 = vn .
 A seqüência de vértices
(x1, x2, x5, x6 ,x3 , x2, x5, x4, x1) é um exemplo de circuito elementar no Grafo G6.
CICLO
Um circuito será simples se nenhum vértice aparecer mais de uma vez, exceto o primeiro e o último. Um circuito simples é chamado de ciclo. A
seqüência de vértices (x1, x2, x5, x4, x1) é um exemplo de ciclo no Grafo G6.
*
Grafos 
Número Cromático
É o menor valor de cores necessárias para colorir os vértices de um grafo, sem que vértices adjacentes tenham a mesma cor.
*
Grafos 
GRAFO VALORADO
Um grafo G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números.
É o grafo que possui valores nos vértices e nas curvas.
Para exemplificar (grafo G3), seja G(V,A) onde:
V={ v | v é uma cidade com aeroporto }
A={(v,w,t) | < há linha aérea ligando v a w, sendo t o tempo esperado de vôo>}
*
Grafos 
MULTIGRAFO
Um grafo G(V,A) é dito ser um multigrafo quando existem múltiplas arestas entre pares de vértices de G. No grafo G4, por exemplo, há duas arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o como um multigrafo.
*
Grafos 
Grafo parcial
Se G2 é um grafo parcial de G1, então G2 possui um mesmo conjunto de vértices, mas não o mesmo de arestas, do grafo G1.
*
Grafos 
Subgrafo
Se o grafo G2 é um subgrafo de G1,então G2 possui um número de vértices inferior aos de G1, embora mantendo o número de curvas entre os vértices existentes.
*
Grafos 
Subgrafo parcial
Se o grafo G2 é um subgrafo parcial de G1, então G2 é um subgrafo que não mantém todas as curvas entre os vértices existentes.
*
Grafos 
Grafo denso
É o grafo que possui alta cardinalidade de vértice ou curva.
Grafo pouco povoado
É o grafo que possui baixa cardinalidade de vértice ou curva.
*
Grafos 
Grafo conexo
É aquele onde qualquer par de vértice for conexo.
Ex. grafo conexo:
Ex. não conexo:
*
Grafos - Caminhamento em amplitude
Este tipo de caminhamento é realizado quando há interesse em avaliar-se todos os vértices principais antes de suas derivações posteriores.
– Escolhe-se um vértice para o início do caminhamento;
– Visitam-se os vértices adjacentes, marcando-os como visitados;
– Coloca-se cada um dos vértices adjacentes numa fila;
– Após visitados os vértices adjacentes, o primeiro da fila torna-se o novo vértice inicial e reinicia o processo;
– Termina quanto todos os vértices tiverem sido visitados ou o vértice procurado for encontrado.
*
Grafos - Caminhamento em amplitude
*
Grafos - Caminhamento em amplitude 
Para o grafo K (anterior) a ordem de visitação, se for escolhido inicialmente o vértice C seria :
• O adjacente será D (primeiro da fila).
• Como não há outro vértice adjacente, escolhe-se o primeiro da fila (D) para recomeçar o processo.
• O adjacente a D é B, o qual vai para a fila.
• Novamente não há outro adjacente, então escolhe-se o primeiro da fila, que é B.
• Repete-se o processo, visitando-se A, que vai para a fila.
• Mais uma vez, recomeça as visitas a partir de A, que era o primeiro da fila.
• Visita-se B, mas verifica-se que ele já está marcado como visitado.
• Então, visita-se C, mas ele também já foi marcado.
• Finalmente, visita-se D, que também já foi visitado, encerrando, então o caminhamento.
*
Grafos - Caminho em profundidade 
Este tipo de caminhamento é feito quando pretende-se explorar ao máximo determinada ramificação do grafo.
– Escolhe-se um vértice inicial;
– Visita-se um primeiro vértice adjacente, marcando-o como visitado;
– Coloca-se o vértice adjacente visitado numa pilha;
– O vértice visitado torna-se o novo vértice inicial;
– Repete-se o processo até que o vértice procurado seja encontrado ou não haja mais vértices adjacentes. Se verdadeiro, desempilha-se o topo e procura-se o próximo adjacente, repetindo o algoritmo;
– O processo termina quando o vértice procurado for encontrado ou quando a pilha estiver vazia e todos os vértices tiverem sido visitados.
*
Grafos - Caminho em profundidade 
*
Grafos - Caminho em profundidade
Seja o grafo T (anterior) :
• A seqüência de caminhamento inicia com a escolha de um vértice, digamos, A.
• Sendo A o vértice inicial, visita-se primeiro um de seus vértices adjacentes, por exemplo, B.
• Empilha-se A e B torna-se o novo vértice inicial.
• Mais uma vez, escolhe-se um adjacente, no caso há só um, E.
• Empilha-se B e E torna-se o novo vértice inicial. Como E não possui vértices adjacentes, desempilha-se o topo, ou seja, B.
• Mas B também não tem mais adjacentes, então desempilha-se A, o qual possui C como novo adjacente.
• Então C torna-se o novo vértice inicial, empilhando-se novamente A.
• O vértice adjacente D é escolhido e C é empilhado.
• D torna-se o novo vértice inicial. D é então empilhado e o seu adjacente F é escolhido.
Como F não possui vértices adjacentes, desempilha-se o topo, ou seja, D Como F (o único adjacente a D) já foi visitado desempilha-se o C. Como o F, próximo adjacente a C, já foi visitado desempilha-se o A. Como A não tem mais adjacentes, termina a busca.
*
Grafos 
Supondo que o grafo abaixo represente as distâncias entre algumas
cidades, podemos perceber que para ir de São Paulo para Recife
existem 4 possibilidades :
• <Spa, Rec> ..................................... = 400
• <Spa, Rio>, <Rio, Vit>, <Vit, Rec> = 450
• <Spa, Sal>, <Sal, Nat>, <Nat, Rec> = 300 (menor caminho)
• <Spa, Rio> <Rio, Nat>, <Nat, Rec> = 520
*
Grafos - Matriz de adjacência 
Podemos representar um grafo através de uma matriz de dimensão C(V) x C(V), onde o conteúdo poderá ser de números binários (0;1) ou inteiros (-1;0;1). Para exemplificar, analisemos o grafo G:
*
Grafos - Matriz de adjacência
A cardinalidade de vértices (ordem) do grafo G é 6,
portanto, para sua representação, deveremos ter uma matriz de adjacências 6x6. Utilizando valores binários, podemos representar desta forma.
*
Grafos - Listas Adjacentes 
Como estamos trabalhando com um dígrafo, devemos estabelecer
qual é a origem e qual é o destino.
No exemplo apresentado, a origem está definida pela letra indicadora de linha. Por exemplo, A está conectado com B, mas não o contrário, por isso ma[A,B] é 1 e ma[B,A] é 0.
Para resolvermos isso, podemos fazer uma representação alternativa:
ma[i,j] =-1 se i é origem da adjacência com j 
ma[i,j] = 1 se i é o destino da adjacência com j 
ma[i,j] = 0 para os demais vértices não em envolvidos na adjacência.
*
Grafos - Listas Adjacentes 
Estruturas fixas são inadequadas caso se necessite alterar o grafo (quantidade de vértices e/ou arestas)
Para que seja possível a remodelagem de um grafo em tempo de execução torna-se necessária a alocação dinâmica.
 Isto é possível através de listas lineares.
*
Grafos - Listas adjacentes
A lista encadeada é formada por nodos que contém o
dado do vértice (letra) e o ponteiro para o vértice adjacente ao indicado no índice (vetor dos vértices).
Os nodos poderão exigir outros campos, tais como marcação de visita ao vértice, dados adicionais para processamento da seqüência do grafo, etc.
*
Grafos 
Este tipo de matriz representa um grafo a partir de suas arestas.
Como exige muitas vezes a alocação de uma matriz maior do que no método da matriz de adjacências, não é tão utilizada quanto aquela.
A matriz alocada deverá ter dimensões C(V) x C(A).
O princípio desta representação está na regra:
mi[i,j] =1 se o vértice i incide com a aresta j, 
mi[i,j] =0
*
Exercícios 
Exercício - 1
Têm-se:
V = {1,2,3,4,5,6}
A = { (1,2), (2,1), (2,3), (2,4), (3,3) , (4,1), (4,3), (5,6)}
Fazer a representação gráfica e a matriz de incidência
Exercício 2
Representar os conjuntos e fazer a matriz de incidência
*
Bibliografia
Elisa M. Pivetta Cantarelli: Notas de aula. 
Veloso, P. A.S. ESTRUTURAS DE DADOS. CAMPUS, 2000.
Pereira, Silvio do Lago. Estrutura de dados Fundamentais. ÉRICA, 1996.
Bucknall, J. ALGORITIMOS E ESTRUTURAS DE DADOS COM DELPHI. BERKELEY BRASIL, 2002.
Wirth, N. ALGORITMOS E ESTRUTURAS DE DADOS. LTC, 1989.
Szwarcfiter, J. L. ESTRUTURAS DE DADOS E SEUS ALGORITMOS. LTC, 1994.