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