CMP 4131Estrutura de Dados II

Capítulo 4 - Grafos e Algoritmos BásicosClarimar José Coelho - CMP/UCG(Última Modi�cação: Fevereiro 2006

Sumário

4 Grafos e Algoritmos 494.1 Origem da Teoria dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2 Evolução Teórica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.3 Grafos Direcionados ou Digrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.4 Terminologia 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.5 Caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.6 Mais Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.7 Grafos Acíclicos Direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.8 Grafos não Direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.9 Terminolgia 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.10 Grafos Valorados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.11 Representação de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.11.1 Matriz de Adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.11.2 Matriz Esparsa × Matriz Densa . . . . . . . . . . . . . . . . . . . . . . . 594.11.3 Lista de Adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.12 Implementando Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.13 Representação de Grafo - Comparações . . . . . . . . . . . . . . . . . . . . . . . 61

4.13.1 Camparação do Espaço . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.13.2 Comparação do Tempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.14 Busca em Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.14.1 Busca em Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.14.2 Busca em Largura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.14.3 Ordenação Topológica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.15 Primeira N2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

II

Lista de Figuras

4.1 Pontes sobre rio Pregel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2 Modelo matemático para o problema das pontes de Königsberg. . . . . . . . . . 504.3 Grafo G1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.4 Grafos direcionados acíclicos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.5 Grafo não direcionado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.6 Grafos valorados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.7 Lista de adjacência para o grafo G1 da Figura 4.3. . . . . . . . . . . . . . . . . . 594.8 Lista de adjacência para o grafo G4 da Figura 4.5. . . . . . . . . . . . . . . . . . 604.9 Grafo direcionado acíclico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.10 Grafo com distâncias entre cidades do estado de Goiás, Brasília e Minas Gerais. 65

III

Lista de Tabelas

4.1 Conjuntos de arestas de saída e incidentes para o grafo G1. . . . . . . . . . . . . 534.2 Comparação das representações de grafo. . . . . . . . . . . . . . . . . . . . . . . 63

IV

Capítulo 4

Grafos e Algoritmos

Grafos são modelos naturais usados para representar relacionamentos arbitrários entredados e objetos. Relacionamentos arbitrários entre dados e objetos aparecem com freqüênciaem ciência da computação, engenharia e muitas outras disciplinas. O estudo de grafos numadisciplina básica como estrutra de dados é importante.

4.1 Origem da Teoria dos Grafos

A teoria dos grafos surgiu de um problema algorítimico: o problema da ponte deKönigsberg, resolvido por Euler em 1736. Na cidade de Königsberg (hoje Kaliningrado) naRússia.

c C d g

A e

g b A f

D

Figura 4.1. Pontes sobre rio Pregel.

Existem duas ilhas sobre o rio Pregel com um total de 7 pontes interligando as regiões

49

50

(Figura 4.1). O problema consiste em partindo de uma dessas regiões, determinar um trajetopelas pontes segundo o qual se possa retornar à região de partida, após atravessar cada pontesomente uma vez.

Euler mostrou que não existe tal trajeto utilizando um modelo em grafos para umageneralização deste problema. Através do modelo mostrado na Figura 4.2, Euler provou queexiste o desejado trajeto quando e somente quando em cada região concorrer um número parde pontes.

Figura 4.2. Modelo matemático para o problema das pontes de Königsberg.

Esta solução é considerada o primeiro teorema em teoria dos grafos.

4.2 Evolução Teórica

Meados do século XIX, três desenvolvimentos isolados despertaram o interesse pelaárea.

1. Formulação do problema das 4 cores (De Morgan 1852)

Qual a quantidade mínima de cores para colorir um mapa de tal forma que países fron-teiriços possuam cores diferentes? Apresenta-se um exemplo em que 3 cores não sãosu�cientes. Uma prova de que 5 cores é su�ciente foi formulada. Conjecturou-se entãoque 4 cores seriam su�cientes. Esta questão �cou em aberto até 1976 quando Appel eHaken provaram para 4 cores. Curiosidade: Supõe-se que a autoria do problema seja deFrancis Guthrie. Este, em 1852, o teria proposto a seu irmão Frederick, então estudante,que por sua vez o comunicou a De Morgan.

2. Problema do ciclo Hamiltoniano (Hamilton 1859)

51

Existem n cidades. Cada par de cidades pode ser adjacente ou não arbitrariamente.Partindo de uma cidade qualquer, o problema consiste em determinar um trajeto quepasse exatamente uma vez em cada cidade e retorne ao ponto de partida.

3. Teoria das árvores, Kircho� (1847)

4. Problemas de circuitos elétricos, Cayley (1857), Química Orgânica.

Não existe uma maneira única de se representar (desenhar) um grafo. Um diagramameramente ressalta a relação de incidência entre vértices e arestas. As arestas podem interceptarem um ponto que não é vértice.

4.3 Grafos Direcionados ou Digrafos

De�nição 4.3.1 Grafo direcionado ou digrafo é o par ordenado G(V,E) com as seguintespropriedades:

1. O primeiro componente V , é um conjunto �nito, não vazio.

2. O segundo componente E, é um conjunto �nito de pares ordenados de vértices, E ⊆ V ×V .Os elementos de E são chamados de arestas de G.

Exemplo 4.3.1 Considere o grafo direcionado G1 = (V1, E1) com 4 os vértices e seis arestas

V1 = {a, b, c, d}

E1 = {(a, b), (a, c), (b, c), (c, a), (c, d), (d, d)}.

O grafo G1 pode ser representado gra�camente como mostra a Figrua 4.3. Os paresque representam uma aresta são ordenados, as arestas (a, c) e (c, a) são distintas. E1 é umconjunto matemático e não pode conter mais que uma instância de uma dada aresta. A aresta(d, d) conecta um nó a ele mesmo.

4.4 Terminologia 1

• Cada elemento de V é chamado vértice ou nó de G. Logo, V é o conjunto de vértices ounós de G.

52

a b

c d

Figura 4.3. Grafo G1.

• Uma aresta (v, w) ∈ E pode ser representada como v −→ w. A seta que sai de v para w

é conhecida como arco direcionado. O vértice w é chamado cabeça do arco porque ele seencontra na cabeça da seta. O vértice v é chamado cauda do arco. O vértice w é dito seradjacente ao vértice v.

• A aresta e = (v, w) sai do vértice v. A notação A(v) é usada para denotar o conjunto dearestas que saem do vértice v, isto é,

A(v) = {(v0, v1) ∈ E : v0 = v}.

• O grau de saída de um nó é o número de arestas que saem deste nó. Logo, o grau desaída de v é |A(v)|.

• O vértice e = (v, w) é dito ser incidente sobre o vértice w. A notação I(w) é usada paradenotar o conjunto de arestas incidentes sobre o vértice w, isto é,

I(w) = {(v0, v1) ∈ E : v1 = w}.

• O grau de entrada de um nó é o número de arestas incidentes no nó. Logo, o grau deentrada de w é |I(w)|. Por exemplo, a Tabela 4.2 mostra os conjuntos de saída e incidentesdos vértices e o grau de entrada e saída para cada vértice do grafo G1 mostrado na Figura4.3.

53

Tabela 4.1. Conjuntos de arestas de saída e incidentes para o grafo G1.

Vértice A(v) Grau de saída I(v) Grau de entradaa {(a, b), (a, c)} 2 {(a, c)} 1b {b, c)} 1 {(a, b)} 1c {(a, c), (c, d)} 2 {(a, c), (b, c)} 2d {(d, d)} 1 {(c, d), (d, d)} 2

