Representações Computacionais

Até aqui descrevemos grafos de forma abstrata. Para armazená-los e manipulá-los em computador, precisamos de representações concretas. Vamos usar os mesmos grafos da seção passada:

graph LR
  subgraph s1["Grafo A"]
    A((a)) 
    B((b))
    C((c))
    D((d))
  end

  subgraph s2["Grafo B"]
    direction LR 
    A1((e)) 
    B1((f))
    C1((g))
    D1((h))
  end

    A --- B
    B --- C
    C --- A
    B --- D

    A1 --> B1
    B1 --> C1
    C1 --> A1
    C1 --> D1

    s1 ~~~ s2

A:::WT
B:::WT
C:::WT
D:::WT

A1:::WT
B1:::WT
C1:::WT
D1:::WT
classDef WT fill:#FFFFFF
style s1 stroke:none,fill:transparent
style s2 stroke:none,fill:transparent

Matriz de Adjacência

Dado o grafo com \(n\) vértices, a matriz de adjacência é uma matriz quadrada de ordem \(n\) em que as linhas e colunas são os vértices. O valor na posição \((i, j)\) indica se existe aresta entre o vértice \(i\) e o vértice \(j\). Usamos \(1\) para existência e \(0\) para ausência.

Para os grafos A e B:

Matriz de adjacência do grafo A
	A	B	C	D
A	0	1	1	0
B	1	0	1	1
C	1	1	0	0
D	0	1	0	0

Note que a matriz é simétrica (\(A=A^T\)) para grafos não-direcionados.

Matriz de adjacência do grafo B
	A	B	C	D
A	0	1	0	0
B	0	0	1	0
C	1	0	0	1
D	0	0	0	0

Note que as linhas representam de onde as arestas partem. Já as colunas, representam onde elas incidem.

Implementação

Vamos implementar a matriz de adjacência para um grafo não-direcionado. Fica como tarefa realizar a implementação da versão direcionada.

#define V 4 // Grafo com quatro vértices

void add_edge(int mat[V][V], int i, int j) {
    mat[i][j] = 1;
    mat[j][i] = 1; 
}

A função add_edge (adicionar aresta) recebe uma matriz quadrada de ordem V (número de vértices) e os vértices que estão conectados por uma aresta. Como o grafo é não-direcionado, a matriz deve ser simétrica, isto é, mat[i][j] = mat[j][i] = 1.

Uma dica de segurança para a função add_edge é adicionar a seguinte linha:

if (i < 0 || i >= V || j < 0 || j >= V) return;

Isso vai garantir que não serão passados valores fora do intervalo permitido.

Para imprimir a matriz, utilizamos um laço duplo percorrendo as linhas e colunas:

void display_matrix(int mat[V][V]) {
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++)
        printf("%d ", mat[i][j]);
    printf("\n");
  }
}

Para testar a implementação, considere o grafo A.

int main() {
    int mat[V][V] = {0};

    add_edge(mat, 0, 1);
    add_edge(mat, 0, 2);
    add_edge(mat, 1, 2);
    add_edge(mat, 1, 3);

    display_matrix(mat);

    return 0;
}

Se liga! O comando int mat[V][V] = {0} inicializa a matriz com zero em todas as posições.

Neste modelo, trocamos os rótulos \(a,b,c\) e \(d\) por índices na matriz. Por exemplo, add_edge(mat, 0, 1) corresponde à aresta entre os vértices \(a\) e \(b\).

Exercício

Modifique a implementação anterior para grafos direcionados. Use o grafo B para testar seu código.

Refinamento

Nota-se que é muito simples implementar uma matriz de adjacências. Nesta subseção, propomos algumas modificações a fim de obter um código mais funcional.

Ao invés de termos um grafo com tamanho fixo definido por uma constante, vamos criar nossa matriz usando o tamanho do conjunto de vértices dinâmicamente.

A função zeros aloca uma matriz bidimensional com lin linhas e col colunas, inicializando todas as posições com zero. O uso de calloc garante tanto a alocação quanto a inicialização. Em caso de falha durante a alocação de alguma linha, toda a memória previamente alocada é corretamente liberada.

int** zeros(size_t lin, size_t col) {
  int **matrix = calloc(lin, sizeof(int *));
  if (!matrix) return NULL;

  for (size_t i = 0; i < lin; i++) {
      matrix[i] = calloc(col, sizeof(int));
      if (!matrix[i]) {
          for (size_t k = 0; k < i; k++)
              free(matrix[k]);
          free(matrix);
          return NULL;
      }
  }
     
  return matrix; 
}

void display_matrix(int** matrix, size_t lin, size_t col) {
  for (size_t  i = 0; i < lin; i++) {
    for (size_t  j = 0; j < col; j++)
        printf("%d ", matrix[i][j]);
    printf("\n");
  }
}

