1. Implemente a TAD Grafo utilizando uma lista de adjacências para armazenar os vértices e arestas.

Passo 1

O enunciado pede para implementar um TAD (Tipo Abstrato de Dados) Grafo usando lista de adjacências para armazenar vértices e arestas. O conteúdo envolve estruturas de dados (listas ligadas) e operações básicas de grafos (criar grafo, inserir aresta, liberar memória etc.). Vamos precisar definir estruturas em C para o nó de adjacência, a lista de adjacência e o grafo, e depois implementar funções para criar o grafo, inserir arestas, imprimir e liberar tudo.

Passo 2

Primeiro, definimos as estruturas essenciais: um nó de lista ligada (AdjListNode) que guarda o vértice destino e um ponteiro para o próximo nó; uma lista de adjacências (AdjList) com ponteiro para o início da lista; e o próprio grafo (Graph), que armazena o número de vértices e um array de listas adjacentes.
Em seguida, criamos uma função para alocar e inicializar um novo nó de adjacência a partir de um vértice destino. Depois, definimos a função createGraph que aloca o grafo, guarda o número de vértices e inicializa cada lista de adjacência como vazia.

Passo 3

Para inserir uma aresta, na função addEdge adicionamos um nó no início da lista do vértice de origem apontando para o destino. Como vamos considerar grafo não orientado, fazemos o mesmo no sentido inverso.

Passo 4

Depois, a função printGraph percorre cada lista de adjacência e imprime os vértices adjacentes, mostrando a estrutura do grafo.

Passo 5

Por fim, a função freeGraph percorre cada lista de adjacência liberando todos os nós, depois libera o array e a própria estrutura do grafo, evitando vazamento de memória.
No final, mostramos um exemplo de uso em main: criamos um grafo de 5 vértices, inserimos algumas arestas, imprimimos e liberamos a memória.

Resposta

#include <stdio.h>
#include <stdlib.h>
typedef struct AdjListNode {
int dest;
struct AdjListNode *next;
} AdjListNode;
typedef struct {
AdjListNode *head;
} AdjList;
typedef struct {
int numVertices;
AdjList *array;
} Graph;
AdjListNode* createNode(int dest) {
AdjListNode *newNode = malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
Graph* createGraph(int vertices) {
Graph *graph = malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->array = malloc(vertices * sizeof(AdjList));
for(int i = 0; i < vertices; i++)
graph->array[i].head = NULL;
return graph;
}
void addEdge(Graph *graph, int src, int dest) {
AdjListNode *newNode = createNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// como é grafo não orientado, adiciona no sentido inverso
newNode = createNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void printGraph(Graph *graph) {
for(int v = 0; v < graph->numVertices; v++) {
AdjListNode *pCrawl = graph->array[v].head;
printf("%d:", v);
while(pCrawl) {
printf(" %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
void freeGraph(Graph *graph) {
for(int v = 0; v < graph->numVertices; v++) {
AdjListNode *current = graph->array[v].head;
while(current) {
AdjListNode *tmp = current;
current = current->next;
free(tmp);
}
}
free(graph->array);
free(graph);
}
int main() {
int V = 5;
Graph *graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
freeGraph(graph);
return 0;
}

Exercícios relacionados