4.5 Caminho

De�nição 4.5.1 Um caminho em um grafo direcionado G = (V,E) é uma seqüência não vaziade vértices:

P = {v1, v2, . . . , vk},

onde vi ∈ V para 1 ≤ i ≤ k, tal que (vi, vi+1) ∈ E para 1 ≤ i ≤ k.O comprimento do caminho P é k−1. Entre os caminhos do grafo G1 existe o caminho

de comprimento zero {a}, o caminho de comprimento um, {b, c}, o caminho de comprimentodois, {a, b, c}, e assim por diante.

O grafo G1 gera um número in�nito de caminhos. Considere que{a, c, a, c, a, c, a, c, a, c, a, c, a} é um caminho de G1. Observe também o distinção entre ocaminho zero, {d} e o caminho de comprimento um, {d, d}.

4.6 Mais Terminologia

Considere o caminho P = {v1, v2, . . . , vk} em um grafo direcionado G = (V,E).

• O vértice vi+1 é o sucessor do vértice vi para 1 ≤ i < k. Cada elemento vi para o caminhoP (exceto o o último) tem um sucessor;

• O vértice vi−1 é o predecessor de vi para 1 < i ≤ k. Cada elemento vi do caminho P

(exceto o primeiro) tem um predecessor.

• Um caminho P é chamado de caminho simples se e somente se vi 6= vj para todo i e j talquue 1 ≤ i < j < k. Todovia, é permitido que v1 seja o mesmo que vk em um caminhosimples.

