- Crie um programa para ler um grafo a partir de um arquivo e armazená-lo em uma estrutura de lista de adjacência. Crie um formato para o seu arquivo de entrada.
Passo 1
O enunciado pede pra gente criar um programa em C que leia um grafo a partir de um arquivo e armazene internamente usando lista de adjacência. O conteúdo é Estrutura de Dados (listas ligadas e I/O de arquivos). Vamos precisar definir um formato de arquivo, depois implementar as estruturas (vértices e nós de lista) e ler o arquivo pra popular essa estrutura.
Passo 2
Definimos um formato simples para grafo não direcionado e não ponderado. No arquivo de entrada, a primeira linha tem dois inteiros: o número de vértices
e o número de arestas
. Nas próximas
linhas temos pares
e
(0 ≤
) indicando cada aresta. Exemplo de arquivo:
5 6
0 1
1 2
2 3
3 4
4 0
1 3
5 6
0 1
1 2
2 3
3 4
4 0
1 3
Passo 3
Criamos as estruturas em C. Um nó de lista armazena o vértice adjacente e um ponteiro pro próximo nó. E temos um vetor de ponteiros, onde cada posição corresponde a um vértice e aponta pro início da sua lista de adjacência.
Passo 4
Implementamos a função de leitura: abrimos o arquivo, lemos
e
, alocamos o vetor de listas e inicializamos tudo como NULL. Em seguida, pra cada aresta
, criamos dois nós (um pra
na lista de
e outro pra
na lista de
), inserindo sempre no início (inserção O(1)).
Passo 5
Por fim, mostramos como percorrer e imprimir a lista de adjacência pra verificar. Cada vértice
exibe todos os seus vizinhos seguindo os ponteiros até NULL.
Resposta
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
// nó de lista que armazena um vértice adjacente
typedef struct AdjNo {
int vert;
struct AdjNo *prox;
} AdjNo;
typedef struct AdjNo {
int vert;
struct AdjNo *prox;
} AdjNo;
// grafo: vetor de listas de adjacência
typedef struct Grafo {
int n; // número de vértices
int m; // número de arestas
AdjNo **adj; // vetor de ponteiros para as listas
} Grafo;
typedef struct Grafo {
int n; // número de vértices
int m; // número de arestas
AdjNo **adj; // vetor de ponteiros para as listas
} Grafo;
// cria um nó e já configura vertice e próximo
AdjNo* cria_no(int v) {
AdjNo novo = (AdjNo) malloc(sizeof(AdjNo));
if (!novo) {
perror(“malloc”);
exit(EXIT_FAILURE);
}
novo->vert = v;
novo->prox = NULL;
return novo;
}
AdjNo* cria_no(int v) {
AdjNo novo = (AdjNo) malloc(sizeof(AdjNo));
if (!novo) {
perror(“malloc”);
exit(EXIT_FAILURE);
}
novo->vert = v;
novo->prox = NULL;
return novo;
}
// lê o grafo de um arquivo, seguindo o formato descrito
Grafo* le_grafo(const char *nome_arquivo) {
FILE *f = fopen(nome_arquivo, “r”);
if (!f) {
perror(“fopen”);
exit(EXIT_FAILURE);
}
Grafo* le_grafo(const char *nome_arquivo) {
FILE *f = fopen(nome_arquivo, “r”);
if (!f) {
perror(“fopen”);
exit(EXIT_FAILURE);
}
Grafo *G = (Grafo*) malloc(sizeof(Grafo));
if (!G) {
perror("malloc");
exit(EXIT_FAILURE);
}
// lê número de vértices e arestas
fscanf(f, "%d %d", &G->n, &G->m);
// aloca vetor de listas e inicializa
G->adj = (AdjNo**) malloc(G->n * sizeof(AdjNo*));
if (!G->adj) {
perror("malloc");
exit(EXIT_FAILURE);
}
for (int i = 0; i < G->n; i++)
G->adj[i] = NULL;
// lê cada aresta e insere nas duas listas (grafo não direcionado)
for (int i = 0; i < G->m; i++) {
int u, v;
fscanf(f, "%d %d", &u, &v);
// insere v na lista de u
AdjNo *no_v = cria_no(v);
no_v->prox = G->adj[u];
G->adj[u] = no_v;
// insere u na lista de v
AdjNo *no_u = cria_no(u);
no_u->prox = G->adj[v];
G->adj[v] = no_u;
}
fclose(f);
return G;
}
// imprime o grafo
void imprime_grafo(Grafo *G) {
for (int i = 0; i < G->n; i++) {
printf("%d:", i);
for (AdjNo *p = G->adj[i]; p != NULL; p = p->prox) {
printf(" -> %d", p->vert);
}
printf("\n");
}
}
void imprime_grafo(Grafo *G) {
for (int i = 0; i < G->n; i++) {
printf("%d:", i);
for (AdjNo *p = G->adj[i]; p != NULL; p = p->prox) {
printf(" -> %d", p->vert);
}
printf("\n");
}
}
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, “Uso: %s <arquivo_de_entrada>\n”, argv[0]);
return EXIT_FAILURE;
}
if (argc != 2) {
fprintf(stderr, “Uso: %s <arquivo_de_entrada>\n”, argv[0]);
return EXIT_FAILURE;
}
Grafo *G = le_grafo(argv[1]);
imprime_grafo(G);
// liberar memória omitido por brevidade
return 0;
}