Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Vetor de listas de adjacência

O vetor de listas de adjacência de um digrafo tem uma lista encadeada (= linked list) para cada vértice do digrafo.  A lista do vértice v contém todos os vértices vizinhos de v.

(Esta página foi inspirada na seção 17.4 (Adjacency-Lists Representation), em particular no programa 17.6 (p.28), do livro de Sedgewick.)

Exemplo

Eis um digrafo e seu vetor de listas de adjacência:

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

0: 5 1 1: 5 0 2: 4 3: 1 4: 5: 3

Eis o conjunto de arestas de um grafo e o vetor de listas de adjacência do grafo:

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

0: 5 1 1: 3 5 0 2: 4 3: 5 1 4: 2 5: 3 1 0

Estruturas

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

/* A estrutura digraph representa um digrafo. O campo adj é um ponteiro para o vetor de listas 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; 
   link *adj; 
};

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

typedef struct digraph *Digraph;

/* A lista de adjacência de um vértice v é composta por nós do tipo node. Um link é um ponteiro para um node. Cada nó da lista contém um vizinho w de v e o endereço do nó seguinte da lista. */

typedef struct node *link;
struct node { 
   Vertex w; 
   link next; 
};

/* A função NEW recebe um vértice w e o endereço next de um nó e devolve um novo nó x com x.w = w e x.next = next. */

link NEW (Vertex w, link next) { 
   link x = malloc(sizeof *x);
   x->w = w; 
   x->next = next;     
   return x;                         
}

[No livro de Sedgewick, o nome do primeiro campo de um node é  v  e não w.  Por vezes, isso torna o código um pouco confuso. Além disso, Sedgewick escreve "E" no lugar do meu "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.  O número de arestas de um grafo G é (G->A)/2.

Essas estruturas não devem ser consideradas definitivas. Elas poderão ser modificadas e adaptadas adiante, conforme as necessidades.

Algumas funções básicas

Eis algumas funções básicas de construção e manipulação de digrafos representados por listas 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 = malloc(V * sizeof(link));
   for (v = 0; v < V; v++) 
      G->adj[v] = NULL;
   return G;
}

/* A função abaixo 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. */

void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w) { 
   link p;
   if (v == w) return;
   for (p = G->adj[v]; p != NULL; p = p->next) 
      if (p->w == w) return;
   G->adj[v] = NEW(w, G->adj[v]);
   G->A++;
}

A execução da função DIGRAPHinsertA consome muito tempo, pois percorre toda a lista de vizinhos de v.  Talvez seja melhor substituir o código pelo que está abaixo e transferir a responsabilidade de evitar laços e arcos paralelos ao cliente/usuário, que provavelmente tem condições de fazer isso de maneira eficiente.

   void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w) { 
      if (v == w) return;
      G->adj[v] = NEW(w, G->adj[v]);
      G->A++;
   }

Para tratar de grafos, é conveniente adaptar os nomes das funções. Também é conveniente escrever uma função específica para inserção de arestas:

#define GRAPHinit DIGRAPHinit

/* A função abaixo insere uma aresta v-w no grafo G. Se v == w ou o grafo já tem aresta v-w, a função não faz nada. */

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

Exercícios

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

1. [Importante]  Considere o grafo definido pelas arestas abaixo.  Faça uma figura do vetor de listas de adjacência do grafo quando as arestas acima são inseridas por GRAPHinsertE, na ordem dada acima, em um grafo inicialmente vazio.

   3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4