54

• Um ciclo é um caminho P de comprimento diferente de zero em que v1 = vk. O compri-mento de um ciclo é exatamento o comprimento do caminho P .

• Um loop é um ciclo de comprimento um. Isto é, ele é um caminho da forma {v, v}.

• Um ciclo simples é um caminho que é ambos um ciclo e um caminho simples.

Referindo novamente ao grafo G1 da Figura 4.3, o caminho {a, b, c, d} é um caminho simplesde comprimento três. O caminho {c, a, c, d} também tem comprimento três mais não é simplesporque o vértice c ocorre duas vezes na seqüência, não no �m. O grafo contém o caminho{a, b, c, a} que é um ciclo de comprimento três. O caminho {a, c, a, c, a} é um ciclo de compri-mento quatro.

4.7 Grafos Acíclicos Direcionados

Para certas aplicações é conveniente lidar com grafos que não contém ciclos. Porexemplo, a árvore é um tipo especial de grafo que não comtém ciclos.

De�nição 4.7.1 Grafo direicionado que não contém ciclos.

Todas as árvores são grafos acíclicos direcionados. Todavia, nem todo grafo acíclicodirecionado são árvores. Por exemplo, considere os grafos direcionados, G2 e G3, acíclicosmostrados na Figura 4.4. G2 é uma árvore mas G3 não é.

a

b

d

c

e f g

2 G h

i j

k

3 G

Figura 4.4. Grafos direcionados acíclicos.

55

4.8 Grafos não Direcionados

Em um grafo não direcionado os vértices são conectados por arcos não direcionados.Arcos não direcionados é uma aresta que não tem seta. Ambas as extremidades de um arconão direcionado são equivalentes, não existe cabeça ou cauda. Logo, a aresta de um grafo nãodirecionado é representada como um conjunto envés de pares ordenados.

De�nição 4.8.1 Grafo não direcionado é um par ordenado G = (V, E) com as seguintespropriedades:

1. O primeiro componente, V , é um conjunto �nito não vazio. Os elementos de V sãochamados de vértices de G;

2. O segundo componente, E, é um conjunto de conjuntos. Cada elemento de E é umconjunto compreendido de exatamente dois (distintos) vértices. Os elementos de E sãochamados de arestas de G.

Exemplo 4.8.1 Considere o grafo não direcionado G4 = (V4, E4) com quatro vértices e quatroarestas:

V4 = {a, b, c, d}

E4 = {{a, b}, {a, c}, {b, c}, {c, d}}

O grafo G4 pode ser representado gra�camente como mostra a Figura 4.5.

a

c

b

d

Figura 4.5. Grafo não direcionado.

Observe que, devido as arestas em um grafo não direcionado ser um conjunto, {a, b} ≡{b, a}, e E4 é também um conjunto, ele não pode conter mais que uma instância de uma dada

56

aresta. Outra conseqüência da de�nição é que um vértice não pode ter uma aresta para elemesmo em um grafo não direcionado porque as arestas é um conjunto de tamanho dois e umconjunto não pode conter duplicatas.

4.9 Terminolgia 2

Considere o grafo não direcionado G = (V, E) dado pela De�nição 4.

• Uma aresta {v, w} ∈ E sai e incide sobre os vértices v e w;

• O conjunto de arestas que saem do vértice v é o conjunto A(v) = {(v0, v1) ∈ E : v0 =

v ∪ v1 = v}. O conjunto de arestas incidentes sobre o vértice w é I(w) ≡ A(w).

4.10 Grafos Valorados

