Classe Grafo
Lição 3 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.
A classe Graph é construída em torno de um único campo, vertices, que é a lista de adjacência: um mapa de cada chave de vértice para a lista de seus vizinhos. Cada operação que adicionarmos mais tarde (adicionar arestas, listar vizinhos, remover arestas) é apenas uma pequena alteração neste mapa.
O construtor inicia o grafo em seu estado vazio: sem vértices, sem arestas. Portanto, o mapa é apenas um mapa vazio. Os métodos que adicionarmos nas próximas lições irão expandi-lo.
Desafio
FácilEscreva uma classe Graph com um constructor que não recebe entrada.
Inicialize um único campo vertices como um mapa vazio (ou o equivalente da sua linguagem para um mapa de adjacência de chave para lista).
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
static int _cmp_int(const void* a, const void* b) {
int ai = *(const int*)a, bi = *(const int*)b;
return (ai > bi) - (ai < bi);
}
int main() {
Graph g;
Graph_init(&g);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "verticesEmpty") == 0) { printf("%s\n", g.vertexCount == 0 ? "true" : "false"); }
}
return 0;
}
Todas as lições de Grafos - Série de Estruturas de Dados #9
2Projeto de Grafo
Classe GrafoAdicionar VérticeAdicionar ArestaPossui ArestaObter VizinhosRemover ArestaTamanho