Grafos
Msc. Daniele Carvalho Oliveira
1
2
Pontes de Königsberg (1736)
3
O que são Grafos
 Conjunto
pontos.
 Grafo
de pontos e linhas que conectam os
é um modelo matemático que representa
relações entre objetos.
4
O que são Grafos
 Grafos
são estruturas de dados largamente
usadas em computação.
 Exemplos




de aplicações são:
Modelagem de circuitos digitais
Representação de processos em sistemas
paralelos ou distribuídos, Redes
Redes Sociais
Recuperação de Informação
5
O que são Grafos
 Similar
a árvores e listas, com menos restrições
6
7
Definição
 Um


Grafo é um par ordenado 𝐺 = (𝑉, 𝐸)
𝑉 é um conjunto finito não-vazio. Os elementos de
𝑉 são denominados vértices.
𝐸 é um conjunto finito de pares ordenados de
vértices. Os elementos de 𝐸 são denominados
arestas.
 Dois
vértices ligados por uma aresta são
denominados adjacentes
8
Exemplo
𝑉
= 0,1,2,3,4
 𝐸 = { 1,2 , 1,3 , 1,4 , 3,4 }
9
Conceitos de Grafos
10
Laços, Arestas Múltiplas e
Multigrafo
11
Grafo Trivial e Grafo Simples
A
B
C
12
Grafo Completo
13
Grafo Regular
Não é Grafo Regular
Grafo Regular de grau 3
14
Subgrafo
15
Caminho simples, trajeto e
ciclos

Um Caminho é uma sequência de vértices
𝑣1 , 𝑣2 , … , 𝑣𝑘 , tal que (𝑣𝑖 , 𝑣𝑖+1 ) ∈ 𝐸 𝐺

Quando todos os vértices do caminho são distintos,
recebe o nome de caminho simples.

Quando todas as arestas são distintas, o caminho
recebe o nome de trajeto

Um ciclo é um caminho 𝑣1 , 𝑣2 , … , 𝑣𝑘 , tal que 𝑣1 = 𝑣𝑘 e
𝑘≥3
16
 Caminho
 Trajeto:
 Ciclo:
simples: 2,1,3,4
1,3,4,1,2
1,3,4,1
17
Grafo Conexo e Desconexo
18
Grafo Ponderado
3
5
1
4
2
6
7
8
19
Dígrafo
20
Dígrafo
 Grafo
Orientado
 Deve-se
respeitar a orientação das arestas
21
Dígrafo
 Grau
de entrada: número de arestas que
incidem no vértice

Vértice Fonte: grau de entrada = 0
 Grau
de saída: número de arestas que partem
do vértice

Vértice Sumidouro: grau de saída = 0
22
Árvores
 Um





Grafo 𝑇(𝑉, 𝐸)
Não possui ciclos
Conexo
Seja 𝑣 ∈ 𝑉, se 𝑣 possui grau menor ou igual a 1,
então 𝑣 é uma folha
Uma árvore com 𝑛 vértices possui 𝑛 − 1 arestas.
Um grafo 𝐺 é uma árvore, se, e somente se, existir
um único caminho entre cada par de vértices de
𝐺.
23
24
Representação de Grafos
25
 Como
representar grafos em nossos algoritmos?
 Estruturas

de dados!
Matrizes
 Matriz
de Adjacência
 Matriz de Incidência

Listas
 Listas
de Adjacência
26
Matriz de Adjacência
 Dado
um grafo 𝐺(𝑉, 𝐸)
 Uma Matriz de Adjacência 𝑀 é formada por 𝑛
linhas e 𝑛 colunas

𝑛 = número de vértices do grafo
1, 𝑠𝑒 𝑖, 𝑗 ∈ 𝐸(𝐺)
𝑀𝑖𝑗 =
0, 𝑠𝑒 𝑖, 𝑗 ∉ 𝐸(𝐺)
27
1
2
3
4
5
1
0
1
0
0
1
2
1
0
1
1
0
3
0
1
0
1
0
4
0
1
1
0
1
5
1
0
0
1
1
28
1
2
3
4
5
1
0
1
0
0
1
2
0
0
1
0
0
3
0
1
0
0
0
4
0
1
1
0
0
5
0
0
0
1
1
29
Matriz de Adjacência
O
espaço reservado para armazenar as
informações da matriz é da ordem 𝑂 𝑉 2
 Para buscar uma aresta: 𝑂(1)
30
Matriz de Incidência
 Dado