Aplicação prática requer anotação adicional em grafos. Tal informação pode ser colo-cada nas arestas ou vértices. Um grafo com informação adicional é chamado de grafo valoradoou rotulado. A Figura 4.6 mostra dois exemplos de grafos valorados.

a

c

b

d 88

83 31

9

a

c

b

d 26

31

41

Gráfo direcionado com vértices valorados Grafo não direcionado com arestas valoradas

5 G 6 G

59

Figura 4.6. Grafos valorados.

Por exemplo, o grafo direcionado com vértices rotulados/valorados tal como o grafoG5 da Figura 4.6 pode ser usado para representar uma máquina de estado �nito. Cada vérticecorresponde a um estado da máquina e cada aresta corresponde a um estado de transiçãopermitido.

O grafo não direcionado com arestas valoradas tal como G6 na Figura 4.6 pode serusado para representar informação geográ�ca. Os vértices do grafo representa localizações e as

57

arestas representam possíveis rotas entre as localizações. Nesse grafo o rótulo é usado sobrecada aresta para representar a distância entre dois pontos.

4.11 Representação de Grafos

Considere o grafo direcionado G = (V,E). Com E ⊆ V × V , o grafo G contém maisde |V |2 arestas. Existem 2|V |

2 conjuntos possíveis de arestas para um dado conjunto de vérticesV . Logo, a principal preocupação quando projetar a representação de um grafo é encontraruma maneira apropriada de representar o conjunto de arestas.

4.11.1 Matriz de Adjacência

Considere o grafo direcionado G = (V, E) com n vértices, v = {v1, v2, . . . , vn}. Oesquema de representação usa uma matriz A n× n de zeros e uns dado por

Ai,j =

1 (vi, vj) ∈ E;

0 caso contrário.

isto é, o (i, j)−ésimo elemento da matriz, será um se vi → vj for uma aresta em G. A matrizA é chamada matriz de adjacência. Por exemplo, a matriz de adjacência par o grafo G1 daFigura 4.3 é

A1 =

0 1 1 0

0 0 1 0

1 0 0 1

0 0 0 1

O número de uns na matriz de adjacência é igual ao número de arestas no grafo. Avantagem de usar uma matriz de adjacência é que é fácil determinar o conjunto de arestas quesaem e incidem em um vértice. Considere o vértice vi. Cada um na i−ésima linha correspondea uma aresta que sai do vértice vi. Cada um na i−ésima coluna corresponde a uma arestaincidente no vértice vi.

Nesse caso, existem duas vezes mais uns na matriz de adjacência do que arestas nografo não direcionado.

Matriz de adjacência pode ser usada também para representar grafos não direcionados.Um grafo G = (V, E) não direcionado é representado com com n vértices, usando uma matriz

58

A n× n de zeros e uns dada por

Ai,j =

1 {vi, vj} ∈ E;

0 caso contrário.

Os dois conjuntos {vi, vj} e {vj, vi} são equivalentes, a matriz A é simétrica em relaçãoa diagonal. Isto é, Ai,j = Aj,i. Logo, todos as entradas na diagonal são zeros: Ai,i = 0 para1 ≤ i ≤ n. Por exemplo, a matriz de adjacência para o grafo G4 da Figura 4.5 é

A4 =

0 1 1 0

1 0 1 0

1 1 0 1

0 0 1 0

Nesse caso, existem duas vezes mais uns na matriz de adjacência que arestas no grafonão direcionado.

Uma simples variação permite usar a matriz de adjacência para representar um grafovalorado. Por exemplo, dado um rótulo numérico, pode-se representar um grafo (direcionadoou não direcionado) usando uma matriz A n × n onde o rótulo numérico associado a aresta(vi, vj), no caso do grafo direcionado, e a aresta {vi, vj}, no caso de um grafo não direcionado.Por exemplo, a matriz de adjacência para o grafo G6 da Figura 4.6 é

A6 =

∞ 31 41 ∞31 ∞ 59 ∞41 59 ∞ 26

∞ ∞ 26 ∞

Nesse caso, as entradas correspondentes a arestas não existentes são representadaspor ∞. Aqui ∞ serve como um tipo de sentinela. O valor usado como sentinela depende daaplicação. Por exemplo, se a aresta representa rotas entre localizações geográ�cas, então ocomprimento ∞ representa um valor maior que todos que existem.

