Grafos Estrutura de Dados

Prévia do material em texto

Estruturas de Dados
Grafos
Prof. Eduardo Alchieri
 
Grafos
(introdução)
 Grafo é um conjunto de pontos e linhas que conectam vários 
pontos
 Formalmente, um grafo G(V,A) é definido pelo par de conjuntos 
V e A, onde:
 V - conjunto não vazio: os vértices do grafo;
 A - conjunto de pares ordenados a=(v,w), v e w V: as ∈
arestas do grafo.
 Seja, por exemplo, o grafo G(V,A) dado por:
 V = {t | t é um time de futebol}
 A = {(v,w) | v é do mesmo estado de w}
São Paulo
Corintians Santos
PalmeirasNeste exemplo estamos considerando a relação
v é do mesmo estado de w, que é uma relação simétrica
G1:
 
Grafos
(conceitos)
 Digrafo (Grafo orientado)
 Considere o grafo definido a seguir:
 V = {t | t é um time de futebol}
 A = {(v,w) | v é melhor do que w}
 No caso de um digrado, as arestas são chamadas de 
arcos
Neste exemplo estamos considerando a relação
v é melhor do que w, que não é uma relação simétrica
São Paulo
Corintians Santos
Palmeiras
Inter
G2:
 
Grafos
(conceitos)
 Ordem: A ordem de um grafo G é dada pela cardinalidade do 
conjunto de vértices, ou seja, pelo número de vértices de G.
 Ordem de (G1) = 4
 Adjacência: em um grafo não orientado, dois vértices v e w são 
adjacentes se há uma aresta a = (v,w) em G. Esta aresta é dita 
ser incidente a ambos, v e w. É o caso de SAN e PAL em G1.
 No caso de digrafos, a adjacência é dividida em:
 Sucessor: um vértice w é sucessor de v se há um arco 
de v para w. Em G2, COR é sucessor de SPL.
 Antecessor: um vértice v é antecessor de w se há um 
arco de v para w. Em G2, SPL é antecessor de COR.
SPL
COR SAN
PAL
G1:
SPL
COR SAN
PAL
G2:
 
Grafos
(conceitos)
 Grau: o grau de um vértice é dado pelo número de arestas que 
lhe são incidentes. Em G1, grau de SAN = 3
 No caso de digrafos, a noção de grau é dividida em:
 Grau de emissão: corresponde ao número de arcos 
que partem de um vértice v
 Em G2, grau de emissão de COR = 1
 Grau de recepção: corresponde ao número de arcos 
que chegam a um vértice v
 Em G2, grau de recepção de PAL = 2
 Fonte: Um vértice v é uma fonte caso seu grau de recepção for 
zero. Exemplo, SPL em G2.
 Sumidouro: Um vértice v é um sumidouro caso seu grau de 
emissão for zero. Exemplo, PAL em G2.
SPL
COR SAN
PAL
G1:
SPL
COR SAN
PAL
G2:
 
Grafos
(conceitos)
 Grafo valorado: um grafo G(V,A) é dito ser valorado quando 
existe uma ou mais funções relacionando V e/ou A com um 
conjunto de números.
 Seja G(V,A) onde:
 V = {v | v é uma cidade com aeroporto}
 A = {(v,w,t) | <há linha aérea ligando v a w, sendo t o 
tempo esperado de voo>}
 
Grafos
(conceitos)
 Multigrafo: um grafo G(V,A) é dito ser um multigrafo quando 
existem múltiplas arestas entre pares de vértices de G. No 
grafo G8, por exemplo, há duas arestas entre os vértices A e C 
e entre os vértices A e B, caracterizando-o como um multigrafo
 Subgrafo: um grafo G
s
(V
s
, A
s
) é dito ser subgrafo de um grafo 
G(V,A) quando V
s
 V e A⊆
s
 A. O grafo G⊆
9
, por exemplo, é 
subgrafo de G
8
.
 
Grafos
(conceitos)
 Grafo conexo: um grafo G(V,A) é dito ser conexo se há pelo menos 
