Eliminar Arista

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

Eliminar una arista es el reflejo de añadir una: ya que la conexión se almacena en ambas direcciones, tenemos que deshacer ambos lados. Saca v de la lista de vecinos de u, y saca u de la de v.

Ten cuidado con los casos extremos. Si u o v no están en el grafo en absoluto, o si la arista nunca fue añadida, el método no debería hacer nada silenciosamente. Estamos eliminando la arista, no los vértices: los vértices mismos permanecen en el grafo (con cualquier otra arista que aún tengan).

Desafío

Fácil

Agrega un método removeEdge a la clase Graph.

Este recibe dos enteros u y v y elimina la arista entre ellos:

Si u está en vertices, elimina v de su lista de vecinos.
Si v está en vertices, elimina u de su lista de vecinos.
Si un vértice o la arista no existen, no hagas nada. Los vértices en sí permanecen en el grafo.

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");
            }
        }
        if (strcmp(cmd, "removeEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_removeEdge(&g, atoi(a1), atoi(a2)); }
    }
    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 Arista Obtener VecinosEliminar AristaTamaño

3Desafíos de práctica

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