Aggiungere un vertice
Lezione 4 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
Un vertice è un singolo punto nel grafo. Aggiungerne uno significa registrare la sua chiave nella mappa vertices con un elenco di vicini vuoto: esiste, ma non ha ancora collegamenti.
Se la chiave è già nella mappa, non fare nulla. Non vogliamo cancellare i vicini esistenti di un vertice solo perché qualcuno ha chiamato addVertex due volte. Questo tipo di comportamento idempotente rende il metodo sicuro da chiamare in seguito da addEdge.
Scriviamolo.
Sfida
FacileAggiungi un metodo addVertex alla classe Graph.
Accetta un intero key e:
- Se
keynon è invertices, aggiungilo con una lista di vicini vuota. - Se
keyè già invertices, non fare nulla.
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"); }
if (strcmp(cmd, "hasVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Graph_indexOf(&g, atoi(arg)) != -1 ? "true" : "false"); }
if (strcmp(cmd, "addVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Graph_addVertex(&g, atoi(arg)); }
}
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