uma cadeia ligando cada par de vértices deste grafo G
 Grafo desconexo: um grafo G(V,A) é dito ser desconexo se há 
pelo menos um par de vértices que não está ligado por 
nenhuma cadeia
 
Grafos
(conceitos)
 Base: uma base de um grafo G(V,A) é um subconjunto B V, tal que:⊆
 Dois vértices quaisquer de B não são ligados por nenhum caminho
 Todo vértice não pertencente a B pode ser atingido por um caminho 
partindo de B
 Anti-base: uma anti-base de um grafo G(V,A) é um subconjunto AB V, tal ⊆
que:
 Dois vértices quaisquer de AB não são ligados por nenhum caminho
 De todo vértice não pertencente a AB pode ser atingir AB por um 
caminho
 
Grafos
(conceitos)
 Raiz: se a base de um grafo G(V,A) é um conjunto unitário, então esta base 
é a raiz de G
 Anti-raiz: se a anti-base de um grafo G(V,A) é um conjunto unitário, então 
esta anti-base é a anti-raiz de G
 
Grafos
(implementação)
 Matriz de Adjacência
 Cada posição na matriz é um arco
 Linha indica o nó de saida do arco
 Coluna indica o nó de chegada
 Valor da posição indica a existência ou não do arco (também pode 
indicar o peso associado ao arco)
 Deve ser utilizada para grafos densos, onde o número de arcos |A| é 
próximo do número de vértices ao quadrado |V|2
 Complexidade de espaço O(V2)
 O tempo necessário para acessar um elemento é constante
 Ler ou examinar a matriz tem complexidade de tempo O(V2)
 
Grafos
(implementação)
 Matriz de Adjacência
 
Grafos
(implementação)
 Lista de Adjacência
 Os vértices de uma lista de adjacência são em geral armazenados em 
uma ordem arbitraria
 Possui uma complexidade de espaco O(|V| + |A|)
 Indicada para grafos esparsos, onde |A| é muito menor do que |V|2
 É compacta e usualmente utilizada na maioria das aplicações
 Tempo O(|V|) para determinar se existe uma aresta entre os vértices i e 
j, pois podem existir O(|V|) vértices na lista de adjacentes do vertice i
 
Grafos
(implementação)
 Lista de Adjacência
 
Grafos
(aplicações)
 Muitos problemas reais podem ser reduzidos a problemas em 
grafos
 Vértices são cidades e arcos são estradas: os grafos 
auxiliam a tracar os caminhos e descobrir o caminho mais 
curto (ou mais longo) entre cidades
 Vértices são terminais de dispositivos eletrônicos e arcos 
representam as conexões entre esses terminais
 Vértices são tarefas em um projeto e arcos representam as 
dependências entre as tarefas
 
Grafos
(busca)
 Busca: o objetivo de uma busca é explorar um grafo, i.e., 
obter um processo sistemático de como cominhar por 
seus vértices e arestas
 Raiz da busca: o vértice inicial da busca
 Existem basicamente dois tipos de busca
 Profundidade
 Busca o mais profundo no grafo sempre que 
possível
 Largura
 Busca primeiro nos vértices localizados a uma 
mesma distância da raiz de busca
 
Grafos
(busca em profundidade)
 A estratégia é buscar o mais profundo no grafo sempre que 
possível
 Os arcos são exploradas a partir do vértice v mais 
recentemente descoberto que ainda possui arestas não 
exploradas saindo dele
 Quando todas as arestas adjacentes 
a v tiverem sido exploradas a busca
anda para trás para explorar vértices 
que saem do vértice do 
qual v foi descoberto
 
Grafos
(busca em profundidade - algoritmo)
 busca_profundidade (inicio, alvo, G)
 empilha(pilha, inicio); e marque inicio
 Enquanto !estaVazia(pilha) faça
 v = getTopo(pilha);
 Av = o conjunto de arestas\arcos de v ainda não exploradas em G
 Se (Av != null) então
 retire um arco\aresta (v,w) de Av
 Se (w não está marcado) então
 Se (w == alvo) então retorne w;
 marque e empilhe w (empilhe(pilha,w))
 Senão
 desempilhe(pilha); //retira v do topo da pilha
 retorne null; 
 
