Algoritmos para Grafos  |  Índice

Custos nos arcos e arestas

Muitas aplicações associam um número com cada arco do grafo. Numa rede de estradas, por exemplo, é natural levar em conta o extensão de cada estrada em quilometros, ou o custo do pedágio.

Grafos com custos nos arcos

Dado um grafo G, suponha que temos um função c que associa um número c_a com cada arco a de G.  Diremos que  c_a  é o custo [o livro de Sedgewick diz weight] do arco a.  Vamos supor que os custos são números do tipo int, podendo ser positivos e negativos.  (A restrição a custos inteiros não é uma limitação grave pois números fracionários podem ser convertidos em número inteiros mediante multiplicação por uma constante suficientemente grande.)

Muitos livros usam o termo rede (= network) para se referira um grafo que tem custos associados aos arcos.

Em algumas aplicações, pode ser apropriado dizer peso no lugar de custo.  Em outras aplicações, pode ser mais apropriado dizer capacidade.

Matriz de adjacências com custos

Num grafo com custos nos arcos, a matriz de adjacências, adj, tem dupla função: além de indicar a presença e ausência de arcos, ela armazena os custos dos arcos.  Se os vértices v e w são adjacentes então adj[v][w] é o custo do arco v-w. Senão, adj[v][w] vale

INFINITY .

Em geral, basta que a constante INFINITY seja maior que o valor absoluto do custo de qualquer arco. Mas em algumas aplicações pode ser mais apropriado adotar o valor 0 ou -1.

Exemplo:  Eis a matriz de adjacências de um grafo com custos nos arcos. (Todos os custos são positivos neste exemplo.)  Os caracteres - representam a constante INFINITY.

     0  1  2  3  4  5  6  7
                              
0    - 31 29  -  - 60 51 31
1   32  -  -  -  -  -  - 21
2   28  -  -  -  -  -  -  -
3    -  -  -  - 34 18  -  -
4    -  -  - 34  - 40 51 46
5   60  -  - 18 40  -  -  -
6   51  -  -  - 51  -  - 25
7   31 21  -  - 46  - 25  - 
                                   

Para inicializar a matriz de adjacências de um grafo, podemos usar uma adaptação óbvia das funções MATRIXint() e GRAPHinit().  Para inserir arcos no grafo, usaremos uma adaptação óbvia da função GRAPHinsertArc().

Listas de adjacência com custos

Na representação por listas de adjacência, basta acrescentar aos nós node um campo c para acomodar os custos dos arcos.

typedef struct node *link;
struct node { 
   vertex w; 
   int c; 
   link next; 
};

É claro que um terceiro argumento, correspondente ao custo, deverá ser acrescentado às funções NEWnode() e GRAPHinsertArc() (que tem a missão de inserir um novo arco no grafo).

Grafos não-dirigidos e suas arestas

Grafos não-dirigidos 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 formam a aresta.

#define UGraph Graph
#define UGRAPHinit GRAPHinit

/* Insere no grafo não-dirigido G uma aresta com pontas 
   v e w e custo c.
   A função supõe que v e w sã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 UGRAPHinsertEdge( Graph G, vertex v, vertex w, int c) { 
   if (G->adj[v][w] == INFINITY) {
      G->adj[v][w] = c; 
      G->adj[w][v] = c; 
      G->A += 2;
   }
}

Variante para listas de adjacência:

void UGRAPHinsertEdge( Graph G, vertex v, vertex w, int c) { 
   for (link a = G->adj[v]; a != NULL; a = a->next) 
      if (a->w == w) return;
   G->adj[v] = NEWnode( w, G->adj[v], c);
   G->adj[w] = NEWnode( v, G->adj[w], c);
   G->A += 2;
}