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