A matriz de adjacência tem |V |2 entradas, a quantidade de espaços necessários pararepresentar as arestas de um grafo é O(|V |2), independente do número atual de arestas nografo. Seo grafo contém relativmamente poucas arestas, isto é, se |E| ≪ |V 2|, então a maioriados elementos da matriz de adjacência deverá ser zero (ou ∞). A matriz que a maioria doselementos são zero (ou ∞) é uma matriz esparsa.

59

4.11.2 Matriz Esparsa × Matriz Densa

Informalmente, um grafo com poucas arestas é esparso e um grafo com muitas arestasé denso.

De�nição 4.11.2.1 Grafo esparso é um grafo G = (V, E) onde |E| = Θ(|V |).

Exemplo 4.11.2.1 Considere o grafo G = (V, E) com n nós. Suponha que o grau de saída decada vértice em G seja a constante �xa k. O grafo G é um grafo esparso porque |E| = k|V | =O(|V |). Um grafo que não é esparso é dito denso.

De�nição 4.11.2.2 Um grafo denso é um grafo G = (V, E) onde |E| = Θ(|V |2).

Exemplo 4.11.2.2 Considere o grafo G = (V,E) com n vértices. Suponha que o grau de saídado vértice em G seja uma função f de n, 0 < f ≤ 1. Se n = 16 e f = 0.25, o grau de saída decada nó é 4. O grafo G é um grafo denso porque |E| = f |V |2 = Θ(|V |2).

4.11.3 Lista de Adjacência

Técnica freqüentemente usada para representar grafo esparso, G = (V, E). Usa-se |V |listas ligadas, uma para cada vértice. A lista ligada para o vértice vi ∈ V contém os elementosde {w : (vi, w) ∈ A(vi)}, o conjunto de nós adjacentes a vi. Como resultado, as listas sãochamadas de listas de adjacência.

A Figura 4.7 mostra a lista de adjacência para o grafo direcionado da Figura 4.3.

a b c

b c

c a

d d

1 G

d

Figura 4.7. Lista de adjacência para o grafo G1 da Figura 4.3.

60

A Figura 4.8 mostra a lista de adjacência para o grafo não direcionado da Figura 4.5.

a b c

b a

c a b

d c

4 G

c

d

Figura 4.8. Lista de adjacência para o grafo G4 da Figura 4.5.

Por de�nição, um grafo esparso tem |E| = O(|V |). Conseqüentemente o espaço reque-rido para representar um grafo esparso usando lista de adjacência é O(|V |). Isto é assintotica-mente melhor que usar matriz de adjacência que requer espaço de O(|V |2).

4.12 Implementando Grafos

Formalmente, o grafo G = (V, E) é um par ordenado com dois conjuntos: um conjuntode vértices e um conjunto de arestas. Informalmente, o grafo pode ser visto como uma estruturasde que contém vértices e arestas.

#define N 10

#define T ipo_Dado int

#define Grafo(X) Tipo_Dado X[N ][N ]

#define MV alor 99

Principais Operações em Grafo

void Inicializa(Grafo (G));

void Conecta(Grafo (G), int i, int j, T ipo_Dado V );

61

void Desconecta(Grafo(G), int i, int j);

Tipo_Dado Adjacente(Grafo(G), int i, intj);

void Imprime(Grafo(G));

void Menores_Custos(Grafo(G), Grafo(C));

void Gera_Caminhos(Grafo(G), Grafo(P ));

void Exibe_Caminho(Grafo(P ), int i, int j, int f);

void Menor_Caminho(Grafo(G), int i, int j);

void Gera_Conectividade(Grafo(G), Grafo(Cd));

Tipo_Dado Centro(Grafo(G));

4.13 Representação de Grafo - Comparações

Para selecionar o esquema apropriado à representação de grafos é necessário entendera relação tempo e espaço utilizados. Embora os detalhes de implementação sejam omitidos,pode-se tirar conclusões sobre a performance esperada das implementações.

4.13.1 Camparação do Espaço

Considere a representação de um grafo direcionado G = (V,E). Além do espaçonecessário para armazenar os vértices |V | e arestas |E| é necessário espaço para armazenar amatriz de adjacência. Nesse caso, a matriz é |V |× |V |. Logo, a quantidade de espaço requeridapela implementação em matriz de adjacência é

