Grafos
Representação
Algoritmos em Grafos
Letícia Rodrigues Bueno
UFABC
Número de Erdõs
Grafos
Representação
Número de Erdõs
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 solucionamos
através de algoritmos;
Grafos
Representação
Número de Erdõs
Definição de Grafos
• Wikipedia (2012): “...conjunto de pontos (vértices) ligados
por retas (as arestas)”
• Abstração que permite codificar relacionamentos entre
pares de objetos;
• Objetos: cidades, pessoas, países, empresas, etc;
• Relacionamentos: amizade, conectividade, idioma, etc;
Grafos
Representação
Supervisão de pós-graduação
Número de Erdõs
Grafos
Representação
Número de Erdõs
Supervisão de pós-graduação
Rodrigo
Andreia
Leticia
Renata
Felipe
Jorge
Grafos
Representação
Número de Erdõs
Vôos Aéreos
Azul Linhas Aéreas, retirado de: http://www.voeazul.com.br/
Grafos
Representação
Número de Erdõs
Vôos Aéreos
Webjet Linhas Aéreas, retirado de: http://www.webjet.com.br/
Grafos
Representação
Vôos Aéreos
TAM Linhas Aéreas, retirado de: http://www.tam.com.br/
Número de Erdõs
Grafos
Representação
Número de Bacon
Fonte: http://oracleofbacon.org/
Número de Erdõs
Grafos
Representação
Número de Bacon
Fonte: http://oracleofbacon.org/
Número de Erdõs
Grafos
Representação
Número de Erdõs
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 exige
percorrer lista de adjacências.
Grafos
Representação
Número de Erdõs
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 ).
Grafos
Representação
Número de Erdõs
Representação Computacional: E esse grafo?
12
11
2
8
9
4
7
13
1
5
6
14
(e) G1
3
10
Grafos
Representação
Número de Erdõs
Problema 1: Número de Erdõs
• Paul Erdõs: famoso matemático hungáro;
• Trabalhou com centenas de
colaboradores;
• Publicou mais de 1.400 artigos;
• Número de Erdõs é um tributo divertido
criado pelos amigos;
• Paul Erdõs tem número de Erdõs 0;
• Os colaboradores diretos tem número 1;
• Os colaboradores dos colaboradores tem
número 2 e assim por diante;
Grafos
Representação
Número de Erdõs
Definição
• Dada uma lista de pessoas e as relações de colaboração
entre elas, qual é o número de Erdõs de cada pessoa?
Grafos
Representação
Número de Erdõs
Definição
• Dada uma lista de pessoas e as relações de colaboração
entre 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.
Grafos
Representação
Número de Erdõs
Exemplo
Murty
Lovasz
Babai
Bondy
White
Chvatal
Harary
0 Erdos
Hell
Deng
Imrich
Papadi
mitriou
Watkins
Gates
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty
Lovasz
Babai
Bondy
White
Chvatal
Harary
0 Erdos
Hell
Deng
Imrich
Papadi
mitriou
Watkins
Gates
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty
Lovasz
Babai
Bondy
White
Chvatal
Harary
0 Erdos
Hell
Deng
Imrich
Papadi
mitriou
Watkins
Gates
Erdos
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty
Bondy
Chvatal1
Lovasz 1
Babai
1
White
Harary 1
0 Erdos
Hell
1
Deng
Imrich
Papadi
mitriou
Watkins
Gates
Chvatal Lovasz Babai Hell Harary
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty
Bondy 2
Chvatal1
Lovasz 1
Babai
1
2
White
Harary 1
0 Erdos
Hell
1
2 Deng
Imrich2
Papadi
mitriou
Watkins2
Gates
Bondy Imrich Watkins Deng White
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty 3
Bondy 2
2
Chvatal1
Lovasz 1
Babai
1
White
Harary 1
0 Erdos
Hell
1
Imrich2
Watkins2
Murty Papadimitriou
2 Deng
3
Papadi
mitriou
Gates
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty 3
Bondy 2
2
Chvatal1
Lovasz 1
Babai
1
White
Harary 1
0 Erdos
Hell
1
2 Deng
Papadi
mitriou
Imrich2
3
Watkins2
4 Gates
Gates
Grafos
Representação
Número de Erdõs
Busca em Largura (BFS - Breadth-First Search)
Murty
Bondy
White
Chvatal
Harary
Lovasz
Erdos
Babai
Hell
Deng
Imrich
Papadi
mitriou
Watkins
Gates
Grafos
Representação
Algoritmo BFS
1 bfs(G, s):
2
para u em V(G) faça
3
u.visitado = False
4
u.d = ∞
5
u.p = None
6
s.visitado = True
7
s.d = 0
8
Q = Fila()
9
insere(Q, s)
10
enquanto tamanho(Q) > 0 faça
11
u = remove(Q)
12
para v em adj(u) faça
13
se não v.visitado então
14
v.d = u.d + 1
15
v.p = u
16
v.visitado = True
17
insere(Q, v)
Número de Erdõs
Grafos
Representação
Número de Erdõs
Algoritmo BFS
1 bfs(G, s):
2
para u em V(G) faça
3
u.visitado = False
4
u.d = ∞
5
u.p = None
6
s.visitado = True
7
s.d = 0
8
Q = Fila()
9
insere(Q, s)
10
enquanto tamanho(Q) > 0 faça
11
u = remove(Q)
12
para v em adj(u) faça
13
se não v.visitado então
14
v.d = u.d + 1
15
v.p = u
16
v.visitado = True
17
insere(Q, v)
Análise da complexidade:
Grafos
Representação
Número de Erdõs
Algoritmo BFS
1 bfs(G, s):
2
para u em V(G) faça
3
u.visitado = False
4
u.d = ∞
5
u.p = None
6
s.visitado = True
7
s.d = 0
8
Q = Fila()
9
insere(Q, s)
10
enquanto tamanho(Q) > 0 faça
11
u = remove(Q)
12
para v em adj(u) faça
13
se não v.visitado então
14
v.d = u.d + 1
15
v.p = u
16
v.visitado = True
17
insere(Q, v)
Análise da complexidade:
• Cada vértice
adicionado uma vez
na fila (linha 17): O(n)
Grafos
Representação
Número de Erdõs
Algoritmo BFS
1 bfs(G, s):
2
para u em V(G) faça
3
u.visitado = False
4
u.d = ∞
5
u.p = None
6
s.visitado = True
7
s.d = 0
8
Q = Fila()
9
insere(Q, s)
10
enquanto tamanho(Q) > 0 faça
11
u = remove(Q)
12
para v em adj(u) faça
13
se não v.visitado então
14
v.d = u.d + 1
15
v.p = u
16
v.visitado = True
17
insere(Q, v)
Análise da complexidade:
• Cada vértice
adicionado uma vez
na fila (linha 17): O(n)
• A lista de adjacência
de cada vértice
percorrida uma vez
(linha 12): O(m)
Grafos
Representação
Número de Erdõs
Algoritmo BFS
1 bfs(G, s):
2
para u em V(G) faça
3
u.visitado = False
4
u.d = ∞
5
u.p = None
6
s.visitado = True
7
s.d = 0
8
Q = Fila()
9
insere(Q, s)
10
enquanto tamanho(Q) > 0 faça
11
u = remove(Q)
12
para v em adj(u) faça
13
se não v.visitado então
14
v.d = u.d + 1
15
v.p = u
16
v.visitado = True
17
insere(Q, v)
Análise da complexidade:
• Cada vértice
adicionado uma vez
na fila (linha 17): O(n)
• A lista de adjacência
de cada vértice
percorrida uma vez
(linha 12): O(m)
• Complexidade total:
O(n + m)
Grafos
Representação
Número de Erdõs
Exercícios
1. Considere G = (V , E ), n = |V |, m = |E | e grafos
não-orientados. Calcule a complexidade no pior caso de:
Problema
Espaço em memória
Buscar vértices adjacentes
de um vértice v
Conferir adjacência
dos vértices u e v
Visitar todas as arestas
Calcular o grau
de um vértice v
Matriz
Adjacências
Lista
Adjacências
Grafos
Representação
Número de Erdõs
Bibliografia Utilizada
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. e STEIN, C.
Introduction to Algorithms, 3a edição, MIT Press, 2009.