TEMA_1 3_-_ARA0175_-_REPRESENTA__O_DE_GRAFOS

Prévia do material em texto

Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TEMA 1.3 – REPRESENTANDO GRAFOS
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
REPRESENTAÇÃO DOS GRAFOS
Grafos – Representando Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 3
Representações computacionais comuns de grafos
• Matriz de adjacência (Matriz)
• Matriz de Incidência (Matriz)
• Listas de adjacências (Lista encadeada)
Grafos – Matriz de adjacência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 4
1
2
54
3
𝐺
1 2 3 4 5
1 0 1 1 0 0
2 1 0 1 1 0
3 1 1 0 1 1
4 0 1 1 0 1
5 0 0 1 1 0
Matriz de Adjacência de 𝐺
A Matriz de adjacências de um grafo é uma matriz de 0’s e 1’s com
colunas e linhas indexadas pelos vértices do grafo.
Grafos – Matriz de adjacência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 5
1
2
54
3
𝐺
1 2 3 4 5
1 0 1 1 0 0
2 1 0 1 1 0
3 1 1 0 1 1
4 0 1 1 0 1
5 0 0 1 1 0
Matriz de Adjacência de 𝐺
A Matriz de adjacências de um grafo é uma matriz de 0’s e 1’s com
colunas e linhas indexadas pelos vértices do grafo.
Grafos – Matriz de adjacência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 6
1
2
54
3
𝐺
1 2 3 4 5
1 2 1 1 0 0
2 1 0 1 1 0
3 1 1 0 1 1
4 0 1 1 0 1
5 0 0 1 1 0
Matriz de Adjacência de 𝐺
A Matriz de adjacências de um grafo é uma matriz de 0’s e 1’s com
colunas e linhas indexadas pelos vértices do grafo.
Laço é contado 
das vezes.
Grafos – Matriz de adjacência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 7
Característica do Grafo em Matriz de adjacências
• Usado para representar grafos densos, que possuem mais arestas.
• Complexidade de espaço: Θ(𝑛2)
• Se o grafo é simples, o grau de um vértice é dado pela soma dos elementos
de sua linha (ou coluna) correspondente.
Grafos – Matriz de Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 8
Grafos – Matriz de Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 9
Seja 𝐺 um grafo com 𝑛 vértices e 𝑚 arestas. A matriz de incidência
de 𝐺 é uma matriz de ordem 𝑛 × 𝑚, denotada por 𝐴 = [𝑎𝑖𝑗],
definida:
Grafos – Matriz de Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 10
1
2
54
3
𝐺
a b c d e f
1 1 1
2 1 1 1
3 1 1 1
4 1 1
5 1 1
Matriz de Incidência de 𝐺
a b
c d
e
f
Grafos – Matriz de Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 11
1
2
54
3
𝐺
a b c d e f
1 1 1 0 0 0 0
2 1 0 1 0 0 1
3 0 1 0 1 0 1
4 0 0 1 0 1 0
5 0 0 0 1 1 0
Matriz de Incidência de 𝐺
a b
c d
e
f
Grafos – Matriz de Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 12
1
2
54
3
𝐺
a b c d e f
1 1 1 0 0 0 0
2 1 0 1 0 0 1
3 0 1 0 1 0 1
4 0 0 1 0 1 0
5 0 0 0 1 1 0
Matriz de Incidência de 𝐺
a b
c d
e
f
Grafos – Matriz de Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 13
Característica do Grafo em Matriz de Incidência
• Necessita de rotulação nas arestas.
• Complexidade de espaço: Θ(𝑛𝑚)
• Apenas grafos que não possuem arestas paralelas podem ser armazenados.
• Como cada aresta é incidente em exatamente dois vértices, cada coluna de
𝐴(𝐺) possui exatamente dois 1’s.
• O número de 1’s em cada linha é igual ao grau do vértice correspondente.
Grafos – Matriz de Adjacência e Incidência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 14
• As duas representações anteriores (matrizes de adjacência e de incidência)
são importantes porque elas facilitam a recuperação de uma série de
informações a respeito de um grafo. Por exemplo o grau de um vértice,
determinar se dois vértices são adjacentes, entre outras.
• É possível encontrar formar mais eficientes de armazenamento de dados.
Grafos – Lista de adjacência 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 15
1
2
54
3
𝐺
Lista de Adjacência de 𝐺
O vetor de listas de adjacência de um grafo tem uma lista encadeada
associada com cada vértice do grafo. A lista associada com um vértice
𝑣 contém todos os vizinhos de 𝑣.
21
2
3
4
5
1
1
2
4
3
3 4
2 4 5
3 5
3
Grafos – Exercício
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 16
1. Dado os grafos abaixo, forneça sua representação gráfica, Matriz
de Adjacência e Lista de Adjacência:
a) 𝐺(𝑉, 𝐴) = {V = {a,b,c}, A = {}}
b) 𝐺(𝑉, 𝐴) = {V = {1,2,3,4}, A = {{1,2},{2,3},{3,4},{4,1}}}
c) 𝐺(𝑉, 𝐴) = {V = {x,y,z,w}, A = {{x,y}{w,z},{y,z}}}
d) 𝐺(𝑉, 𝐴) = {V = {a,b,c,d,e}, A = {{a,b},{a,c},{a,d},{a,e}}} 
Grafos – Exercício
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 17
2. Dado os grafos abaixo, forneça a matriz de adjacência, de
incidência e a lista de adjacência:
2
1
4
3
𝐺1
𝐺2
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
IMPLEMENTAÇÃO DE GRAFOS
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 19
Vamos representar o seguinte grafo 𝐺 em uma matriz de adjacências:
Matriz de Adjacências em Python
2
14
3
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 20
2
14
3
Vamos representar o seguinte grafo 𝐺 em uma matriz de adjacências:
Matriz de Adjacências em Python
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 21
Matriz de Adjacências em Python
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 22
Matriz de Adjacências em Python
Gera a matriz 𝑛 𝑥 𝑛
preenchida com 
zeros.
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 23
Matriz de Adjacências em Python
Grafo não direcionado
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 24
Matriz de Adjacências em Python
Imprime a Matriz de 
adjacência.
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 25
2
14
3
Matriz de Adjacências em Python
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 26
𝑎
𝑏
𝑒𝑑
𝑐
Seja o seguinte grafo 𝐺:
Lista de Adjacências em Python
Exemplo:
a ['b', 'c']
b ['a', 'c', 'd']
c ['b', 'e', 'a', 'd']
d ['b', 'c', 'e']
e ['c', 'd']
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 27
lista_vertices = ['a', 'b', 'c', 'd', 'e']
𝑎
𝑏
𝑒𝑑
𝑐
Seja o seguinte grafo 𝐺:
Lista de Adjacências em Python
Exemplo:
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 28
Lista de Adjacências em Python
𝑎
𝑏
𝑒𝑑
𝑐
lista_arestas = [('a', 'b'), ('b', 'a'), ('b', 'c’), 
('c', 'b’), ('c', 'e'), ('e', 'c’), 
('c', 'a'), ('a', 'c'), ('b', 'd’), 
('d', 'b'), ('d', 'c'), ('c', 'd’), 
('d', 'e'), ('e', 'd')]
Seja o seguinte grafo 𝐺:Exemplo:
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 29
Lista de Adjacências em Python
Função de montagem do grafo 𝑮:Exemplo:
def cria_grafo(lista_vertices, lista_arestas):
grafo = {}
for vertice in lista_vertices:
grafo[vertice] = []
for aresta in lista_arestas:
grafo[aresta[0]].append(aresta[1])
return grafo
𝑎
𝑏
𝑒𝑑
𝑐
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 30
Lista de Adjacências em Python
Função de montagem do grafo 𝑮:Exemplo:
𝑎
𝑏
𝑒𝑑
𝑐
Cada vértice é uma chave 
e cada chave tem uma lista 
vazia.
def cria_grafo(lista_vertices, lista_arestas):
grafo = {}
for vertice in lista_vertices:
grafo[vertice] = []
for aresta in lista_arestas:
grafo[aresta[0]].append(aresta[1])
return grafo
Grafos – Implementação de Grafos em Python
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 31
Lista de Adjacências em Python
Função de montagem do grafo 𝑮:Exemplo:
def cria_grafo(lista_vertices, lista_arestas):
grafo = {}
for vertice in lista_vertices:
grafo[vertice] = []
for aresta in lista_arestas:
grafo[aresta[0]].append(aresta[1])
return grafo
𝑎
𝑏
𝑒𝑑
𝑐
Cada aresta é adicionada 
em seu vértice incidente
Grafos – Exercício de Implementação
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 32
1. No algoritmo em Python de Matriz de Adjacência,implemente:
a) Uma função que some os graus dos vértices.
b) Uma função que verifique se o grafo é nulo.
2. No algoritmo em Python de Lista de Adjacência, implemente:
a) Uma função que calcule qual o vértice de grau máximo (Δ(𝐺)).
3. Implemente em Python o algoritmo que apresente a Matriz de incidência de
um grafo.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 33
Dúvidas?