|V | × tamanho(Vértice) + |E| × tamanho(Aresta) + |V |2 × tamanho(Aresta) + O(1)

Por outro lado, considere a quantidade de espaço requerido quando o mesmo grafo érepresentado em lista de adjacência. Além dos vértices e arestas, existem |V | listas ligadas.Cada lista tem tem um ponteiro para a cabeça e cauda. Existem |E| elementos ligados, cadaum com um ponteiro para o próximo elemento da lista e um ponteiro para a aresta. Logo, oespaço requirido é

|V | × tamanho(Vértice) + |E| × tamanho(Aresta) + |V | × tamanho(elemento)+|E| × (tamanho(elemento) + tamanho(Aresta)) + O(1)

62

Assumindo que todos os ponteiros requerem o mesmo espaço, pode-se calculuir que alista de adjacência usa menos espaço que a matriz de adjacência quando

|E| < |V |2 − |V |2

Por exemplo, dado um grafo com 10 nós, a versão com lista de adjacência usa menosespaço quando existe menos que 45 arestas. Pode-se dizer que a lista de adjacência usa menosespaço quando a o grau médio de um nó, d̄ = |E|/|V |, satisfaz d̄ w |V |/2.

4.13.2 Comparação do Tempo

As seguintes operações são muito usadas na implementação de diferentes algoritmosde grafos:

• Busca aresta (v, w)

Dado os vértices v e w, localiza a instância da aresta correspondente. Quando usandomatriz de adjacência, a aresta pode ser encontrada em tempo constante;

Quando a lista de adjacência é usada, o pior caso roda no tempo é O(|A(v)|), desde queA(v)| é o comprimento da lista de adjacência associada com o vértice v;

• Enumera todos as arestas

A localização de todas as arestas no caso de matriz de adjacência, é necessário examinartodos as entradas |V |2 da matriz. Logo, o pior caso é o tempo necessário para enumerartodas as arestas é O(|V |2);

A enumeração de todas as arestas no caso de lista de adjacência requer o caminhamentoem |V | listas. Em cada lista existem |E| arestas. O pior caso é dado por O(|V |+ |E|).

• Enumera arestas saindo de v

Para enumerar todos os vértices que saem do vértice v requer a busca completa da v−ésimalinha da matriz de adjacência. O pior caso é dado por O(|V |);

A enumeração de todas as arestas que saem do vértice v é uma operação trivial no casode lista de adjacência. A v−ésima lista é percorrida. Isso leva tempo O(|A|(v)|) no piorcaso.

63

• Enumera arestas incidentes sobre w

A enumeração de todas as arestas incidentes sobre o vértice w requer o caminhamentocompleto da w−ésima coluna da matriz de adjacência. O pior caso é dado por O(|V |);

Os vértices incidentes no vértice w usando lista de adjacência é uma operação não trivial.É necessário encontrar cada lista de adjacência com o objetivo de encontrar todas asarestas incidentes sobre o vértice dado. O pior caso é dado por O(|V |+ |E|).

A Tabela 4.2 mostra um resumo com o tempo de execução para cada operação asso-ciada a cada esquema de representação de grafos.

Tabela 4.2. Comparação das representações de grafo.Operção Matriz de adjacência Lista de adjacência

Busca aresta (v, w) O(1) O(|A(v)|)Enumera todas as arestas O(|V |2) O(|V |+ |E|)

Enumera todas as arestas saindo de v O(|V |) O(|A(v)|)Enumera as arestas incidentes sobre w O(|V |) O(|V |+ |E|)

4.14 Busca em Grafo

Algoritmos para grafos tem em comum a característica que eles sistemamtimante vis-tam todos os vértices do grafo. Isto é, o algoritmo caminha através da estrutura de dados dografo e executa alguma operação em cada vértice do grafo. Esse processo de caminha atravésdo grafo e chamado busca em grafo (graph transversal).

4.14.1 Busca em Profundidade

4.14.2 Busca em Largura

4.14.3 Ordenação Topológica

Ordenação topológica é a ordenação dos vértices de um grafo direcionado dado pelaseguinte de�nição:

