Grafos

Listas de Adjacência:  Uma Implementação simples  na linguagem C.

O primeiro passo na implementação dos grafos consiste em definir num ficheiro de definições o tipo de dados do grafo e das listas de adjacência. 
 

• Antes de definirmos o tipo do grafo, vamos comecar por definir o tipo das listas de adjacência.  As listas de adjacência são implementadas com listas ligadas. Assim, vamos definir o tipo do nodo dessas listas:

 

typedef struct nodo
{ VERTICE v;
  struct nodo * next;
} NODO;
 
 

• Este é o tipo de um nodo da lista. O tipo da listas de adjacência é definido em C como um apontador para este nodo.

typedef NODO * ADJ;
 
 
O grafo pode agora ser definido como um sequência (array) de apontadores para as listas de adjacência.  Em C este grafo é definido do seguinte modo:

ADJ GRAFO[N];
 
em que N é o numero de vértices do grafo.
 

• Esta definição, porém, implica que estaticamente  se especifique qual o número máximo de  vértices que um dado grafo pode conter! Uma alternativa mais eficiente de definir o tipo do grafo consiste em defini-lo como uma sequência de apontadores para as listas de adjacência:

typedef ADJ * GRAFO;
 

E dinamicamente construir uma sequência de apontadores igual ao número máximo de vértices de um dado grafo.
 
 

• Nesta implementação consideramos que o tipo dos vértices dos grafos são inteiros:

typedef int VERTICE;
 

• De seguida definimos uma série de macros para  simplificar o acesso aos vários campos de um nodo da lista ligada de adjacências, para testar se a lista e vazia e para construir um novo nodo da lista. Estas macros são depois usadas na implementação tornando-a mais legível e simplificando o seu código.

#define EL(n)      n->v
#define NEXT(l)    l->next
#define EMPTY(l)   (l == NULL)
#define CONSNODO   (ADJ)malloc(sizeof(NODO))
 
 

• No ficheiro de definições incluímos ainda o tipo das funções que manipulam o grafo e as listas ligadas de adjacência:

 

GRAFO   novo_grafo      (int nvertices);
GRAFO   add_ramo        (GRAFO g , VERTICE v1,VERTICE v2);
ADJ     sucessores      (GRAFO g , VERTICE v);
BOOLEAN is_sucessor     (GRAFO g , VERTICE v1 , VERTICE v2);
void    show_sucessores (GRAFO g , VERTICE v);
ADJ     antecessores    (GRAFO g , VERTICE v);

ADJ     ins_lista_adjacentes  (ADJ l , VERTICE v);
void    show_lista_adjacentes (ADJ l);
 

A implementação dos grafos é codificado no ficheiro de implementação.
 

• O ficheiro de implementação importa o ficheiro de definições:

#include "listas_adj.h"
 
 

• Criar uma novo grafo corresponde a

GRAFO novo_grafo(int nvertices)
{ GRAFO g;
  int i;

  g = (GRAFO)malloc( sizeof(ADJ) * nvertices );
  for (i = 0 ; i < nvertices ; ++i)
    *(g+i) = NULL;
  return g;
}
 

 

• Adicionar um ramo ao grafo:

GRAFO add_ramo(GRAFO g , VERTICE v1 , VERTICE v2)
{
  *(g+v1) = ins_lista_adjacentes(*(g+v1),v2);
  return g;
}
 
 

• Usando lista de adjacência facilmente se obtém os vértices sucessores de um dados vértice v:

os sucessores são os vértices existentes na lista de adjacentes de v.

ADJ sucessores(GRAFO g,VERTICE v)
{
  return *(g + v);
}

 

• Verificar se um dado vértice é sucessor  corresponde a verificar se esse vértice está na respectiva lista de adjacentes.

BOOLEAN is_sucessor (GRAFO g , VERTICE v1 , VERTICE v2)
{
  return isin(*(g+v1),v2);
}

 

• Determinar os antecessores é nesta representaçao de grafos um pouco mais complicado, pois cada vértice contém apenas uma referência para os seus sucessores e não para os seus antecessores.  Assim, para determinarmos os antecessores de um vértice v precisamos de verificar para todos os vértices i do grafo se v e um sucessor de i. Nesse caso,  i e inserido na lista de nodos adjacentes (i.e., antecessores) de v.

ADJ antecessores (GRAFO g , VERTICE v , int nvertices)
{ int i;
  ADJ l;

  l = NULL;
  for ( i = 0 ; i < nvertices ; ++i )
    { if ( isin(*(g+i),v) )
         l = ins_lista_adjacentes(l,i);
    }
  return l;
}
 

 
• De seguida definimos um procedimento que imprime  os sucessores de um vértice. O resultado deste procediemnto e o efeito lateral de imprimir  no ecran os vertices sucessores.

void show_sucessores (GRAFO g , VERTICE v)
{
  show_lista_adjacentes(sucessores(g,v));
}

---


 
• As funções que manipulam a lista de adjacências são funções normais sobre listas ligadas. Aqui apresentam-se  funçães bastante simples.

ADJ ins_lista_adjacentes (ADJ l , VERTICE v)
{ ADJ a;

  a = CONSNODO;

  EL(a)   = v;
  NEXT(a) = l;
  return a;
}

BOOLEAN isin (ADJ l , VERTICE v)
{
  if EMPTY(l) return FALSE;
  else
    if (EL(l) == v) return TRUE;
    else return isin(NEXT(l),v);
}
 

void show_lista_adjacentes (ADJ l)
{
  if ( !EMPTY(l) )
  { printf(" %d ",EL(l));
    show_lista_adjacentes(NEXT(l));
  }
}
 
 

• Aqui podem encontrar a implementação de grafos usando listas de adjacência discutidas nas aulas teorico-praticas. Depois de descomprimir o ficheiro basta fazer make e invocar o programa de teste grafo.

Enviar comentários para jas@di.uminho.pt.
Ultima modificação: 26/10/1998