1. 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 n e o número de arestas m. Nas próximas m linhas temos pares u e v (0 ≤ u,v) indicando cada aresta. Exemplo de arquivo:
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 n e m, alocamos o vetor de listas e inicializamos tudo como NULL. Em seguida, pra cada aresta u,v, criamos dois nós (um pra v na lista de u e outro pra u na lista de v), 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 i exibe todos os seus vizinhos seguindo os ponteiros até NULL.

Resposta

#include <stdio.h>
#include <stdlib.h>
// nó de lista que armazena um vértice adjacente
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;
// 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;
}
// 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 *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");
}
}
int main(int argc, char *argv[]) {
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;
}

Exercícios relacionados