Na linha 1, estamos alocando memória para um vetor de ponteiros. Como a alocação é feita com calloc, todos os ponteiros são inicializados com o valor zero, isto é, NULL. Como de praxe, na linha seguinte, verificamos se a alocação foi realizada com sucesso.

O laço da linha 5 aloca memória para as linhas da matriz utilizando calloc, garantindo que todas as posições sejam inicializadas com zero. Após cada alocação, verificamos se ela foi bem-sucedida. Em caso de falha, liberamos a memória previamente alocada para as linhas anteriores e para o vetor de ponteiros.

A função auxiliar display_matrix é usada para imprimir uma matriz. Por exemplo, o código abaixo

int** mat = zeros(3, 4);
display_matrix(mat, 3, 4);

vai gerar a seguinte saída:

0 0 0 0 
0 0 0 0 
0 0 0 0

Uma vez que alocamos memória, precisamos liberar o espaço reservado quando finalizarmos o programa.

void destroy_matrix(int** matrix, size_t lin) {
  for (size_t i = 0; i < lin; i++)
    free(mat[i]);
  free(mat); 
}

Primeiramente, liberamos a memória de cada linha com free(mat[i]). Depois liberamos o vetor de ponteiros mat.

Agora podemos trabalhar com a semâtica de grafos ao invés de matrizes. Primeiro, vamos criar um nova estrutura que contém uma matriz de ordem \(|V|\times |V|\).

typedef struct {
  size_t V;
  int** adj_matrix;
} Graph;

Usamos size_t para armazenar a ordem do grafo, isto é, o número de vértices. Lembre-se que size_t é usado para contagem de elementos ou tamanho de estruturas por se tratar de um inteiro sem sinal e, portanto, não admite valores negativos.

Sabemos que a matriz de adjacência de um grafo é sempre quadrada, portanto:

Graph* simple_graph(size_t V) {
  Graph* graph = malloc(sizeof(Graph));
  if(!graph) return NULL;

  graph->V = V;
  graph->adj_matrix = zeros(V, V);
   
  return graph; 
}

Assim, a função simple_graph nada mais faz do que criar uma estrutura do tipo Graph na memória heap e instanciar a matriz quadrada de ordem V inicialmente preenchida com zeros, representando um grafo sem arestas.

Para adicionar uma aresta entre dois vértices v e u, vamos associar a ela um peso w. Note que verificamos se os índices v e u pertencem ao intervalo válido.

void add_edge(Graph* graph, size_t v, size_t u, int w) {
  if (u >= graph->V || v >= graph->V) return;
 
  graph->adj_matrix[v][u] = w;
  graph->adj_matrix[u][v] = w; 
}

Também tomamos cuidado para que não fossem acessadas posições negativas na matriz usando size_t.

Nota

Neste modelo, pesos iguais a zero não são permitidos, pois o valor zero é reservado para indicar ausência de aresta.

As funções a seguir calculam o grau e a vizinhança de um vértice v em um grafo não-direcionado representado por matriz de adjacência. A condição mat[v][j] != 0 indica a existência de uma aresta entre os vértices v e j.

size_t degree(Graph* graph, size_t v) {
  size_t deg = 0;
  for (size_t j = 0; j < graph->V; j++){
    if (graph->adj_matrix[v][j] != 0)
      deg++;
    }
  return deg;
}

size_t* neighborhood(Graph* graph, size_t v) {
  if (v >= graph->V) return NULL;
  
  size_t k = 0; 
  size_t size = degree(graph, v); 
  size_t* neighbor = malloc(size*sizeof(size_t));
  
  if (!neighbor) return NULL;
  
  for (size_t j = 0; j < graph->V; j++){
    if (graph->adj_matrix[v][j] != 0)
      neighbor[k++] = j;
  }
  return neighbor;
}

A função neighborhood recebe o grafo graph e um vértice v. Ela percorre a linha correspondente a v na matriz de adjacência, preenchendo o conjunto de vértices adjacentes.

As próximas funções imprimem a matriz de adjacências e a vizinhança, respectivamente.

void display_graph(Graph* graph) {
  display_matrix(graph->adj_matrix, graph->V, graph->V);
}

void display_neighborhood(size_t* neighbor, size_t size) {
  printf("N(v) = { ");
  for (size_t i = 0; i < size; i++)
    printf("%zu ", neighbor[i]);
  printf("}\n");     
}

Finalmente, vamos encapsular a função destroy_matrix para obtermos uma consistência semântica.

void destroy_graph(Graph* graph) {
  destroy_matrix(graph->adj_matrix, graph->V);
  free(graph);
}

