Algoritmos para Grafos, via Sedgewick | Índice remissivo
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.)
Eis o conjunto de arcos de um digrafo e o vetor de listas de adjacência do digrafo:
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
|
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.] Uma estrutura análoga será usada para representar grafos: basta trocar "digraph" e "Digraph" por "graph" e "Graph" e trocar "A" por "E". As definições de node, link e NEW são as mesmas dos digrafos.
/* A estrutura graph representa um grafo. O campo adj é um ponteiro para o vetor de listas de adjacência do grafo, o campo V contém o número de vértices e o campo E contém o número de arestas do grafo. */
struct graph { int V; int E; link *adj; };/* Um objeto do tipo Graph contém o endereço de um graph. */
typedef struct graph *Graph;
Essas estruturas não devem ser consideradas definitivas. Elas poderão ser modificadas e adaptadas adiante, conforme as necessidades.
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) { Vertex 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, basta fazer as adaptações óbvias:
Graph GRAPHinit( int V) { Vertex v; Graph G = malloc( sizeof *G); G->V = V; G->E = 0; G->adj = malloc( V * sizeof (link)); for (v = 0; v < V; v++) G->adj[v] = NULL; return G; }void GRAPHinsertE( Graph 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->adj[w] = NEW( v, G->adj[w]); G->E++; }
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.
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
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
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.
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.
7
0-1
0-5
1-0
1-5
2-4
3-1
(É claro que o último caractere do arquivo é um \n.) 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 aas listas de adjacência do grafo. Use as funções GRAPHinit e GRAPHinsertE.
7
0 1 5 1
1 0 5 3
2 4
3 1
4 2
5 0 1
6
(É claro que o último caractere do arquivo é um \n.) Um arquivo gráfico representa um grafo com vértices 0..V-1. As últimas V linhas do arquivo definem as listas adjacência do grafo. Escreva uma função GRAPHconstruct que receba um arquivo gráfico e construa as listas de adjacência do grafo. Use as funções GRAPHinit e GRAPHinsertE.
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.
Resposta: Veja a resposta na página de matrizes de adjacência.