Gráficos e suas aplicações

Grafos e suas Aplicações

Neste capítulo, examinaremos uma nova estrutura de dados: o grafo. Definiremos

alguns dos termos associados aos grafos e mostraremos como implementá-

los em C. Apresentaremos também algumas aplicações de grafos.

8.1. GRAFOS

Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de

arcos (ou arestas). Cada arco num grafo é especificado por um par de nós.

A Figura 8.1.1a ilustra um grafo. A seqüência de nós é {A,B,C,D,E,F,G,H},

e o conjunto de arcos é {(A,B), (A,D), (A,C), (C,D), (C,F), (E,G), (A,A)}. Se os

pares de nós que formam os arcos forem pares ordenados, diz-se que o grafo

é um grafo orientado (ou dígrafo). As Figuras 8.1.1b, c e d ilustram três

digrafos. As setas entre os nós representam arcos. A ponta de cada seta

representa o segundo nó no par ordenado de nós que forma um arco, e o final

de cada seta representa o primeiro nó no par. O conjunto de arcos do grafo

da Figura 8.1.1b é {<A,B>, <A,C>, <A,D>, <C,D>, <F,C>, <E,G>, <A,A>}.

Usamos parênteses para indicar um par não-desordenado e chaves angulares

para indicar um par ordenado. Nas três primeiras seções deste capítulo,

concentraremos nossa atenção nos digrafos. Examinaremos os grafos nãoorientados

novamente na Seção 8.4.

664

MAKRON

Books

Cap. 8 Grafos e suas aplicações 665

Observe que um grafo não precisa ser uma árvore (Figuras 8.1.1a,

b e d), mas uma árvore tem de ser um grafo (Figura 8.1.1c). Observe também

que um nó não precisa ter arcos associados a ele (nó H nas Figuras 8.1.1a e b).

Um nó n incide em um arco x se n for um de seus dois nós no par

ordenado de nós que constituem x. (Dizemos também que x incide em n.) O

grau de um nó é o número de arcos incidentes nesse nó. O grau de entrada

de um nó n é o número de arcos que têm n como cabeça, e o grau de saída

de n é o número de arcos que têm n como terminação da seta. Por exemplo,

o nó A na Figura 8.1.1d tem grau de entrada 1, grau de saída 2 e grau 3.

Um nó n será adjacente a um nó m se existir um arco de m até n. Se n for

adjacente a m, n será chamado sucessor de m e m será um predecessor

de n.

Uma relação R num conjunto A é uma seqüência de pares ordenados

de elementos de A. Por exemplo, se A - {3,5,6,8,10,17}, o conjunto R =

{<3,10>,<5,6>,<5,8>,<6,17>,<8,17>,<10,17>} será uma relação. Se <x,y> for

um membro de uma relação R, diz-se que x está relacionado a y em R. A

relação R anterior pode ser descrita dizendo-se que x está relacionado com

y se x for menor que y eo resto obtido a partir da divisão de y por x for ímpar.

<8,17> é um membro dessa relação porque 8 é menor que 17 e o resto da

divisão de 17 por 8 é 1, um número ímpar.

Uma relação pode ser representada por um grafo no qual os nós

representam o conjunto básico e os arcos representam os pares ordenados

da relação. A Figura 8.1.2a ilustra o grafo que representa a relação anterior.

Um número pode ser associado a cada arco de um grafo, como na Figura

8.1.2b. Nesta figura, o número associado a cada arco é o resto obtido da

divisão do inteiro posicionado na cabeça do arco pelo inteiro posicionado em

sua terminação. Um grafo desse tipo, no qual existe um número associado a

cada arco, é chamado grafo ponderado ou rede. O número associado a um

arco é chamado peso.

Identificaremos várias operações primitivas que serão úteis ao lidar

com grafos. A operação join(a,b) introduz um arco do nó a até o nó b se ainda

não existir um; joinwt(a,b,x) insere um arco de a até 6 com peso x num grafo

ponderado; remv(a,b) e remvwt(a,b,x) eliminam um arco de a até 6, caso

exista (remuwt define também x com seu peso). Embora possamos também

acrescentar ou eliminar nós de um grafo, discutiremos essas possibilidades

em seção mais adiante. A função adjacent(a,b) retorna true se b for adjacente

a a, e false, caso contrário.

666 Estruturas de Dados Usando C Cap. 8

Figura 8.1.1 Exemplos de grafos.

(b)

(c) (d)

(a)

Cap. 8 Grafos e suas aplicações 667

Figura 8.1.2 Relações e grafos.

(b)

(a)

668 Estruturas de Dados Usando C Cap. 8

Um caminho de comprimento k do nó a ao nó b é definido como uma

seqüência de k + 1 nós n1, n2,..., nk + 1, tal que n1 = a,