De�nição 4.14.3.1 Considere um grafo direcionado acíclico G = (V,E). A ordenação topoló-gica dos vértices de G é uma seqüência S = {v1, v2, . . . , v|v|} onde cada elemento de V aparece

64

exatamente uma vez. Para cada par de distintos vértices vi e vj na seqüência S, se vi → vj éuma aresta em G, isto é, (vi, vj) ∈ E, então i < j (se existe um caminho do vértice vi para ovértice vj, então vi aparece antes de vj na ordenação).

a

d

b

c

f

c

g

i

h

0

3

1

3

1

1

1

2

2

7 G

Figura 4.9. Grafo direcionado acíclico.

Informalmente, a ordenação topológica é uma lista de vértices de um grafo diercionadoacíclico onde todos os sucessores de qualquer vértice dado aparecem na sucessão depois dovértice dado. Considere o grá�co derecionado acíclico mostrado na Figura 4.9. A seqüênciaS = {a, b, c, d, e, f, g, h, i} é uma ordenação topológica dos vértices de G7.

Para verifcar, considere o conjunto de vértices:

E = {(a, b), (a, c), (a, e), (b, d), (b, e), (c, f), (c, h), (d, g), (e, g), (e, h), (e, i), (f, h), (g, i), (h, i)}

Os vértices em cada aresta estão em ordem alfabética, e assim deve ser a seqüência S.Deve ser evidente também, a partir da Figura 4.9, que a ordenação topológica não é única. Porexemplo, as seqüências seguintes são ordenação topólogicas válidas para o grafo G7:

S ′ = {a, c, b, f, e, d, h, g, i}

S ′′ = {a, b, d, e, g, c, f, h, i}

S ′′′ = {a, c, f, h, b, e, d, g, i}...

65

4.15 Primeira N2

Elaboração de um programa para solução de problema relacionado a busca em grafoe algoritmos de menores caminhos.

1 2

3

4

50

35

12

6075

5200

170150

190

6

7

300

160

60

250

8

60

90170

10

9

400

450

180120

70

29

250

14

160

Figura 4.10. Grafo com distâncias entre cidades do estado de Goiás, Brasília e Minas Gerais.

Na Figura 4.10, os vértices representam as seguintes cidades: 1 - Ipameri, 2 - Catalão,3 - Urutaí, 4 - Pires do Rio, 5 - Goiânia, 6 - Anápolis, 7 - Brasília, 8 - Caldas Novas, 9 - Araguarie 10 - Uberlândia.

A formulação geral para a solução do problema se refere ao grafo valorado da Figura4.10. Escreva um programa em linguagem C para implemetar as seguintes operações em grafo:

1. Criar grafo valorado a partir da Figura 4.10 usando a representação de matriz ou lista deadjacência através do uso repetido da função conecta;

2. Ordenar topológicamente os vértices do grafo;

3. Calcular do centro do grafo;

4. Calcular a matriz/lista de custo do grafo;

5. Criar a matriz/lista de caminhos para o grafo;

6. Listar os menores caminhos entre vértices do grafo;

66

7. Liberar memória no caso de implementação com lista de adjacência.

a) Pela elaboração do programa, deve ser entendido que o programa deve ser elaboradona linguagem C e a nota atribuída considerará a correção, e�ciência, paragrafação (in-dentação), uso adequado de comentários e legibilidade do programa. Além disso, seráconsiderado o uso de todos os conceitos (estruturas de controle, estruturas de dados,sub-algoritmos) na correção do programa;

b) O programa deve de�nir uma estrutura de dados para armazenar o grafo: matriz ou listade adjacência.

c) Data de entrega: ver calendário.

d) O trabalho completo e correto vale 6.0 (seis) pontos para a representação do grafo commatriz de adjacência. O algoritmo de Floyd-Warshall deve ser usado obrigatoriamentepara o cálculo da matriz de custo e matriz de menores caminhos. Detalhes do algoritmode Floyd-Warshall deve ser incluso na revisão bibliográ�ca do texto.

e) A solução usando a represetação com lista de adjacência vale 10.0 (dez) pontos. O al-goritmo de Dijkstra deve ser usado obrigatoriamente para a criação da lista de custo elista de menores caminhos. Detalhes do algoritmo de Dijkstra deve ser incluso na revisãobibliográ�ca do texto.