Grafos
(busca em profundidade - algoritmo)
 Execute o algoritmo com o seguinte digrafo G(V,A)
 V = {1,4,5,6,7,8}
 A = {(1,4), (4,5), (4,6), (1,7), (7,6), (7,8)}
 Considere o vértice inicial = 1 e o alvo = 8.
 
 
Grafos
(busca em largura)
 Expande a fronteira entre vértices descobertos e não 
descobertos uniformemente através da largura da fronteira
 O algoritmo descobre todos os vertices a uma distância k do 
vértice de origem antes de descobrir qualquer vértice a uma 
distância k + 1Grafos
(busca em largura - algoritmo)
 busca_largura (inicio, alvo, G)
 enfileirar(fila,inicio); e marque inicio
 Enquanto !estaVazia(fila) faça
 v = desenfileirar(fila);
 Se (v == alvo) então retorne v;
 Av = o conjunto de arestas\arcos de v em G
 para cada (v,w) em Av tal que w não está marcado faça:
 marque e enfileire w (enfileirar(fila,w))
 retorne null; 
 
Grafos
(busca em largura - algoritmo)
 Execute o algoritmo com o seguinte digrafo G(V,A)
 V = {1,4,5,6,7,8}
 A = {(1,4), (4,5), (4,6), (1,7), (7,6), (7,8)}
 Considere o vértice inicial = 1 e o alvo = 8.
 
 
Grafos
(busca)
 Complexidade temporal de ambos os algoritmos de busca é
O(|V|+|A|)
 Complexidade espacial da busca em profundidade é O(h), onde 
h é o comprimento do mais longo caminho no grafo
 Complexidade espacial da busca em largura é O(|V|)
 
 
Grafos
(Ordenamento Topológico)
 Uma ordenação topológica de um digrafo acíclico (DAG) é uma 
ordem linear de seus nós em que cada nó vem antes de todos 
nós para os quais este tenha arestas de saída
 Ordenaçao linear de todos os vértices, tal que se DAG 
contém uma aresta (u, v) então u aparece antes de v
 Pode ser vista como uma ordenação de seus vértices ao 
longo de uma linha horizontal de tal forma que todas as 
arestas estão direcionadas da esquerda para a direita
 Um grafo pode ter vários ordenamentos topológicos possíveis
 
 
Grafos
(Ordenamento Topológico)
 Exemplo:
 Possíveis ordenações topológicas?
 7, 5, 3, 11, 8, 2, 9, 10
 3, 5, 7, 8, 11, 2, 9, 10
 3, 7, 8, 5, 11, 10, 2, 9
 5, 7, 3, 8, 11, 10, 9, 2
 7, 5, 11, 3, 10, 8, 9, 2
 7, 5, 11, 2, 3, 8, 9, 10 
 
Grafos
(Ordenamento Topológico)
 Algoritmo
 Simular no exemplo anterior!
 
Grafos
(Ordenamento Topológico)
 Aplicações
 Programação de uma sequência de trabalhos ou tarefas
 Exemplo (escalonamento de tarefas):
 
Grafos
(Caminho mais curto)
 Muitas das aplicações de grafos necessitam encontrar o 
caminho mais curto entre dois vertices de um grafo ponderado
 Para isso consideraremos um grafo com arestas ponderadas 
(valoradas), tanto direcionais como não direcionais, nos quais o 
peso se refere ao custo de atravessar a aresta (as unidades de 
custo dependem da aplicação)
 Exemplo: um grafo direcionado para representar uma rede 
de aeroportos
 Vértices representam os aeroportos
 Arestas representam os vôos disponíveis entre os 
aeroportos
 Custo das arestas podem representar: o tempo de 
