Embed Size (px)
Citation preview
Grafos - Busca
Profa.ElaineParrosMachadodeSousaalterações: Cristina Dutra de Aguiar Ciferri
Materialbaseadoemaulasdosprofessores:
GustavoBa5sta,RobsonCordeiro,MoacirPon5Jr.,MariaCris5naOliveiraeThiagoA.S.Pardo
ALGORITMOS E ESTRUTURAS DE DADOS II
BUSCAEMGRAFOS:MOTIVAÇÃO¢ Percorrerumgrafoéumproblemafundamental� deve-seterumaformasistemá5cadevisitarasarestaseosvér5ces
� oalgoritmodevesersuficientementeflexívelparaseadequaràdiversidadedegrafos
¢ Requisitos� nãodevehaverrepe5ções(desnecessárias)devisitasaumvér5cee/ouaresta
� todososvér5cese/ouarestasdevemservisitados
BUSCAEMGRAFOS:TIPOSDEBUSCA¢ Exemplos:
� dadoumgrafoG=(V,A)eumvér5cev∈V=>encontrartodososvér5cesemGqueestãoconectadosav.
� dadoumgrafoG=(V,A)=>visitartodososvér5cesdeG.
¢ Duasmaneirasprincipaisderealizaressastarefas:� Buscaemprofundidade� Buscaemlargura
¢ Breadth-FirstSearch–BFS� expandeafronteiraentrevér5cesdescobertosenãodescobertosuniformementeatravésdalarguradafronteira.
¢ Caracterís5cas� oalgoritmodescobretodososvér5cesaumadistânciakdovér5ceorigemantesdesedescobrirqualquervér5ceaumadistânciak+1
� abuscaemlargurapermitedescobrirtodososvér5cesalcançáveisapar5rdeumvér5cedeorigemu,comomenornúmerodearestasentreuetodososoutrosvér5ces
BuscaemLargura:Definição
¢ Cadavér5ceécoloridodebranco,cinzaoupreto.� todososvér5cessãoinicialmentebrancos.� quandoumvér5cevé“descoberto”pelaprimeiravezeletorna-secinza.
� quandotodososvér5cesadjacentesavforem“descobertos”,vtorna-sepreto.
BuscaemLargura:Estratégia
¢ Observações� vér5cescinzaepretojáforam“descobertos”,massãodiferenciadosparaassegurarqueabuscaocorraemlargura
� se(u,v)∈Aeovér5ceuépreto,entãoovér5cevtemquesercinzaoupreto.¢ todososvér5cesadjacentesaumvér5cepretojáforam“descobertos”
� vér5cescinzapodemteralgunsvér5cesadjacentesbrancos,representandoafronteiraentrevér5ces“descobertos”enão“descobertos”.
BuscaemLargura:Estratégia
¢ Usodeumafilaparaorganizarosvér5cesquedevemserdescobertos1 afilacomeçacomovér5ceorigem2 oprimeirovér5cedafilaérecuperadoe
processado,sendoqueseusvér5cesadjacentessãoinseridosnofinaldafila
3 seafilaestávazia,oprocessotermina.Casocontrário,volta-seaopasso2
BuscaemLargura:Fila
2
5
1
6
3
7
4
8
q 1 0
Busca em Largura: Exemplo
k
Vértice origem: 1 Distância k do vértice origem: 0 Ação: vértice 1 torna-se cinza
2
5
1
6
3
7
4
8
q 1 0
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 1: 2, 6 Distância k do vértice origem: 1
2
5
1
6
3
7
4
8
q 6 1
2 1
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 1: 2, 6 Distância k do vértice origem: 1 Ação: vértice 1 torna-se preto e vértices 2 e 6 tornam-se cinza
2
5
1
6
3
7
4
8
q 6 1
2 1
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 6: 3, 7 Distância k do vértice origem: 2
2
5
1
6
3
7
4
8
q 2 1
3 7 2 2
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 6: 3, 7 Distância k do vértice origem: 2 Ação: vértice 6 torna-se preto e vértices 3 e 7 tornam-se cinza
2
5
1
6
3
7
4
8
q 2 1
3 7 2 2
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 2: 5 Distância k do vértice origem: 2
2
5
1
6
3
7
4
8
q 3 2
7 5 2 2
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 2: 5 Distância k do vértice origem: 2 Ação: vértice 2 torna-se preto e vértice 5 torna-se cinza
2
5
1
6
3
7
4
8
q 3 2
7 5 2 2
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 3: 4 Distância k do vértice origem: 3
2
5
1
6
3
7
4
8
q 7 2
5 4 2 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 3: 4 Distância k do vértice origem: 3 Ação: vértice 3 torna-se preto e vértice 4 torna-se cinza
2
5
1
6
3
7
4
8
q 7 2
5 4 2 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 7: 8 Distância k do vértice origem: 3
2
5
1
6
3
7
4
8
q 5 2
4 8 3 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 7: 8 Distância k do vértice origem: 3 Ação: vértice 7 torna-se preto e vértice 8 torna-se cinza
2
5
1
6
3
7
4
8
q 5 2
4 8 3 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 5: nenhum Distância k do vértice origem: -
2
5
1
6
3
7
4
8
q 4 3
8 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 5: nenhum Distância k do vértice origem: - Ação: vértice 5 torna-se preto
2
5
1
6
3
7
4
8
q 4 3
8 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 4: nenhum Distância k do vértice origem: -
2
5
1
6
3
7
4
8
q 8 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 4: nenhum Distância k do vértice origem: - Ação: vértice 4 torna-se preto
2
5
1
6
3
7
4
8
q 8 3
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 8: nenhum Distância k do vértice origem: -
2
5
1
6
3
7
4
8
q
Busca em Largura: Exemplo
k
Vértices não descobertos adjacentes a 8: nenhum Distância k do vértice origem: - Ação: vértice 8 torna-se preto
¢ Caracterís5ca� linearemrelaçãoaotamanhodarepresentaçãodografousandolistasdeadjacência
¢ O(|V|)� todososvér5cessãocolocadosnafilanomáximoumavez,ouseja,sãoexecutadas|V|iteraçõescomcustoO(1)cadaumadelas
¢ O(|A|)� cadalistadeadjacênciaépercorridanomáximoumavezquandoovér5ceére5radodafila
Busca em Largura: Complexidade
O(|V|+|A|)
¢ Oalgoritmoébaseparaoutrosalgoritmosimportantes:� encontraraárvoregeradoramínima(MST)–AlgoritmodePrim
� encontrarocaminhomaiscurtodeumvér5cevatodososoutros–AlgoritmodeDijkstra
BuscaemLargura:Uso
a busca em largura resulta no caminho mais curto entre o vértice origem u e um vértice qualquer v.
