Aula3 grafos

Prévia do material em texto

1
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
1
GrafosGrafos
Prof. Dr. Julio Arakaki 
www.pucsp.br/~jarakaki (jarakaki@pucsp.br)
Depto. Ciência da Computação
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
2
Grafos - RepresentaçãoGrafos - Representação
Como representar Grafos no computador?
Duas estruturas fundamentais
- Matriz
- Lista
Estrutura de dados
Qual é a estrutura mais adequada (ou mais eficiente)?
(Depende do Algoritmo)
2
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
3
Grafos – Matriz de AdjacênciaGrafos – Matriz de Adjacência
- Associar vértices às linhas e às colunas da matriz
- Cada elemento da matriz indica se há ou não aresta 
entre os vértices
Matriz de adjacência
Matriz n x n (n é número de vértices)
aij = 1 , se existe aresta entre vértices i e j
aij = 0 , caso contrário.
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
4
Grafos – Matriz de AdjacênciaGrafos – Matriz de Adjacência
3
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
5
Grafos – Matriz de AdjacênciaGrafos – Matriz de Adjacência
Exercícios:
a) Determine o grafo 
correspondente
b) Determine as matrizes de 
Adjacência correspondentes
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
6
Grafos – Matriz de IncidênciaGrafos – Matriz de Incidência
- Associar vértices às linhas e arestas às colunas da 
matriz
- Cada elemento da matriz indica se aresta incide sobre 
o vértice
Matriz de incidência
Matriz n x m (n vértices, m arestas)
aij = 1, se vértice i incide sobre aresta j
aij = 0, caso contrário.
4
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
7
Grafos – Matriz de IncidênciaGrafos – Matriz de Incidência
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
8
Grafos – Matriz de IncidênciaGrafos – Matriz de Incidência
Exercícios:
a) Determine o grafo 
correspondente
b) Determine as matrizes de Incidência 
correspondentes
5
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
9
Grafos – Matriz (Desvantagens)Grafos – Matriz (Desvantagens)
Grafos grandes e esparsos
grande: muitos vértices
esparso: relativamente com poucas arestas
Grande consumo de memória
Matriz formada principalmente de zeros!
Representação via listas
Associar a cada vértice uma lista de 
vértices adjacentes
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
10
Grafos – Lista de AdjacênciasGrafos – Lista de Adjacências
6
GrafosGrafosGrafosGrafos
© Julio Arakaki
Ciência da Computação
Representação/Implementação
11
Vantagens e DesvantagensVantagens e Desvantagens
- Testar adjacência (v1 e v2 são vizinhos)?
- Listar vizinhos de v?
- Inserir aresta?
- Remover aresta?
- ...
Tempo de execução para:
Qual a melhor estrutura de dados a ser utilizada?
Matriz ou Lista?