Código para leitura de grafos

Olá, alunos!

Como combinado em sala de aula, todos usarão o mesmo método para leitura dos dados dos grafos nas atividades. Só relembrando, o formado da entrada é esse:

V
A
V1 U1 W1
V2 U2 W2
...
VA UA WA

Onde:

  • V é o número de vértices
  • A é o número de arestas
  • Vn é o vértice de origem da n-ésima aresta
  • Un é o vértice de destino da n-ésima aresta
  • Wn é o peso da n-ésima aresta

Exemplo para um grafo de 3 vértices e 2 arestas, uma ligando o vértice 0 com 1, peso 3; outra ligando o vértice 1 com 2, peso 5:

3
2
0 1 3
1 2 5

Vocês podem digitar esses valores na entrada do programa através do teclado, ou guardá-los em um arquivo de texto, redirecionando a entrada no terminal (como fizemos em sala de aula):

./grafo < exemplo.txt

Lembrem-se de incluir esses dois arquivos de cabeçalho:

#include <stdio.h>
#include <string.h>

Finalmente, o código-fonte:

int v, a, orig, dest, peso;

// Obtém número de vértices e arestas
scanf("%d", &v);
scanf("%d", &a);

// Declara a matriz de adjacências
int G[v][v];
memset(G, 0, v * v * sizeof(int));

// Obtém os dados de cada aresta
for (int i = 0; i < a; i++)
{
    scanf("%d %d %d", &orig, &dest, &peso);
    G[orig][dest] = peso;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

*