um grafo 𝐺(𝑉, 𝐸) de 𝑛 vértices e 𝑚 arestas
1, ∀𝑣𝑖 , 𝑠𝑒 𝑣𝑖 , 𝑣𝑗 ∈ 𝐸 𝐺
𝑀𝑖𝑗 =
0, 𝑠𝑒 𝑣𝑖 , 𝑣𝑗 ∉ 𝐸 𝐺
0, 𝑠𝑒 𝑣𝑖 , 𝑣𝑖 ∈ 𝐸 𝐺
31
e1 e2 e3 e4 e5 e6 e7 e8
e8
e7
e1
e5
e6
e4
e2
e3
1
1
0
0
0
0
0
1
0
2
1
1
1
0
1
0
0
0
3
0
1
1
1
0
0
0
0
4
0
0
0
1
1
1
0
0
5
0
0
0
0
0
1
1
0
32
1, ∀𝑣𝑖 , 𝑠𝑒 𝑣𝑖 , 𝑣𝑗 ∈ 𝐸 𝐺
𝑀𝑖𝑗 =
−1, ∀𝑣𝑗 , 𝑠𝑒 𝑣𝑖 , 𝑣𝑗 ∈ 𝐸 𝐺
0, 𝑠𝑒 𝑣𝑖 , 𝑣𝑗 ∉ 𝐸 𝐺
0, 𝑠𝑒 𝑣𝑖 , 𝑣𝑖 ∈ 𝐸 𝐺
33
e1 e2 e3 e4 e5 e6 e7 e8
e8
e7
e1
e5
e6
e4
e2
e3
1
1
0
0
0
0
0
1
0
2
-1
1
-1
0
-1
0
0
0
3
0
-1
1
-1
0
0
0
0
4
0
0
0
1
1
-1
0
0
5
0
0
0
0
0
1
-1
0
34
Matriz de Incidência
O
espaço reservado para armazenar as
informações da matriz é da ordem 𝑂 |𝑉| × |𝐸|
 Para buscar uma aresta: 𝑂(1)
35
Lista de Adjacência
 Consiste
em um vetor 𝐴𝑑𝑗 com 𝑛 = |𝑉| entradas
 Cada entrada 𝐴𝑑𝑗[𝑣] possui uma lista
encadeada de vértices adjacentes à 𝑣.
36
1
5
2
2
1
4
3
2
4
4
5
2
5
1
4
3
3
37
1
5
2
3
3
2
4
2
5
4
2
3
38
Matriz de Incidência
O
espaço reservado para armazenar as
informações da matriz é da ordem 𝑂 |𝑉| + |𝐸|
 Para buscar uma aresta: 𝑂(𝑛)

Para descobrir se existe a aresta (𝑖, 𝑗) deve-se
percorrer a lista do nó 𝑖 até encontrar (ou não) 𝑗
39
Busca em Grafos
40
Algoritmos de Busca
 Operação

mais comum em Grafos
Visita sistemática a seus nós (uma única vez!)
 Similar
 Para
às buscas em árvore
passear ou caminhar pelos vértices e
arestas, utiliza-se marcar um vértice quando ele
já foi visitado.
41
Algoritmos de Busca
 Dois


tipos básicos de busca
Busca em Profundidade
Busca em Largura
42
Busca em
Profundidade
43
1
5
2
2
1
4
3
2
4
4
5
2
5
1
4
3
3
44
Busca em Profundidade
 Para
acessar todos os vértices do grafo, a busca
em profundidade varre a lista de adjacência de
cada vértice do grafo

Assim, o tempo gasto para a operação é
𝑂(|𝑉| + |𝐸|)
45
Busca em
Largura
46
Distâncias
Fila
1
1
2
3
4
5
∞
∞
∞
∞
∞
1
5
2
3
3
2
4
2
5
4
2
3
47
Distâncias
Fila
1
2
3
4
5
0
∞
∞
∞
∞
1
5
2
3
3
2
4
2
5
4
2
3
48
Distâncias
Fila
5
2
1
2
3
4
5
0
1
∞
∞
1
1
5
2
3
3
2
4
2
5
4
2
3
49
Distâncias
Fila
2
1
2
3
4
5
0
1
∞
∞
1
1
5
2
3
3
2
4
2
5
4
2
3
50
Distâncias
Fila
2
1
2
3
4
5
0
1
∞
∞
1
1
5
2
3
3
2
4
2
5
4
2
3
51
Distâncias
Fila
2
4
1
2
3
4
5
0
1
∞
2
1
1
5
2
3
3
2
4
2
5
4
2
3
52
Distâncias
Fila
4
1
2
3
4
5
0
1
∞
2
1
1
5
2
3
3
2
4
2
5
4
2
3
53
Distâncias
Fila
4
1
2
3
4
5
0
1
∞
2
1
1
5
2
3
3
2
4
2
5
4
2
3
54
Distâncias
Fila
4
3
1
2
3
4
5
0
1
2
2
1
1
5
2
3
3
2
4
2
5
4
2
3
55
Distâncias
Fila
3
1
2
3
4
5
0
1
2
2
1
1
5
2
3
3
2
4
2
5
4
2
3
56
Distâncias
Fila
3
1
2
3
4
5
0
1
2
2
1
1
5
2
3
3
2
4
2
5
4
2
3
57
Distâncias
Fila
1
2
3
4
5
0
1
2
2
1
1
5
2
3
3
2
4
2
5
4
2
3
58
Distâncias
Fila
1
2
3
4
5
0
1
2
2
1
1
5
2
3
3
2
4
2
5
4
2
3
59
Busca em Largura
 Primeiro
os vértices são inicializados, ou seja,
marcados como não visitados.
 O vetor de distâncias é inicializado com ∞ em
todas as posições

Este processo de inicialização gasta tempo 𝑂(|𝑉|)
60
Busca em Largura
A
medida que os vértices são encontrados, são
colocados em uma fila


As operações de inserção e remoção da fila
gastam tempo 𝑂(1)
Como todos os vértices são colocados e retirados
da fila, o tempo total é 𝑂(|𝑉|)
61
Busca em Largura
 Como
cada vértice é colocado na fila apenas 1
vez, a lista de adjacência de cada um só é
analisado 1 vez

Tempo 𝑂(|𝐸|)
 Portanto
o tempo de execução da busca em
largura é 𝑂(|𝑉| + |𝐸|)