AED Algoritmos e Estruturas de Dados
LEEC - 2005/2006
Teoria de Grafos eAlgoritmos em Grafos
AED (IST/DEEC) 2
Grafos - O que é um grafo?
• Objecto abstracto• Dois tipos de entidades
– Nós ou Vértices– Ramos ou Arestas
• Vértices representam– cidades, pessoas, máquinas,
números, etc• Arestas representam
– existência de ligações entrenós, valor da ligação entrenós, distância entre nós, etc
AED (IST/DEEC) 3
Grafos - Motivação• Mapas
– caminhos mais curtos; ca-minhos mais baratos.
• Circuitos Eléctricos– existência de curto-circui-
tos; existência de cruzamen-to entre ligações.
• Sequenciamento– tarefas a executar por um
conjunto de recursos sujei-tas a restrições de caráctertecnológico.
• Emparelhamento– processamento de imagem
estéreo; atribuição de pes-soas a lugares.
• Redes de dados– computadores ligados entre
si, enviando e recebendomensagens; existência de li-gação entre quaisquer nós; redundância.
• Estrutura de Programas– grafos gerados por compila-
dores representando a estru-tura de chamadas;
AED (IST/DEEC) 4
Grafos – Definições (1)• Def: Um grafo é um conjunto de vértices e um conjunto
de arestas que ligam pares de vértices distintos (com nunca mais que uma aresta a ligar qualquer par de vértices).
• Def: Dois vértices ligados por uma aresta dizem-se adjacentes.
• Def: Uma aresta que ligue dois vértices diz-se incidentede cada um dos vértices.
AED (IST/DEEC) 5
Grafos – Definições (2)• Def: O número de arestas incidentes num vértice diz-se o
grau desse vértice.
• Def: O subconjunto de arestas e vértices a elas associadosdiz-se um sub-grafo do grafo original.
• Def: Uma sequência de vértices na qual os vérticessucessivos estão ligados por arestas do grafo diz-se umcaminho.
AED (IST/DEEC) 6
Grafos – Definições (3)• Def: Num caminho simples os vértices e arestas são
distintos.
• Def: Um caminho em que todos os vértices e arestas sãodistintos, excepto para o primeiro e último que são iguais, diz-se um ciclo.
• Def: Dois caminhos simples dizem-se disjuntos se não possuírem vértices comuns, excepto possivelmente para osvértices extremos.
AED (IST/DEEC) 7
• Def: Um grafo diz-se ligado se existir um caminho de cadavértice para todos os outros vértices do grafo.
• Def: Um grafo que não seja ligado é constituído porcomponentes ligadas, que se dizem sub-grafos ligadosmáximos.
• Def: Um grafo ligado acíclico, i.e. sem ciclos, diz-se umaárvore.
Grafos – Definições (4)
AED (IST/DEEC) 8
Grafos – Definições (5)• Def: Um conjunto de árvores diz-se uma floresta.
• Def: A árvore de suporte de um grafo ligado é um sub-grafo que contém todos os vértices e é uma árvore.
• A floresta de suporte de um grafo é um sub-grafo quecontém todos os seus vértices e é uma floresta.
AED (IST/DEEC) 9
Grafos – Propriedades em árvores• Um grafo G de V vértices é uma árvore se e só se satisfizer
qualquer das seguintes condições:
– G tem V-1 arestas e nenhum ciclo.
– G tem V-1 arestas e é ligado.
– Existe apenas um caminho simples a unir quaisquer dois vértices.
– G é ligado mas retirando uma só aresta faz com que deixe de o ser.
AED (IST/DEEC) 10
Grafos – Exemplos (1)
• Os vértices 6 e 7 são adjacentes.• Os vértices 4 e 6 não são adjacentes.• O vértice 7 tem grau quatro.
1
4
2
76
5 8
3
G
AED (IST/DEEC) 11
Grafos – Exemplos (2)
• G’ é um sub-grafo de G, gerado a partir das arestas a cheio.• O vértice 5 não pertence a G’.• G é um grafo ligado; G’ não é.• O sub-grafo G’ é constituído por um grafo completo com três
vértices e por uma árvore com quatro vértices
1
4
2
76
5 8
3
G’
AED (IST/DEEC) 12
Grafos – Exemplos (3)
1
4
2
76
5 8
3
G
• Caminho: 1-2-4-5-7-8
AED (IST/DEEC) 13
Grafos – Exemplos (4)
1
4
2
76
5 8
3
G
• Ciclo: 3-4-5-6-7-8-3
AED (IST/DEEC) 14
Grafos – Exemplos (5)
1
4
2
76
5 8
3
G’’
• G’’: árvore de suporte de G.
AED (IST/DEEC) 15
• Introdução– Definição de grafo– Motivação aplicacional
• Definições e notação• Propriedades elementares em grafos• Exemplos
Grafos – Síntese da Aula 1
AED (IST/DEEC) 16
Grafos - Definições e Propriedades (1)• Def: Um grafo diz-se completo quando existe uma aresta
ligando qualquer par de vértices.
• Prop: Um grafo com V vértices possui, no máximo,V(V-1)/2 arestas.
• Def: Um grafo G’ diz-se complemento do grafo G quandose obtém a partir de um grafo completo com o mesmonúmero de vértices de G, retirando-lhe todas as arestas de G.
AED (IST/DEEC) 17
Grafos - Definições e Propriedades (2) • Def: Um grafo que possua um número de arestas próximo
do número máximo diz-se denso.
• Def: Um grafo cujo complemento seja denso diz-se esparso.
• Def: Densidade de um grafo: 2E/V, em que E é o númerode arestas e V o de vértices.
• Def: A um sub-grafo completo dá-se o nome de clique.
AED (IST/DEEC) 18
Grafos - Definições e Propriedades (3)• Def: Um grafo que possua a propriedade de ser possível
dividir os vértices em dois conjuntos tais que todas as arestas apenas ligam vértices de um conjunto a vértices do outro conjunto diz-se bipartido.
• Def: Quando existe um sentido atribuído às arestas, os grafos dizem-se direccionados, dirigidos ou digrafos.
• Def: O primeiro vértice de uma aresta direccionada diz-se fonte e o segundo diz-se destino.
AED (IST/DEEC) 19
Grafos - Definições e Propriedades (4)• Prop: Apenas os vértices destino são adjacentes dos vérti-
ces fonte.
• Def: Um ciclo direccionado num digrafo é um ciclo em que todos os pares de vértices adjacentes surgem pela ordem especificada pelas arestas.
• Def: Um digrafo sem ciclos direccionados diz-se grafo direccionado acíclico, ou DAG (Directed Acyclic Graph).
AED (IST/DEEC) 20
Grafos - Definições e Propriedades (5) • Def: Quando se atribuem pesos às arestas, representando
custo, distância, etc., diz-se que o grafo é ponderado.
– Também é possível atribuir pesos aos próprios vértices, ou a pares vértice/aresta.
• Def: Grafos ponderados direccionados, dizem-se redes.
AED (IST/DEEC) 21
Grafos - Interface ADT para Grafos (1)• Os algoritmos para processamento de grafos serão
desenvolvidos no contexto de uma ADT que define as tarefas de interesse.
• A nossa primeira interface elementar é tal que:– O número de vértices e arestas são especificados por inteiros;– Uma aresta é definida por um par de inteiros, designando os
vértices que une;– O número de vértices é limitado superiormente.
• Esta interface irá sendo alargada à medida das necessidades.
AED (IST/DEEC) 22
typedef struct {int v; int w;} Edge;Edge EDGE(int, int);
typedef struct graph *Graph;
Graph GRAPHinit(int);void GRAPHinsertE(Graph, Edge);void GRAPHremoveE(Graph, Edge);int GRAPHedges(Edge a[], Graph G);Graph GRAPHcopy(Graph);void GRAPHdestroy(Graph);
Grafos - Interface ADT para Grafos (2)
Graphinit cria grafo com o número final de vértices, sem arestas.GraphinsertE insere uma aresta, caso não exista.GraphremoveE retira uma aresta, caso exista.Graphedges conta o núme-ro de arestas.Graphcopy cria uma segun-da cópia do grafo.Graphdestroy faz o inver-so de Graphinit.
AED (IST/DEEC) 23
Grafos - Matriz de Adjacências (1)• Matriz de Adjacências
– Matriz (V×V) de valores booleanos;– A entrada correspondente à linha v e coluna w é 1
se existir uma aresta ligando estes dois vértices;– A mesma entrada vale 0 caso contrário;– A matriz é simétrica, excepto para digrafos, em
que poderá não sê-lo.
AED (IST/DEEC) 24
Grafos - Matriz de Adjacências (2)
• Matriz
1 2 3 4 5 6 7 81 1 1 0 1 0 0 0 02 1 1 0 1 0 0 0 03 0 0 1 1 0 0 1 14 1 1 1 1 1 0 0 05 0 0 0 1 1 1 1 06 0 0 0 0 1 1 1 07 0 0 1 0 1 1 1 18 0 0 1 0 0 0 1 1
Matriz V ×V simétrica
• Grafo
1
4
2
76
5 8
3
G
AED (IST/DEEC) 25
Grafos - Implementação de ADT (1)#include <stdlib.h>#include “GRAPH.h”struct graph {int V; int E; int **adj;};Graph GRAPHinit(int V){
Graph G = malloc(sizeof(struct graph));G->V = V; G->E = 0;G->adj = MATRIXint(V, V, 0);return G;}
void GRAPHinsertE(Graph G, Edge e){int v = e.v, w = e.w;if (G->adj[v][w] == 0) G->E++;G->adj[v][w] = 1; G->adj[w][v] = 1;
}
AED (IST/DEEC) 26
void GRAPHremoveE(Graph G, Edge e){int v = e.v, w = e.w;if (G->adj[v][w] == 1) G->E--;G->adj[v][w] = 0; G->adj[w][v] = 0;
}int GRAPHedges(Edge a[], Graph G){
int v, w, E = 0;for (v = 0; v < G->V; v++)for (w = v+1; w < G->V; w++)if (G->adj[v][w] == 1)a[E++] = EDGE(v, w);
return E;}
Grafos - Implementação de ADT (2)
AED (IST/DEEC) 27
• Definições e propriedades– Grafos completos, complemento de um grafo, densidade, cliques,
grafos bipartidos, grafos direccionados, ciclos em grafos direccionados, grafos ponderados, redes.
• Estrutura abstracta de dados para grafos– Interface elementar
• Matrizes de adjacência– Representação de um grafo– Implementação da estrutura abstracta de dados
Grafos – Síntese da Aula 2
AED (IST/DEEC) 28
Grafos - Listas de Adjacências (1)
• Listas de Adjacências
– Cada vértice possui uma lista ligada;
– Os elementos constituintes da lista de um vértice são os seus vértices adjacentes;
– Em grafos simples, se os vértices v e w são adjacentes, então w pertence à lista de v e v pertence àlista de w.
AED (IST/DEEC) 29
Grafos - Listas de Adjacências (2)
• Grafo
1
4
2
76
5 8
3
G
• Listas de Adjacências
1 424 8 73
13 2 544 6 75
6 5 77 35 6 88 3 7
4 21
Tabela com V listas de arestas
AED (IST/DEEC) 30
Grafos - Implementação de ADT (1)#include <stdlib.h>#include “GRAPH.h”
typedef struct node *link;struct node {int v; link next;};struct graph{int V; int E; link *adj;};
link NEW(int v, link next){link x = malloc(sizeof(struct node));x->v = v; x ->next = next;return x;
}
AED (IST/DEEC) 31
Graph GRAPHinit(int V)}int v; Graph G = malloc(sizeof(struct graph));G->V = V; G->E = 0;G->adj = malloc(V * sizeof(link));for (v = 0; v < V; v++)
G->adj[v] = NULL;return G;}
void GRAPHinsertE(Graph G, Edge e){int v = e.v, w = e.w;G->adj[v] = NEW(w, G->adj[v]);G->adj[w] = NEW(v, G->adj[w]);G->E++;}
Grafos - Implementação de ADT (2)
AED (IST/DEEC) 32
void GRAPHremoveE(Graph G, Edge e){/* Fica como exercício */ }
int GRAPHedges(Edge a[], Graph G){int v, E = 0; link t;for (v = 0; v < G->V; v++)for (t = G->adj[v]; t != NULL; t = t->next)
if (v < t->v )a[E++] = EDGE(v, t->v);
return E;}
Grafos - Implementação de ADT (3)
AED (IST/DEEC) 33
Grafos - Vantagens das M. de Adj.• Representação de eleição quando
– há espaço disponível;– os grafos são densos;– os algoritmos requerem mais que V2 operações.
• Adição e remoção de arestas é feita de forma eficiente;
• É fácil evitar a existência de arestas paralelas;
• É fácil determinar se dois vértices estão ou não ligados.
AED (IST/DEEC) 34
• Grafos esparsos de grande dimensão requerem espaço de memória proporcional a V2;
• Neste casos, a simples inicialização do grafo (proporcional a V2) pode ser do-minante na execução global do algoritmo;
• Pode nem sequer existir memória suficiente para armazenar a matriz.
Grafos - Inconvenientes das M. de Adj.
AED (IST/DEEC) 35
Grafos - Vantagens das L. de Adj.• Inicialização é proporcional a V.
• Utiliza sempre espaço proporcional a V+E– adequado para grafos esparsos.– algoritmos que assentem na análise de arestas em grafos esparsos.
• Adição de arestas é feita de forma eficiente.
AED (IST/DEEC) 36
• Arestas paralelas e adjacência entre vértices– requer que se pesquise as listas de adjacências, o que pode levar
um tempo proporcional a V.
• Remoção de arestas– pode levar um tempo proporcional a V (este problema pode ser
contornado).
• Não aconselhável para– grafos de grande dimensão que não podem ter arestas paralelas;– grande utilização de remoção de arestas.
Grafos - Inconvenientes das L. de Adj.
AED (IST/DEEC) 37
Grafos - Variantes e Extensões (1)• Outros tipos de grafos
– Digrafos• ambas facilmente extensíveis;• arestas representadas só uma vez;
– Grafos ponderados e redes• M. de Adj. preenchida com pesos;• L. De Adj. com campos extra para representação dos
pesos.
AED (IST/DEEC) 38
• Alteração da estrutura de dados– Tipo “EDGE” contendo informação adicional, para
além dos vértices que liga.
– Vectores indexados pelos vértices• Manutenção da informação do grau do vértice.
– Vector de arestas• Forma alternativa de representação de grafos.
Grafos - Variantes e Extensões (2)
AED (IST/DEEC) 39
Grafos - Representações alternativas• Três mecanismos básicos de representação de grafos
– Vector de arestas;– Matriz de adjacências;– Listas de adjacências.
• Produzem diferentes desempenhos ao nível das opera-ções de manipulação.
• Escolha deverá depender do problema a resolver.
AED (IST/DEEC) 40
Grafos – Desempenho Relativo
V. de Arestas M. de Adj. L. de Adj.Espaço E V2 V+E
Inicialização 1 V2 VCópia E V2 E
Destruição 1 V EInserir aresta 1 1 1
Encontrar aresta E 1 VRemover aresta E 1 V
Vértice isolado? E V 1Caminho de u a v? Elg*V V2 E
AED (IST/DEEC) 41
Grafos - Encontrar e remover arestas (1)• Eficientes em representações por matriz de adjacências.
• Como torná-las eficientes para as outras representações?
• Atribuir um símbolo inteiro a cada aresta– Aresta v-w fica com o símbolo v*V+w.
• Por exemplo, fazer uso de tabelas de dispersão (“hash-tables”)
• Quando uma aresta é inserida, é fácil testar se o símbolo já foi usado.
AED (IST/DEEC) 42
Grafos - Encontrar e remover arestas (2)
• Remoção em digrafos– ponteiro na tabela de dispersão para a sua representação
na lista de adjacências;– requer listas duplamente ligadas.
• Remoção em grafos simples– colocação de ambos os ponteiros na tabela de dispersão;– ou ponteiro entre os vértices.
AED (IST/DEEC) 43
• Listas de adjacência– Representação de um grafo– Implementação da estrutura abstracta de dados
• Comparação das representações alternativas– Vantagens e inconvenientes das matrizes de adjacência– Vantagens e inconvenientes das listas de adjacência
• Variantes e extensões– Grafos direccionados, ponderados e redes– Outras representações
• Comparação das representações alternativas– Memória e tempo de execução
Grafos – Síntese da Aula 3
Recommended
