A Estrutura de Dados

Estruturas de dados para grafos

Como representar um grafo de modo que ele possa ser processado eficientemente num computador?  Como fazer isso em linguagem C?

Introdução

Os vértices de nossos grafos serão representados por números inteiros.  O conjunto de vértices será  0 1 2 3 ... V-1 .  Poderíamos usar o tipo-de-dados int para representar vértices, mas é melhor ter um nome específico para esse tipo:

/* Vértices de grafos são representados por objetos do tipo vertex. */

#define vertex int

O conjunto de arcos de um grafo pode ser representado de várias maneiras. Discutimos abaixo duas representações clássicas:

• matriz de adjacências e
• listas de adjacência.

Cada uma das representações tem suas vantagens e suas desvantagens.  As descrições a seguir devem ser entendidas apenas como modelos e não como algo definitivo. As estruturas de dados serão modificadas e adaptadas mais adiante, conforme as necessidades.

Matriz de adjacências

A matriz de adjacências de um grafo é uma matriz de 0's e 1's com colunas e linhas indexadas pelos vértices.  Se  adj[][]  é uma tal matriz então, para cada vértice v e cada vértice w,

• adj[v][w] = 1   se v-w é um arco  e
• adj[v][w] = 0   em caso contrário.

Assim, a linha v da matriz adj[][] representa o leque de saída do vértice v e a coluna w da matriz representa o leque de entrada do vértice w.  Por exemplo, veja a matriz de adjacências do grafo cujos arcos são  0-1 0-5 1-0 1-5 2-4 3-1 5-3 :

  0 1 2 3 4 5   

0 0 1 0 0 0 1

1 1 0 0 0 0 1

2 0 0 0 0 1 0

3 0 1 0 0 0 0

4 0 0 0 0 0 0

5 0 0 0 1 0 0

Como nossos grafos não têm laços, os elementos da diagonal da matriz de adjacências são iguais a 0.  Se o grafo for não-dirigido, a matriz é simétrica: adj[v][w] ≡ adj[w][v].

Um grafo é representado por uma struct graph que contém a matriz de adjacências, o número de vértices, e o número de arcos do grafo:

/* REPRESENTAÇÃO POR MATRIZ DE ADJACÊNCIAS: A estrutura graph representa um grafo. O campo adj é um ponteiro para a matriz de adjacências do grafo. O campo V contém o número de vértices e o campo A contém o número de arcos do grafo. */

struct graph {

   int V;

   int A;

   int **adj;

};

/* Um Graph é um ponteiro para um graph, ou seja, um Graph contém o endereço de um graph. */

typedef struct graph *Graph;

Seguem algumas ferramentas básicas para a construção e manipulação de grafos:

/* REPRESENTAÇÃO POR MATRIZ DE ADJACÊNCIAS: A função GRAPHinit() constrói um grafo com vértices 0 1 .. V-1 e nenhum arco. */

Graph GRAPHinit( int V) {

   Graph G = malloc( sizeof *G);

   G->V = V;

   G->A = 0;

   G->adj = MATRIXint( V, V, 0);

   return G;

}

/* REPRESENTAÇÃO POR MATRIZ DE ADJACÊNCIAS: A função MATRIXint() aloca uma matriz com linhas 0..r-1 e colunas 0..c-1. Cada elemento da matriz recebe valor val. */

static int **MATRIXint( int r, int c, int val) {

   int **m = malloc( r * sizeof (int *));

   for (vertex i = 0; i < r; ++i)

      m[i] = malloc( c * sizeof (int));

   for (vertex i = 0; i < r; ++i)

      for (vertex j = 0; j < c; ++j)

         m[i][j] = val;

   return m;

}

/* REPRESENTAÇÃO POR MATRIZ DE ADJACÊNCIAS: A função GRAPHinsertArc() insere um arco v-w no grafo G. A função supõe que v e wsão distintos, positivos e menores que G->V. Se o grafo já tem um arco v-w, a função não faz nada. */

void GRAPHinsertArc( Graph G, vertex v, vertex w) {