Esperamos que tenha gostado desta apresentação. Recomende, por favor, esta apresentação aos seus amigos noutra rede social para carregar. Botões estão em baixo. Obrigado.
Botões:
Cancelamento
Carregar
A apresentação está carregando. Por favor, espere
Gustavo Sant´Anna Ferreira Rodrigo Ribeiro de Souza
PublicouRaul Rozario Alterado mais de 8 anos atrás
Incorporar
Carregar apresentação
Copiar para cambiar
Apresentações semelhantes
Mais detalhes
Apresentação em tema: "Gustavo Sant´Anna Ferreira Rodrigo Ribeiro de Souza"— Transcrição da apresentação:
1 Gustavo Sant´Anna Ferreira Rodrigo Ribeiro de Souza
DISTÂNCIA EM GRAFOS Gustavo Sant´Anna Ferreira Rodrigo Ribeiro de Souza
2 Busca em Largura (FIFO (Listas))
Distância em Grafos Busca em Largura (FIFO (Listas)) Nós usamos o algoritmo de Busca em Largura para descobrir o número de arestas no menor caminho de S a Vi para grafos sem pesos nas arestas. Onde S é o vértice escolhido inicialmente e Vi é qualquer um dos outros vértices do grafo. S V1 V2 V3 V5 V4 ds(V1)=ds(V2)=ds(V3)=1
3 Algoritmo Busca em Largura (G,v)
Distância em Grafos Algoritmo Busca em Largura (G,v) Entrada: G=(V,E) (um grafo não direcionado e V um vértice de G) Saída : Depende da aplicação
4 Distância em Grafos Algoritmo Início Marque V; Coloque V numa fila;
Enquanto a fila não estiver vazia faça Remova o primeiro vértice W da fila; Faça o Pré-Work em W; //(depende da aplicação)// Para Todo (W,X) tal que X é desmarcado faça Marque X; Adicione (W,X) à árvore T; Coloque X na fila; Fim
5 Distância em Grafos Exemplo de Busca em Largura A C B F D E Fila
Início Marque V; Coloque V numa fila; Enquanto a fila não estiver vazia faça Remova o primeiro vértice W da fila; Faça o Pré-Work em W; Para Todo (W,X) tal que X é desmarcado faça Marque X; Adicione (W,X) à árvore T; Coloque X na fila; Fim A D B C E F Fila
6 Distância em Grafos Exemplo onde o algoritmo de busca em largura não encontra o menor caminho num grafo com peso nas arestas. Grafo com Peso A D B C 10 4 3 2 D A B C Busca em Largura
7 Técnica do Algoritmo Guloso
Distância em Grafos Técnica do Algoritmo Guloso • Consiste num processo interativo para “construir” soluções sucessivamente mais próximas da solução global procurada. • Aplica-se para alguns problemas do tipo : Dado um conjunto S , achar S’  S tal que : -- S’ satisfaz a uma propriedade P dada, e -- S’ é o máximo (ou mínimo) com relação a algum critério. Obs: Essa metodologia não permite remover elementos já incluídos no conjunto S’. • Por isso nem sempre é uma abordagem correta para resolver problemas de maximização.
8 Single Source Shortest Path
Distância em Grafos Single Source Shortest Path É um algoritmo que descobre a menor distância de um vértice V para qualquer outro vértice do grafo. Algoritmo Implementação Custo
9 Distância em Grafos Algoritmo Single Source Shortest Paths (G,v).
• Entrada: G=(v,e) (um grafo com peso nas arestas e (v) vértice de origem). Saída : Para cada vértice w , w.sp é a menor distância de v para w
10 Distância em Grafos Algoritmo Single Source Shortest Paths A F E D C B
Início: Para todos os vértices W faca w.mark := Falso; w.sp:= ; v.sp:= 0; Enquanto existir um vértice não marcado faça pegue w sendo um vértice não marcado desde que w.sp é mínimo; w.mark := Verdadeiro; Para toda aresta (w,z) desde que z é não marcado faça se w.sp + peso (w,z) < z.sp então z.sp := w.sp + peso (w,z) Fim. A F E D C B 2 10 3 4 6 1 5
11 Distância em Grafos Implementação
O heap é uma boa estrutura de dados para encontrarmos os elementos mínimos (w.sp) e atualizarmo-os, quando tornarem-se menores que seus pais, devendo ser trocados e movidos para cima até a sua posição apropriada. Ele guarda todos os vértices desmarcados com suas atuais menores distâncias de V como suas chaves, que inicialmente recebem o valor  com exceção de V, que recebe o valor zero. Para localizarmos um elemento utilizamos um array com ponteiros para suas localizações no heap, pois o heap não é uma estrutura de busca.
12 Distância em Grafos CUSTO
Atualizar uma distância toma O(log m) comparações onde m é o tamanho do heap. Há |V| iterações , levando a |V| deleções no heap. Há também no máximo |E| atualizações ( desde que cada aresta pode causar no máximo uma atualização), levando a O ( |E| log |V| ) comparações no heap. Daí o tempo de execução é: O ( ( |E| + |V| ) log |V| ).
Carregar ppt "Gustavo Sant´Anna Ferreira Rodrigo Ribeiro de Souza"
Apresentações semelhantes
Algoritmos de Caminho Mínimo em Grafos
Algoritmo de Caminho Mínimo
Árvores 2010/1 Teoria dos Grafos (INF 5037/INF2781)
Árvores CC/EC/Mestrado Teoria dos Grafos ‏ 1.
Algoritmos em Grafos.
Algoritmos em Grafos (Parte 2)
Antonio Dirceu Rabelo de Vasconcelos Filho
Celso C. Ribeiro Caroline T. Rocha
Fluxo em Redes Prof. Ricardo R. Santos.
Exercícios PAA- Grafos
Exercícios PAA- Grafos
Pontes Seja (G) o número de componentes conexas de G. Uma ponte é uma aresta a tal que (G - a) > (G)
UFES CC/EC/Mestrado Teoria dos Grafos Árvores. UFES CC/EC/Mestrado Teoria dos Grafos Árvores Grafo Acíclico: não possui ciclos.
CC/EC/PPGI/UFES CC/EC/MestradoTeoria dos Grafos Algoritmo de Caminho Mínimo.
Métodos para representação de estruturas hierárquicas
Análise e Síntese de Algoritmos
Problemas de fluxo numa rede
GRASP Greedy Randomized Adaptative Search Procedure
Árvores.
Medida do Tempo de Execução de um Programa
Apresentações semelhantes
Sobre projeto
SlidePlayer
Termos de uso
Feedback
Política de Privacidade
Feedback
© 2021 SlidePlayer.com.br Inc.
All rights reserved.
Busca
To make this website work, we log user data and share it with processors. To use this website, you must agree to our Privacy Policy, including cookie policy.