Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Matrizes de adjacência

A matriz de adjacência de um digrafo tem 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.

As matrizes de adjacência de grafos são simétricas:  adj[v][w] = adj[w][v]  para todo v e todo w.

(Esta página foi inspirada na seção 17.3 (Adjacency Matrix Representation), em particular nos programas 17.3, 17.4 e 17.5 (p.22-25), do livro de Sedgewick.)

Exemplo

Eis um digrafo e sua matriz de adjacência:

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

Eis um grafo (definido por seu conjunto de arestas) e sua matriz de adjacência:

0-1 0-5 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 1 0 1 2 0 0 0 0 1 0 3 0 1 0 0 0 1 4 0 0 1 0 0 0 5 1 1 0 1 0 0

Estruturas

Um digrafo será representado por uma struct digraph que contém o número de vértices, o número de arcos e a matriz de adjacência do digrafo.

/* A estrutura digraph representa um digrafo. O campo adj é um ponteiro para a matriz de adjacência do digrafo. O campo V contém o número de vértices e o campo A contém o número de arcos do digrafo. */

struct digraph {
   int V; 
   int A; 
   int **adj; 
};

/* Um objeto do tipo Digraph contém o endereço de um digraph. */

typedef struct digraph *Digraph;

[O livro de Sedgewick escreve "graph" no lugar do nosso "digraph". Também escreve "E" no lugar do nosso "A".]

Essa mesma estrutura será usada para representar grafos, mas nesse caso escreveremos "graph" e "Graph" no lugar de "digraph" e "Digraph":

#define graph digraph
#define Graph Digraph

É apropriado lembrar que, o número de arestas de um grafo é mais significativo que o seu número de arcos.  Se G é um Graph, o número de arestas de G é (G->A)/2.

Essas estruturas devem ser consideradas mais como modelos do que como algo definitivo. Elas poderão ser modificadas e adaptadas adiante, conforme as necessidades.

Algumas funções básicas

Eis algumas funções básicas de criação e manipulação de digrafos representados por matrizes de adjacência:

/* Esta função devolve (o endereço de) um novo digrafo com vértices 0,..,V-1 e nenhum arco. */

Digraph DIGRAPHinit (int V) { 
   Digraph G = malloc(sizeof *G);
   G->V = V; 
   G->A = 0;
   G->adj = MATRIXint(V, V, 0);
   return G;
}

/* A função abaixo aloca uma matriz com linhas 0..r-1 e colunas 0..c-1. Cada elemento da matriz recebe valor val. */

int **MATRIXint (int r, int c, int val) { 
   Vertex i, j;
   int **m = malloc(r * sizeof(int *));
   for (i = 0; i < r; i++)
      m[i] = malloc(c * sizeof(int));
   for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
         m[i][j] = val;
   return m;
}

/* Esta função insere um arco v-w no digrafo G. Se v == w ou o digrafo já tem arco v-w, a função não faz nada.  É claro que v e w não podem ser negativos e devem ser menores que G->V. */

void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w) { 
   if (v != w && G->adj[v][w] == 0) {
      G->adj[v][w] = 1; 
      G->A++;
   }
}

/* Esta função remove do digrafo G o arco que tem ponta inicial v e ponta final w.  Se não existe tal arco, a função nada faz. */

void DIGRAPHremoveA (Digraph G, Vertex v, Vertex w) { 
   if (G->adj[v][w] == 1) {
      G->A--;
      G->adj[v][w] = 0; 
   }
}

/* Para cada vértice v do digrafo G, esta função imprime, em uma linha, todos os vértices adjacentes a v. */

void DIGRAPHshow (Digraph G) { 
   Vertex v, w; 
   for (v = 0; v < G->V; v++) {
      printf("%2d:", v);
      for (w = 0; w < G->V; w++)
         if (G->adj[v][w] == 1) 
            printf(" %2d", w);
      printf("\n");
   }
}

É claro que essas mesmas funções podem ser usadas para construir grafos. Mas é conveniente adaptar os nomes das funções e escrever uma função específica para inserção de arestas:

#define GRAPHinit DIGRAPHinit
#define GRAPHshow DIGRAPHshow

/* Esta função insere uma aresta v-w no grafo G. */

void GRAPHinsertE (Graph G, Vertex v, Vertex w) { 
   DIGRAPHinsertA(G, v, w);
   DIGRAPHinsertA(G, w, v);
}

É um bom exercício escrever uma função GRAPHremoveE que remova uma aresta de um grafo.

Exercícios

A maior parte dos exercícios abaixo envolve grafos. Convido o leitor a refazer todos os exercícios depois de trocar "grafo" e "aresta" por "digrafo" e "arco" respectivamente.

1. Escreva uma função que verifique se um digrafo (dado por sua martriz de adjajcência) é simétrico
2. Escreva uma função que confira a consistência da representação de um grafo.  Ao receber um grafo G, a função deve devolver 1 se a matriz G->adj é simétrica e tem diagonal nula, e se valor de G->A é consistente com o conteúdo de G->adj.  Caso contrário, a função deve devolver 0.
3. Escreva uma função GRAPHdeg que devolva o grau de um vértice v num grafo G.
4. Escreva uma função DIGRAPHindeg que devolva o grau de entrada de um vértice v num digrafo G representado por sua matriz de adjacência.
5. Escreva uma função GRAPHremoveE que remova uma aresta v-w de um grafo G dado por sua matriz de adjacência. (Veja DIGRAPHremoveA.) Se v-w não for aresta, a função nada faz.
6. Escreva uma função de DIGRAPHcopy que receba um digrafo representado por sua matriz de adjacência, crie uma cópia do digrafo, e devolva (o endereço d)a cópia.
7. Escreva uma função de DIGRAPHdestoy que destrua um digrafo representado por sua matriz de adjacência (ou seja, libere o espaço que o digrafo ocupa na memória).
8. Escreva uma função que receba um vetor de arestas e devolva a representação por matriz de adjacência do grafo definido por essas arestas.
9. Escreva uma função DIGRAPHarcs que armazene os arcos de um digrafo num vetor fornecido pelo usuário.
10. Escreva uma função GRAPHedges que armazene as arestas de um grafo num vetor fornecido pelo usuário.

Mais exercícios

A maior parte dos exercícios abaixo envolve grafos. Convido o leitor a refazer todos os exercícios depois de trocar "grafo" e "aresta" por "digrafo" e "arco" respectivamente.

11. Digamos que um arquivo é gráfico se sua primeira linha contém um inteiro V e cada uma das demais linha contém dois inteiros pertencentes ao intervalo [0..V-1] separados por um caractere '-'.  Eis um exemplo:

           6
           0-1 
           0-5 
           1-0 
           1-5 
           2-4 
           3-1
    

    Se interpretarmos cada linha do arquivo como uma aresta, podemos dizer que o arquivo define um grafo com vértices 0..V-1.  Escreva uma função GRAPHconstruct que receba um arquivo gráfico e construa a matriz de adjacência do grafo. Use as funções GRAPHinit e GRAPHinsertE.

12. Considere o problema de decidir se dois vértices são adjacentes num grafo representado por sua matriz de adjacência. Quanto tempo consome a solução do problema? Dê sua resposta em função do número de vértices.
13. Considere o problema de decidir se um vértice é isolado num grafo representado por sua matriz de adjacência. Quanto tempo consome a solução do problema? Dê sua resposta em função do número de vértices.