Exemplo de uso para o grafo A:

int main() {

  size_t V = 4;
  Graph* g = simple_graph(V);
  
  add_edge(mat, 0, 1, 1); // Liga 'a' e 'b' 
  add_edge(mat, 0, 2, 1); // Liga 'a' e 'c'
  add_edge(mat, 1, 2, 1); // Liga 'b' e 'c'
  add_edge(mat, 1, 3, 1); // Liga 'b' e 'd'

  printf("Representação por Matriz de Adjacencia:\n");
  display_graph(g);
    
  size_t v = 2;
  size_t* neighbor = malloc(V * sizeof(size_t));
  size_t deg = neighborhood(g, v, neighbor);
    
  printf("\nO vertice v = %zu possui %zu vizinho(s): ", v, deg);

  display_neighborhood(neighbor, deg);
    
  destroy_graph(g);
  free(neighbor); 
  
  return 0;   
}

Saída:

Representação por Matriz de Adjacencia:
0 1 1 0 
1 0 1 1 
1 1 0 0 
0 1 0 0 

O vertice v = 2 possui 2 vizinho(s): N(v) = { 0 1 }

Exercício

Modifique a implementação anterior para grafos direcionados. Use o grafo B para testar seu código. Lembre-se que agora temos de calcular a vizinhança/grau de entrada e de saída.

size_t degree_in(Graph* graph, size_t v);
size_t degree_out(Graph* graph, size_t v);
size_t* neighborhood_in(Graph* graph, size_t v);
size_t* neighborhood_out(Graph* graph, size_t v);

A função para imprimir a vizinhança deve mostrar a vizinhança de entrada e a de saída, por exemplo:

O vertice v = 2 possui 3 vizinho(s): N-(v) = { 1 } e N+(v) = { 0 3 }

Se liga! A matriz de adjacência não pode ser usada para implementar multigrafos naturalmente, pois ela não distingue arestas paralelas e, por isso, exige adaptações.

Lista de Adjacência

A lista de adjacência nada mais é que uma lista de vizinhos para cada vértice.

Usando os mesmos exemplos anteriores, para o grafo A:

\(\mathcal{N}(a) = \{b, c\}\)
\(\mathcal{N}(b) = \{a, c, d\}\)
\(\mathcal{N}(c) = \{a, b\}\)
\(\mathcal{N}(d) = \{b\}\)

Para o grafo direcionado B, temos:

\(\mathcal{N^-}(e)=\{g\}\text{ e }\mathcal{N^+}(e)=\{f\}\)
\(\mathcal{N^-}(f)=\{e\}\text{ e }\mathcal{N^+}(f)=\{g\}\)
\(\mathcal{N^-}(g)=\{f\}\text{ e }\mathcal{N^+}(g)=\{e,h\}\)
\(\mathcal{N^-}(h)=\{g\}\text{ e }\mathcal{N^+}(h)=\emptyset\)

Implementação

Para implementar essas listas, vamos construir listas ligadas.

typedef struct node {
  int dest;
  struct node* next;
} Node;

typedef struct {
  size_t V;
  Node** list_adj;
} Graph;

Node* create_node(int dest) {
  Node* new_node = malloc(sizeof(Node));
  if(!new_node) return NULL;

  new_node->dest = dest;
  new_node->next = NULL;
    
  return new_node;
}

Graph* simple_graph(int V) {
  Graph* graph = malloc(sizeof(Graph));
  if(!graph) return NULL;
  
  Node** list_adj = calloc(V, sizeof(Node*));
  if(!list_adj) return NULL;
    
  graph->V = V;
  graph->list_adj = list_adj;
        
  return graph;
}

void destroy_graph(Graph* graph) {
  for(size_t i = 0; i < graph->V;i++)
    free(graph->list_adj[i]);
  free(graph);
}

void add_edge(Graph* graph, int src, int dest) {    
  Node* new_node = create_node(dest);
  new_node->next = graph->array[src];
  graph->array[src] = new_node;

  new_node = create_node(src);
  new_node->next = graph->array[dest];
  graph->array[dest] = new_node;
}

size_t degree(Graph* graph, size_t v) {
  size_t deg = 0;
  for (Node* cur = graph->list_adj[v]; cur; cur = cur->next)
    deg++;
  return deg;
}

Node* neighborhood(Graph* graph, size_t v) {
  return graph->list_adj[v];
}

void display_graph(Graph* graph) {
  for (size_t i = 0; i < graph->V; i++) {
    printf("%zu:", i);
    for (Node* cur = graph->array[i]; cur; cur = cur->next) {
      printf(" %d", cur->dest);
    }
    printf("\n");
  }
}

