Grafos - C /C++ PDF

Preview

Summary

Download Grafos - C /C++ PDF

Description

Grafos - T exto d e Apoio Definição de Grafo. Representação matricial (matriz de adjacência). Implementação de operações básicas. Representação por listas ligadas.

1.

Conceitos In trodutó rios

Um Grafo consiste num conjunto de Vértices (ou Nós) e num conjunto de Arcos que unem os vértices. Cada arco é definido a partir de um par de vértices. Dizemos que o grafo é não dirigido quando a ordem dos vértices em cada par que define um arco não for relevante, isto é, quando os arcos não têm associado um sentido. Se a ordem dos vértices em cada par não for comutativa, isto é, se os arcos tiverem associado um sentido, estamos em presença de um grafo dirigido ou digrafo. Exemplos de grafos (não dirigidos): V. Castelo Barcelos A

B

Braga

C D E

Guimarães Porto

Exemplos de grafos dirigidos: A

B C D E

Pode ainda existir informação (numérica) associada ao arco (peso), que representa por exemplo uma distância, um custo, etc. Essa informação chama-se peso e o grafo designa-se grafo pesado ou rede.

Exemplos de grafos pesados:

V. Castelo 30

Barcelos 20 Braga

70 50 50

20 Guimarães

Porto

Dois vértices dizem-se adjacentes se existir um arco do primeiro para o segundo. Porto e Guimarães são adjacentes, mas Porto e Barcelos não o são. Um nó A diz-se adjacente de um nó B se houver um arco de B para A. Chama-se Grau de um vértice ao número de arcos que nele incidem. No caso de um grafo dirigido fala-se em grau de entrada como sendo o número de arcos que entram num nó e em grau de saída como o número de arcos que dele saem. Define-se um caminho como uma sequência de vértices distintos, cada um adjacente com o seguinte. Define-se um caminho de comprimento k do vértice A para o vértice B como uma sequência de k+1 vértices n1, n2, ..., nk, nk+1 em que n1 = A e nk+a = B e ni é adjacente de ni+1 para 1  i  k. Um ciclo é um caminho que contém pelo menos três vértices, em que o último é adjacente do primeiro. Dito de outra forma, um ciclo é um caminho de um nó para ele próprio. Um grafo que contenha um ciclo chama-se cíclico. Um grafo sem ciclos chama-se acíclico. As árvores são, como sabemos, grafos acíclicos.

2.

Repres entaç ão Matricial de Grafos

Um grafo pode ser representado por uma matriz de adjacência, que consiste numa tabela bidimensional – matriz – em que cada linha está associada a um dado vértice do grafo. A tabela ou matriz de adjacência tem a seguinte interpretação: o elemento [ i, j ] é verdadeiro ou é igual a 1 se existir um arco de i para j. Tratando-se de um grafo não dirigido, ao ser verdadeiro [ i, j ] também é verdadeiro [ j, i ]. Num grafo não dirigido, a matriz de adjacência é simétrica. Numa matriz de adjacência, o número de elementos iguais a 1 (ou com valor lógico verdadeiro) ao longo de uma linha, indica-nos o grau de saída desse nó. O número de elementos 1 (ou verdadeiro) numa coluna dá-nos o grau de entrada. Vejamos um grafo e a correspondente matriz de adjacência:

---- 2 ----

Vejamos a definição desta estrutura de dados. Considera-se que a constante max representa o número máximo de nós. Para cada elemento [i, j] é associado o valor lógico verdadeiro ou falso consoante existe um arco de i para j. Const max = 100 Tipo Matriz_Adj = Array [1..max; 1..max] de booleano (ou inteiro)

Tratando-se de um grafo pesado, a matriz de adjacência será substituída por uma matriz de pesos e adjacência, e considera-se que cada elemento [i, j] é um registo com dois campos. Um é o campo lógico que indica a existência do arco de i para j, o outro é um número inteiro com o peso associado ao arco. Const max = 100 Tipo arco = registo existe: booleano peso: inteiro Matriz_Adj = Array [1..max; 1..max] de arco

3.

Alguma s Operaç ões B ásicas (ba sead as n a re presentação matricial) Algumas operações básicas definidas para os grafos são: − Juntar(Matriz, X, Y)