2. Escreva uma versão da função DIGRAPHshow apropriada para listas de adjacência. (Veja a função que escrevemos para matriz de adjacência.)
3. Escreva uma função que confira a consistência da representação de um grafo por listas de adjacência.  Ao receber um grafo G, a função deve devolver 1 se o grafo é simétrico, as listas de adjacência não contêm laços nem arestas paralelas, e o valor de G->A é consistente com o vetor G->adj.  Caso contrário, a função deve devolver 0.
4. Escreva uma função GRAPHdeg que receba um grafo representado por listas de adjacência e um vértice v e devolva o grau de v.
5. Escreva uma função DIGRAPHindeg que devolva o grau de entrada de um vértice v num digrafo representado por listas de adjacência.
6. Escreva uma função GRAPHremoveE que remova uma aresta v-w de um grafo G dado por suas listas de adjacência. (Veja DIGRAPHremoveA.) Se v-w não for aresta de G, a função não deve fazer nada.
7. Escreva uma função DIGRAPHcopy que receba um digrafo G, crie uma cópia de G, e devolva (o endereço d)a cópia. Suponha que G representado por um vetor de listas de adjacência.
8. Escreva uma função de DIGRAPHdestoy que destrua um digrafo representado por suas listas de adjacência (ou seja, libere o espaço que o digrafo ocupa na memória).
9. Dê um exemplo simples de um vetor de listas de adjacência de um grafo que não pode ser gerado, a partir do grafo vazio, pelo uso repetido da função GRAPHinsertE.  
10. A figura abaixo sugere o vetor de listas de adjacência de um grafo.  De quantas maneiras diferentes essas listas poderiam ser reescritas sem deixar de representar o mesmo grafo?

          0: 6 5 1 2
          1: 0
          2: 0
          3: 5 4
          4: 6 5 3
          5: 3 0 4
          6: 0 4
          7: 8
          8: 7
          9: 12 11 10
         10: 9
         11: 12 9
         12: 9 11
    

11. Escreva uma função que receba um vetor de arestas e devolva a representação por listas de adjacência do grafo definido por essas arestas.
12. Escreva uma função DIGRAPHarcs que armazene os arcos de um digrafo num vetor fornecido pelo usuário.
13. Escreva uma função GRAPHedges que armazene as arestas de um grafo num vetor fornecido pelo usuário.
14. [Bom!]  Escreva uma função que receba um grafo representado por suas listas de adjacência e inverta todas essas listas.  Por exemplo, suponha que os 4 vizinhos de um certo vértice u aparecem na lista adj[u] na ordem v, w, x, y.  Depois da aplicação da função, a lista deve conter os mesmos vértices na ordem y, x, w, v.

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.

15. Escreva uma função que receba um grafo representado por matriz de adjacência e construa a correspondente representação por listas de adjacência.
16. Escreva uma função que receba um grafo representado por listas de adjacência e construa a correspondente representação por matriz de adjacência.
17. Considere o problema de decidir se dois vértices são adjacentes num grafo representado por suas listas de adjacência. Quanto tempo consome a solução do problema? Dê sua resposta em função do número de vértices.
18. Escreva uma função que receba dois grafos, digamos G1 e G2, e decida se eles são iguais.
19. Considere o problema de decidir se um vértice é isolado num grafo representado por suas listas de adjacência. Quanto tempo consome a solução do problema? Dê sua resposta em função do número de vértices.
20. Uma clique num grafo é um conjunto de vértices dois-a-dois adjacentes.  Uma panela é uma clique formada por vértices "consecutivos", ou seja, uma clique da forma {i+1,i+2,..,i+k}.  Escreva uma função que encontre uma panela máxima.  Faça duas versões de sua função: uma para matriz de adjacência e outra para listas de adjacência. Sua função deve consumir tempo proporcional a V² no máximo.

Construção de grafos e digrafos

21. 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 um arco, podemos dizer que o arquivo define um digrafo com vértices 0..V-1.  Escreva uma função DIGRAPHconstruct que receba um arquivo gráfico e construa a representação do digrafo por listas de adjacência. Use as funções DIGRAPHinit e DIGRAPHinsertA.   Repita o exercício supondo que o arquivo representa um grafo.

22. Uma grade m-por-n é um grafo com m×n vértices distribuídos em m linhas e n colunas com arestas ligando vértices "vizinhos" na horizontal e na vertical da maneira óbvia.  A figura abaixo sugere uma grade 3-por-4.

                     o--o--o--o
                     |  |  |  |
                     o--o--o--o
                     |  |  |  |
                     o--o--o--o
    

    Escreva uma função que construa uma grade m×n. Faça duas versões: uma gera uma representação por matriz de adjacência e outra gera uma representação por listas de adjacência.

23. Dado um grafo G, o grafo L(G) é definido assim:  cada vértice de L(G) representa uma aresta de G e dois vértices de L(G) são adjacentes se as correspondentes arestas de G têm uma ponta em comum.  O grafo L(G) é conhecido como grafo das arestas (= line graph) de G.  Escreva uma função que receba um grafo G e construa o grafo das arestas de G.