void display_neighborhood(Node* neighbor, size_t size) {
  printf("N(v) = { ");
  for (Node* cur = neighbor; cur; cur = cur->next)
    printf("%d ", cur->dest);
  printf("}\n");     
}

int main() {
  size_t V = 4;
  Graph* graph = simple_graph(V);

  add_edge(graph, 0, 1);
  add_edge(graph, 0, 2);
  add_edge(graph, 1, 2);
  add_edge(graph, 1, 3);
  
  printf("Representação por Lista de Adjacencia:\n");
  display_graph(graph);

  size_t v = 2;
  size_t deg = degree(graph, v);
  Node* neighbor = neighborhood(graph, v);
    
  printf("\nO vertice v = %zu possui %zu vizinho(s): ", v, deg);

  display_neighborhood(neighbor, deg);
  destroy_graph(graph);
  
  return 0;
}

Representação por Lista de Adjacencia:
0: 2 1
1: 3 2 0
2: 1 0
3: 1

O vertice v = 2 possui 2 vizinho(s): N(v) = { 1 0 }

Matriz de Incidência

Dado o grafo com \(n\) vértices e \(m\) arestas, a matriz de incidência é uma matriz \(n\times m\) em que as linhas são os vértices, as colunas são as arestas e o valor na interseção indica se a aresta incide sobre o vértice.

Matriz de incidência do grafo A
	(A,B)	(A,C)	(B,C)	(B,D)
A	1	1	0	0
B	1	0	1	1
C	0	1	1	0
D	0	0	0	1

Note que a soma de cada coluna é sempre 2.

Matriz de adjacência do grafo da sec-dir
	(A,B)	(B,C)	(C,A)	(C,D)
A	-1	0	1	0
B	1	-1	0	0
C	0	1	-1	-1
D	0	0	0	1

No caso de grafo direcionado, atribuímos \(-1\) se a aresta \(e\) sai de \(v\), \(1\) se a aresta \(e\) entra em \(v\) e \(0\) caso contrário. Logo, a soma das colunas deve ser sempre zero.

Implementação

Considerando a implementação da matriz de adjacência, vamos reutilizar as funções:

zeros
display_matrix
destroy_matrix
display_neighborhood
destroy_graph

A matriz de incidência não é necessariamente quadrada, portanto:

typedef struct {
  size_t V; // vertices: linha
  size_t E; // arestas: coluna
  int** inc_matrix;
} Graph;

Também modificamos o nome da matriz para inc_matrix para se referir a incidência. Dessa forma, reaproveitamos as funções add_edge, degree e neighborhood trocando adj_matrix por inc_matrix.

A função para criar um grafo vazio (matriz com zero em todas as posições) é semelhante ao caso da matriz de adjacência. Só temos de garantir que a matriz tenha V linhas e E colunas.

Graph* simple_graph(size_t V, size_t E) {
  Graph* graph = malloc(sizeof(Graph));
  if(!graph) return NULL;

  graph->V = V;
  graph->E = E;
  graph->inc_matrix = zeros(V, E);
   
  return graph; 
}

Para imprimir a matriz, temos de tomar cuidado para passar as linhas e colunas corretamente.

void display_graph(Graph* graph) {
  display_matrix(graph->inc_matrix, graph->V, graph->E);
}

Agora, um exemplo de uso usando o grafo A novamente:

int main() {
  size_t V = 4; // vertices
  size_t E = 4; // arestas

  Graph* g = simple_graph(V, E);
  add_edge(g, 0, 1, 1);
  add_edge(g, 1, 2, 1);
  add_edge(g, 2, 3, 1);
  add_edge(g, 2, 0, 1);
    
  printf("Representação por Matriz de Incidencia:\n");
  display_graph(g);
    
  size_t v = 2;
  size_t deg = degree(g, v);
  size_t* neighbor = neighborhood(g, v);
    
  printf("\nO vertice v = %zu possui %zu vizinho(s): ", v, deg);
  display_neighborhood(neighbor, deg);
    
  destroy_graph(g);
  free(neighbor); 
    
  return 0;   
}

Representação por Matriz de Incidencia:
0 1 1 0 
1 0 1 0 
1 1 0 1 
0 0 1 0 

O vertice v = 2 possui 3 vizinho(s): N(v) = { 0 1 3 }

Exercício

Modifique a implementação anterior para grafos direcionados. Use o grafo B para testar seu código. Lembre-se que agora temos de calcular a vizinhança/grau de entrada e de saída.

Nesta seção, estudamos como os grafos podem ser representados na programação. Nós

✅ estudamos a matriz de adjacência, as listas de adjacência e a matriz de incidência;

✅ implementamos os algoritmos para determinar o grau de um vértice e sua vizinhança.

De volta ao topo