vôo, o custo do vôo, a distância entre os aeroportos, 
etc.
 
Grafos
(Caminho mais curto)
 Existem duas abordagens para se calcular o caminho mais 
curto
 Caminho mais curto a partir de uma única fonte
 Algoritmo de Djikstra
 Caminho mais curto entre todos os pares de vértices do 
grafo
 Algoritmo de Floyd
 
Grafos
(Algoritmo de Djikstra)
 Escolhido um vértice como raiz da busca, este algoritmo 
calcula o custo mínimo deste vértice para todos os demais 
vértices do grafo
 O algoritmo pode ser usado sobre grafos orientados, ou não, e 
considera que todas as arestas possuem pesos não negativos 
(nulo é possível)
 
Grafos
(Algoritmo de Djikstra)
 Seja G(V,A) um grafo direcionado e v um vértice de G:
1. Atribuição de distâncias:
 0 ao vértice inicial v;
 ∞ aos demais.
2. Marcar todos os vértices como abertos (não visitados) e o inicial 
como atual
3. Para cada vértice aberto adjacente ao atual, atribua a distância 
estimada dele até o nó inicial. Se a distância for menor que a 
distância registrada, atualize o valor.
4. Depois de processar todos os nós abertos adjacentes ao atual, 
marque-o como fechado (visitado). Sua distância é final e mínima.
5. Escolha o nó aberto de menor distância como novo nó atual e vá 
para 3, termine se não houver.
 
Grafos
(Algoritmo de Djikstra)
 Exemplo:
 
Grafos
(Algoritmo de Djikstra)
 Aplicações
 Protocolos de roteamento dinâmicos (OSPF, IS-IS).
 Algoritmo de planejamento de rota.
 Análise de circuitos elétricos.
 Etc.
 
Grafos
(Árvore Geradora de Custo Mínimo)
 Considere um grafo não direcionado e conectado; e que 
associada a cada arco há uma distância não negativa.
 O objetivo é encontrar o caminho mais curto de tal maneira que 
os arcos fornecam um caminho entre todos os pares de nós
 O subgrafo que conecta todos os vértices é uma árvore 
geradora. Essa árvore é uma árvore geradora mínima se o 
comprimento total é o menor possível
 Este subgrafo possui as seguintes propriedades
 Possui o mesmo conjunto de vértices do grafo
 É conexo
 É acíclico
 
Grafos
(Árvore Geradora de Custo Mínimo)
 Podem haver várias árvores geradoras mínimas, com o mesmo 
comprimento
 Se cada arco tem um peso diferente, existe uma única árvore 
geradora mínima
 A árvore geradora mínima é o subgrafo de menor custo conectando 
todos os vértices
 
Grafos
(Árvore Geradora de Custo Mínimo)
 Algoritmo de Prim: as arestas adicionadas ao subconjunto (árvore) 
devem ser as de mínimo peso que conectam a árvore a um vértice 
ainda não presente
 Entrada: um grafo G(V,A) conectado e ponderado (valorado)
 Inicialize V' = {u}, onde u é um nó arbitrário de V e A' = {}
 Repita até que V' = V:
 Escolha uma aresta (u, v) de A com o mínimo peso tal que u 
esteja em V' e v ainda não
 Adicione v a V' e (u, v) a A'
 Saída: subgrafo G'(V',A'), que é a árvore geradora mínima de G
 
Grafos
(Árvore Geradora de Custo Mínimo)
 Exemplo: 
 
Grafos
(Árvore Geradora de Custo Mínimo)
 Exemplo de Aplicação: instalação de fíbras ópticas no campus 
de uma universidade
 Cada trecho de fíbra óptica entre os prédios possui um 
custo associado
 Um grafo fornece todas as conexões possíveis entre os 
prédios
 Uma árvore geradora fornece um modo de conectar todos 
os prédios sem redundância
 Uma árvore geradora mínima desse grafo nos daria uma 
árvore com o menor custo para fazer essa ligação
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38