Algoritmos em Grafos - professor.ufabc.edu.brprofessor.ufabc.edu.br/~leticia.bueno/classes/aa/materiais/bfs.pdf · Algoritmos em Grafos ... 2 para u em V(G) faça ... Calcular o grau

Grafos Representação Número de Erdõs

Algoritmos em Grafos

Letícia Rodrigues Bueno

UFABC


Motivação

• Objetivo: aprender a resolver problemas;

• Como: usando grafos para modelar problemas;

• Grafos: ferramenta fundamental de abstração;

• Abstraímos problema real (usando grafos) e solucionamosatravés de algoritmos;


Definição de Grafos

• Wikipedia (2012): “...conjunto de pontos (vértices) ligadospor retas (as arestas)”

• Abstração que permite codificar relacionamentos entrepares de objetos;

• Objetos: cidades, pessoas, países, empresas, etc;

• Relacionamentos: amizade, conectividade, idioma, etc;


Supervisão de pós-graduação


Supervisão de pós-graduação

RenataAndreia Felipe Jorge

Rodrigo Leticia


Vôos AéreosAzul Linhas Aéreas, retirado de: http://www.voeazul.com.br/

http://www.voeazul.com.br/

https://apps.voeazul.com.br/SimuladorTarifas/Default.aspx


Vôos Aéreos

Webjet Linhas Aéreas, retirado de: http://www.webjet.com.br/

http://www.webjet.com.br/

http://webjet.com.br/empresa/site/internas/mapa-de-rotas.aspx


Vôos Aéreos

TAM Linhas Aéreas, retirado de: http://www.tam.com.br/

http://www.tam.com.br/

http://www.passiontoflyandserve.com.br/rotas/


Número de Bacon

Fonte: http://oracleofbacon.org/

http://oracleofbacon.org/



Número de Bacon

Fonte: http://oracleofbacon.org/




Representação Computacional: Lista de Adjacências

(a) G (b) Lista de Adjacências de G

Vantagem: espaço em memória Θ(n + m).Desvantagem: determinar se aresta está em G exigepercorrer lista de adjacências.


Representação Computacional: Matriz de Adjacências

(c) H (d) Matriz de Adjacências de H

Vantagem: determinar se aresta está em G exige O(1).Desvantagem: espaço em memória Θ(n2).


Representação Computacional: E esse grafo?

1112

13 1

2 4

7

35

6

14

1098

(e) G1


Problema 1: Número de Erdõs

• Paul Erdõs: famoso matemático hungáro;

• Trabalhou com centenas decolaboradores;

• Publicou mais de 1.400 artigos;

• Número de Erdõs é um tributo divertidocriado pelos amigos;

• Paul Erdõs tem número de Erdõs 0;

• Os colaboradores diretos tem número 1;

• Os colaboradores dos colaboradores temnúmero 2 e assim por diante;


Definição

• Dada uma lista de pessoas e as relações de colaboraçãoentre elas, qual é o número de Erdõs de cada pessoa?


Definição

• Dada uma lista de pessoas e as relações de colaboraçãoentre elas, qual é o número de Erdõs de cada pessoa?

• Este problema pode ser modelado através de um grafo:• As pessoas são os vértices;• As relações de colaboração são as arestas.


Exemplo

Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

0


Busca em Largura (BFS - Breadth-First Search)

Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

0



Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

0

Erdos



Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

1 1

1

1

1

0

Chvatal Lovasz Babai Hell Harary



Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

1 1

1

1

1

2

2

2

22

0

Bondy Imrich Watkins Deng White



Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

1 1

1

1

1

2

2

2

22

3

3

0

Murty Papadimitriou



Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins

1 1

1

1

1

2

2

2

22

3

3

4

0

Gates



Erdos

Hell

Papadimitriou

Gates

Deng

Harary

White

Murty

Bondy

Chvatal

Lovasz

Babai

Imrich

Watkins


Algoritmo BFS

1 bfs(G, s):2 para u em V(G) faça3 u.visitado = False4 u.d = ∞5 u.p = None6 s.visitado = True7 s.d = 08 Q = Fila()9 insere(Q, s)

10 enquanto tamanho(Q) > 0 faça11 u = remove(Q)12 para v em adj(u) faça13 se não v.visitado então14 v.d = u.d + 115 v.p = u16 v.visitado = True17 insere(Q, v)


Algoritmo BFS



Análise da complexidade:


Algoritmo BFS




• Cada vérticeadicionado uma vezna fila (linha 17): O(n)


Algoritmo BFS





• A lista de adjacênciade cada vérticepercorrida uma vez(linha 12): O(m)


Algoritmo BFS





• A lista de adjacênciade cada vérticepercorrida uma vez(linha 12): O(m)

• Complexidade total:O(n + m)


Exercícios

1. Considere G = (V ,E), n = |V |, m = |E | e grafosnão-orientados. Calcule a complexidade no pior caso de:

ProblemaMatriz Lista

Adjacências AdjacênciasEspaço em memóriaBuscar vértices adjacentesde um vértice vConferir adjacênciados vértices u e vVisitar todas as arestasCalcular o graude um vértice v


Bibliografia Utilizada

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. e STEIN, C.Introduction to Algorithms, 3a edição, MIT Press, 2009.

Documents

Algoritmos em Grafos - professor.ufabc.edu.brprofessor.ufabc.edu.br/~leticia.bueno/classes/aa/materiais/bfs.pdf · Algoritmos em Grafos ... 2 para u em V(G) faça ... Calcular o grau