cria um arco do vértice X para o vértice Y;

− Remover(Matriz, X, Y)

remove o arco entre os vértices X e Y;

− Adjacente(Matriz, X, Y)

função de devolve o valor lógico verdadeiro se existir Um arco de X para Y

---- 3 ----

Para os grafos pesados, as operações Juntar e Remover são ligeiramente alteradas, de forma a contemplar também o peso do arco. Termos assim: − Juntar_P(Matriz, X, Y, P)

cria um arco de X para Y com peso P.

− Remover_P(Matriz, X, Y, P) remove o arco entre X e Y e devolve como argumento de saída o peso desse arco. A sua implementação usando a representação do grafo segundo matriz de adjacência é bastante simples. Const max = 100 Tipo Matriz_Adj = Array [1..max; 1..max] de inteiro

(ou booleano)

Procedimento juntar(var mat: matriz_adj; X, Y: inteiro) mat[X,Y]  1

Se o grafo não fosse dirigido, para garantir a simetria da matriz, passaríamos a ter: Procedimento juntar(var mat: matriz_adj; X, Y: inteiro) mat[X,Y]  1 mat[Y,X]  1 Procedimento remover(var mat: matriz_adj; X, Y: inteiro) mat[X,Y]  0

(mat[Y,X]  0 caso fosse não dirigido )

Função adjacente(mat: matriz_adj; X,Y:inteiro): booleano adjacente  mat[X,Y] = 1

à seria mais simples se o array matriz_adj fosse booleano em lugar de inteiro... Função adjacente(mat: matriz_adj; no1,no2:inteiro): booleano adjacente  mat[X,Y]

Considerando agora o grafo pesado: Tipo arco = registo existe: inteiro peso: inteiro

(ou booleano)

Matriz_Peso_Adj = Array [1..max; 1..max] de arco Procedimento juntar_p(var mat: mat_peso_adj; X, Y: inteiro; peso: inteiro) mat[X,Y].existe  1 mat[X,Y].peso  peso

---- 4 ----

Procedimento remover_p(var mat: mat_peso_adj; X, Y: inteiro; var peso: inteiro) peso  mat[X,Y].peso mat[X,Y].existe  0

Tendo um grafo representado através de uma matriz de adjacência, os problemas dos grafos transformam-se um problemas algébricos de manipulação de matrizes. Se na matriz de adjacência (a que chamaremos Adj) Adj[i, j] for verdadeiro (ou 1) então existe um arco de i para j, isto é, há caminho de comprimento 1 de i para j. Da mesma forma, se Adj[i, k] e Adj[k, j] forem ambos verdadeiros, significa existir um caminho de comprimento 2 i para j, passando por k. Generalizando, a expressão: (adj[i,1] e adj[1,j]) ou (adj[i,2] e adj[2,j]) ou ... ou (adj[i,max] e adj[max,j])

onde max é o número de nós do grafo, é verdadeira se existir pelo menos um caminho de comprimento 2 de i para j passando por qualquer outro nó. É possível construir a matriz dos caminhos de comprimento 2 (Adj2) que, para cada posição [i, j] integra a fórmula acima. Essa matriz pode ser obtida calculando o produto booleano de Adj com ela própria. O produto booleano é calculado de forma semelhante à multiplicação de matrizes, substituindo a multiplicação pela conjunção (e) e a adição pela disjunção (ou). Para o grafo da página 3, a matriz dos caminhos de comprimento 2 é calculada como abaixo apresentado:

A partir da matriz adj2 podemos concluir que só há caminhos de comprimento 2 de A para D, de A para E, de B para D e de C para D. Da mesma forma poderíamos calcular Adj3. Adj k .= Adj k - 1 x Ad j (onde x representa o produto booleano) Se pretendermos construir uma matriz que nos indique se existe um caminho (qualquer que seja o comprimento deste) entre dois nós, temos de calcular a disjunção (ou) das matrizes de caminhos de todos os comprimentos sobre esse grafo.

---- 5 ----

