Ottenere i vicini

Lezione 7 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.

Algoritmi come BFS, DFS e il percorso più breve non esaminano la mappa grezza: chiedono «quali sono i vicini di questo vertice?» e percorrono la risposta. Il nostro metodo getNeighbors rende disponibili queste informazioni.

Se il vertice è nel grafo, restituisci il suo elenco di vicini. Restituisci una copia se vuoi che chi chiama possa modificare il risultato senza danneggiare il grafo (è una buona abitudine). Se il vertice non esiste, restituisci un elenco vuoto invece di causare un errore. In questo modo il codice client resta semplice: può sempre iterare sul risultato.

Sfida

Facile

Aggiungi un metodo getNeighbors alla classe Graph.

Accetta un intero key e restituisce un elenco dei suoi vicini:

Se key è in vertices, restituisci il suo elenco di vicini (va bene anche una copia).
Se key non è nel grafo, restituisci un elenco vuoto.

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)); }
        if (strcmp(cmd, "addEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_addEdge(&g, atoi(a1), atoi(a2)); }
        if (strcmp(cmd, "degree") == 0) {
            char* arg = strtok(NULL, " \t");
            if (arg) {
                int k = atoi(arg);
                int ki = Graph_indexOf(&g, k);
                printf("%d\n", ki == -1 ? 0 : g.vertices[ki].n);
            }
        }
        if (strcmp(cmd, "hasEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) printf("%s\n", Graph_hasEdge(&g, atoi(a1), atoi(a2)) ? "true" : "false"); }
        if (strcmp(cmd, "neighbors") == 0) {
            char* arg = strtok(NULL, " \t");
            if (arg) {
                int buf[MAX_NEIGHBORS];
                int n = Graph_getNeighbors(&g, atoi(arg), buf);
                qsort(buf, n, sizeof(int), _cmp_int);
                for (int i = 0; i < n; i++) {
                    if (i > 0) printf(" ");
                    printf("%d", buf[i]);
                }
                printf("\n");
            }
        }
    }
    return 0;
}

Tutte le lezioni di Grafi - Serie sulle strutture dati #9

1Introduzione

Introduzione Che cos'è un grafo?

2Progetto sui grafi

Classe Graph Aggiungere un vertice Aggiungere un arco Verificare la presenza di un arcoOttenere i viciniRimuovere un arco Dimensione

3Sfide pratiche

BFS DFS Percorso più breve Conta le componenti connesse Verifica se è bipartito

Esercitati da solo: Compilatore C online