Obtener Vecinos

Lección 7 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.

Algoritmos como BFS, DFS y el camino más corto no miran el mapa en bruto: preguntan "¿cuáles son los vecinos de este vértice?" y recorren la respuesta. Nuestro método getNeighbors expone eso.

Si el vértice está en el grafo, devuelve su lista de vecinos. Devuelve una copia si quieres que quienes llaman al método muten el resultado sin romper el grafo (este es un buen hábito). Si el vértice no existe, devuelve una lista vacía en lugar de fallar. Eso mantiene el código del cliente simple: siempre puede iterar el resultado.

Desafío

Fácil

Agrega un método getNeighbors a la clase Graph.

Este recibe un entero key y devuelve una lista de sus vecinos:

Si key está en vertices, devuelve su lista de vecinos (una copia está bien).
Si key no está en el grafo, devuelve una lista vacía.

Pruébalo tú mismo

#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;
}

Todas las lecciones de Grafos - Serie de Estructuras de Datos #9

1Introducción

Introducción ¿Qué es un grafo?

2Proyecto de Grafos

Clase Grafo Agregar Vértice Agregar Arista Tiene AristaObtener VecinosEliminar Arista Tamaño

3Desafíos de práctica

BFS DFS Camino más corto Contar componentes conexas Es bipartito