Algoritmos para Grafos, via Sedgewick | Índice remissivo
(Esta página é um resumo da seção seção 20.1 (Representations) p.222-225, do capítulo 20 (Minimum Spanning Trees) do livro de Sedgewick.)
Muitas aplicações associam um número a cada arco de um digrafo. Diremos que esse número é o custo da arco. Vamos supor, em geral, que esses números são do tipo double, podendo ser positivos, negativos, ou nulos. Essa associação de custos aos arcos pode ser entendida como uma função que leva o conjunto de arcos num conjunto de números.
Dependendo da aplicação, pode ser apropriado dizer "peso" ou "comprimento" no lugar de "custo". [Sedgewick diz weight no lugar do nosso "custo". Mas isso aumenta o número de variáveis cujo nome começa "w", o que torna os programas menos legíveis.]
Grafos com custos nas arestas têm uma peculiaridade previsível: os dois arcos que constituem cada aresta têm o mesmo custo. O custo de uma aresta, nesse caso, é o custo de qualquer dos dois arcos que constituem a aresta.
Para representar digrafos com custos nos arcos, é preciso fazer algumas alterações simples na representação de digrafos.
typedef struct { Vertex v, w; double cost; } Arc; Arc ARC (Vertex v, Vertex w, double cost) { Arc e; e.v = v; e.w = w; e.cost = cost; return e; }
O campo cost de cada Arc contém o custo do arco v-w. [Sedgewick escreve wt no lugar do meu cost.] As correspondentes definições para grafos são idênticas:
#define Edge Arc #define EDGE ARC
A matriz de adjacência adj tem agora dupla função: além de indicar a presença ou ausência de arco, ela armazena os custos dos arcos. Se os vértices v e w não são adjacentes então adj[v][w] tem o valor de uma constante
maxCOST
apropriada. Caso contrário, adj[v][w] é o custo da arco v-w. O valor de maxCOST deve ser diferente do custo de qualquer arco. Em algumas aplicações, convém que maxCOST seja maior que o custo de qualquer arco (nesse caso, maxCOST terá o sabor de ∞). Em outras aplicações, pode ser mais apropriado adotar o valor 0.
Exemplo: Eis a matriz de adjacência de um grafo com custos nos arestas. (Os "*" representam maxCOST).0 1 2 3 4 5 6 7 0 * .32 .29 * * .60 .51 .31 1 .32 * * * * * * .21 2 .29 * * * * * * * 3 * * * * .34 .18 * * 4 * * * .34 * .40 .51 .46 5 .60 * * .18 .40 * * * 6 .51 * * * .51 * * .25 7 .31 .21 * * .46 * .25 *(Esse exemplo foi copiado das figuras 20.3, p.223, e 20.4, p.226, de Sedgewick.)
O par de funções abaixo pode ser usado para construir digrafos com custos nos arcos. A função MATRIXdouble é uma variante óbvia da função MATRIXint.
/* (Adaptação do programa 20.1, p.224, de Sedgewick.) */
Digraph DIGRAPHinit (int V) { Digraph G = malloc(sizeof *G); G->V = V; G->A = 0; G->adj = MATRIXdouble(V, V, maxCOST); return G; }void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w, double cost) { if (v != w && G->adj[v][w] == maxCOST) { G->adj[v][w] = cost; G->A++; } }
As mesmas funções podem ser usadas para construir grafos, mas é conveniente adaptar os nomes das funções e o código de DIGRAPHinsertA:
#define GRAPHinit DIGRAPHinit void GRAPHinsertE (Digraph G, Vertex v, Vertex w, double cost) { DIGRAPHinsertA(G, v, w, cost); DIGRAPHinsertA(G, w, v, cost); }
É um bom exercício escrever uma função GRAPHremoveE que remova uma aresta de um grafo.
Eis as adaptações necessárias da representação por listas de adjacência. O campo cost de cada node armazena o custo do arco correspondente.
/* (Adaptação do programa 20.2, p.225, de Sedgewick.) */
typedef struct node *link; struct node { Vertex w; double cost; link next; }; link NEW (Vertex w, double cost, link next) { link x = malloc(sizeof *x); x->w = w; x->cost = cost; x->next = next; return x; }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; }void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w, double cost) { 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, cost, G->adj[v]); G->A++; }
Para tratar de grafos, é conveniente adaptar os nomes das funções e reescrever a função de inserção de arestas.
#define GRAPHinit DIGRAPHinit void GRAPHinsertE (Graph G, Vertex v, Vertex w, double cost) { DIGRAPHinsertA(G, v, w, cost); DIGRAPHinsertA(G, w, v, cost); }