Contudo, num grafo com n nós qualquer caminho de comprimento maior ou igual a n tem forçosamente que possuir nós repetidos. Ou seja, tem de existir um ciclo que pode ser removido, encurtando o caminho. A matriz caminho é chamada de fecho transitivo da matriz de adjacência. Dado um grafo com max vértices, o caminho entre um vértice i e um vértice j, se existir, encontrar-se-á na matriz caminho dada pela disjunção de todas as matrizes adjacência de comprimento entre 1 e max-1: caminho[i,j ] = adj[ i,j ] or adj 2 [i, j] or ... or a dj m a x - 1 [i,j ]

4.

Repres entaç ão de Grafos po r uma Tab ela de Listas Ligada s

A representação de um grafo que vimos na secção 3 (através de uma matriz de adjacência) sofre de algumas limitações: −

é necessário conhecer antecipadamente o número de vértices para definir a dimensão da matriz, o que tanto pode representar um elevado desperdício de espaço ocupado, como pode deixar de responder à necessidade de representação de um grafo cujo número de vértices seja superior ao definido;

−

o espaço ocupado é sempre igual, quer o grafo possua poucos arcos ou muitos arcos; por exemplo, um grafo com 100 vértices implica 100x100 (10.000) células para armazenar os seus arcos, acontecendo com frequência que o espaço efectivamente ocupado seja inferior a 5% deste valor.

Uma solução seria representar os vértices numa tabela de apontadores (array), onde cada apontador é a “cabeça” ou o início de uma lista (ligada) de arcos que saem desse vértice. Teríamos assim um array onde armazenaríamos os vértices e os tais apontadores para a lista de vértices adjacentes, ou seja, a lista de arcos. Cada elemento da lista ligada linear de arcos é composto por dois campos: um campo com o vértice que é destino do arco em questão e, uma vez que se trata de uma lista ligada, um apontador para o arco seguinte. Se se tratar de um grafo pesado, existiria um terceiro campo, com o peso do arco. O destino de um arco é dado pelo índice da posição do array que corresponde a esse arco.

---- 6 ----

A declaração que corresponde a esta estrutura é a seguinte: const max = 100 tipo ap_arco = ^arco arco = record destino: inteiro {peso: inteiro - só para o caso de ser um grafo pesado} prox: ap_arco grafo = array [1..max] de ap_arco

Contudo, esta estrutura, apesar de resolver alguns problemas relativamente à representação matricial, exige ainda que seja conhecido previamente o número de vértices do grafo.

5.

Repres entaç ão de Totalmente L igada

Grafos

por

u ma

Es trutura

A alternativa relativamente à solução anterior corresponde a substituir também o array (estrutura estática) por uma estrutura dinâmica (lista ligada). Assim, para representar um grafo, precisamos de uma lista ligada dos vértices e, para cada vértice, uma lista de adjacências (lista ligada com os arcos) que saem desse vértice. Estamos perante uma representação segundo uma estrutura totalmente ligada. Para a lista dos vértices, consideram-se três campos: −

