Classe Graph
Lezione 3 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
La classe Graph è costruita attorno a un unico campo, vertices, che è la lista di adiacenza: una mappa da ogni chiave di vertice all’elenco dei suoi vicini. Ogni operazione che aggiungeremo più avanti (aggiungere archi, elencare i vicini, rimuovere archi) è solo una piccola modifica a questa mappa.
Il costruttore inizializza il grafo nello stato vuoto: nessun vertice, nessun arco. Quindi la mappa è semplicemente una mappa vuota. I metodi che aggiungeremo nelle prossime lezioni la faranno crescere.
Sfida
FacileScrivi una classe Graph con un costruttore che non accetta input.
Inizializza un unico campo vertices come mappa vuota (o l’equivalente del tuo linguaggio di una mappa di adiacenza da chiavi a liste).
Provalo tu
#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;
}
Tutte le lezioni di Grafi - Serie sulle strutture dati #9
2Progetto sui grafi
Classe GraphAggiungere un verticeAggiungere un arcoVerificare la presenza di un arcoOttenere i viciniRimuovere un arcoDimensioneEsercitati da solo: Compilatore C online