inf_vertice – campo com a informação associada ao vértice (agora não é possível reconhecer os vértices pela sua posição no array (índice do array).

−

prox_vertice – campo apontador para o próximo vértice na lista de vértices.

−

arcos – apontador para o início da lista ligada de arcos que emergem do vértice. ---- 7 ----

Os arcos continuam a ser representados em tantas listas quantos os vértices. Cada elemento da lista de arcos possui dois apontadores: −

prox_arco – apontador para o próximo arco da lista ligada de arcos que saem do vértice na origem da lista;

−

destino – apontador para o vértice onde o arco termina.

A declaração que corresponde a esta estrutura é a seguinte: const max = 100 tipo ap_arco = ^arco ap_vertice = ^vertice arco = record destino: ap_vertice prox_arco: ap_arco vertice = record inf_vertice: dados prox_vertice: ap_vertice arcos: ap_arco var grafo: ap_vertice

no caso de um grafo pesado, cada arco teria ainda um campo do tipo inteiro com o peso do arco: arco = record destino: ap_vertice peso: inteiro prox_arco: ap_arco

---- 8 ----

Percorrer a lista de arcos que sai de um vértice nesta representação ligada é equivalente a atravessar a linha correspondente da matriz de adjacência. Contudo, na matriz de adjacência é possível obter todos os arcos que chegam a um nó percorrendo a coluna correspondente. Não há uma forma eficiente de fazer o mesmo na estrutura ligada.

6.

Alguma s Operaç ões B ásicas (ba seadas n a re presentação segu ndo um a estru tura totalmente l igada)

Nesta secção vamos adaptar as operações vistas na secção 3 para esta nova representação do grafo. A função adjacente recebe como argumentos apontadores para dois vértices, v1 e v2e determina se existe um arco ligando os dois vértices. Para tal, percorre a lista de arcos que sai de v1 tentando encontrar um arco que termine em v2. function adjacente(v1, v2: ap_vertice): booleano var ap: ap_arco ap  v1^.arcos

{ap começa no início da lista de arcos que sai de v1}

Enquanto (ap nil) E (ap^.destino v2) Fazer ap  ap^.prox_arco adjacente  ap nil

As restantes operações a implementar necessitam de uma função designada procura_vertice que vai percorrer a lista de vértices procurando a posição de um dado vértice, devolvendo como resultado um apontador para o vértice procurado. Caso o vértice procurado não exista, esta função cria um nodo na lista de vértices, com a informação do vértice procurado. Este novo nodo (com o novo vértice) é colocado no início da lista de vértices. Função procura_vertice(var grafo: ap_vertice; inf:dados): ap_vertice var ap: ap_vertice ap  grafo Enquanto (ap nil) and (ap^.inf_vertice inf) Fazer ap  ap^.prox_vertice; Se (ap = nil) Então

{não existia nenhum nó com conteúdo inf}

new(ap); ap^.inf_vertice  inf ap^.prox_vertice  grafo ap^.arcos  nil; grafo  ap procura_vertice  ap

---- 9 ----

O procedimento Juntar(grafo, v1, v2) cria no grafo um arco de v1 para v2. Tanto v1 como v2 podem ainda não existir, pelo que este procedimento deve criá-los quando assim acontecer, tal como contemplado na função procura_vertice descrita. v1 e v2 são os identificadores ou nomes dos vertices a juntar. Procedimento juntar(grafo: ap_vertice; v1, v2:dados) var

ap: ap_vertice ar: ap_arco

ap  procura_vertice(grafo, v1) ar  ap^.arcos {ar começa no início da lista de arcos que sai de ap}

Enquanto (ar nil) E (ar^.destino^.inf_vertice v2) Fazer {percorre a lista de arcos que sai de ap até...}

ar  ar^.prox_arco {...chegar ao fim ou encontrar um arco para v2}

Se (ar = nil) Então {chegou ao fim e não havia arco de v1 para v2, logo cria-o}

new(ar) ar^.destino  procura_vertice (grafo,v2) ar^.prox_arco  ap^.arcos ap^.arcos  ar {insere o arco no início da lista de arcos de ap, i.e., v1}

O procedimento Remover(grafo, ap_v1, ap_v2) remove, se existir, o arco que liga os vértices v1 a v2. na solução que vamos apresentar, ap_v1 e ap_v2 são apontadores, pelo que pretendemos remover o arco que vai do vértice apontado por v1 para o vértice apontado por v2. Procedimento remover(ap_v1, ap_v2: ap_vertice) var

ar1, ar2: ap_arco

ar1  ap_v1^.arcos Enquanto (ar1 nil) E (ar1^.destino ap_v2) Fazer ar2  ar1

{ar2 vai ser sempre o arco anterior a ar1}

ar1  ar1^.prox_arco Se ar1 nil Então

{existe arco de v1 para v2}

{verifica se o arco de v1 para v2 é o 1º da lista}

Se ar1 = ap_v1^.arcos Então ap_v1^.arcos  ar1^.prox_arco Senão

ar2^.prox_arco  ar1^.prox_arco

dispose(ar1)

---- 10 ----

Propomos que desenvolva o procedimento que receba v1 e v2 como campos do tipo dados, isto é, identificadores dos vértices (tal como na solução apresentada para o procedimento Juntar).

Caso pretenda aprofundar este tema, sugerimos que siga a lista de bibliografia recomendada no início do semestre.

---- 11 ----...