Agregar Arista

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

Una arista conecta dos vértices. Dado que nuestro grafo es no dirigido, la conexión va en ambos sentidos: si u y v están conectados, entonces u aparece en la lista de vecinos de v y v aparece en la de u.

Antes de conectar nada, asegúrate de que ambos vértices existan llamando a addVertex en cada uno (es una operación nula si ya existen). Luego, añade cada uno a la lista de vecinos del otro. Omite una inserción duplicada si la arista ya está allí. Para un bucle sobre sí mismo (u == v), añádelo solo una vez.

Ahora vamos a escribirlo.

Desafío

Fácil

Agrega un método addEdge a la clase Graph.

Este toma dos enteros u y v y los conecta en ambas direcciones:

Asegúrate de que tanto u como v existan (usa addVertex si no es así).
Agrega v a la lista de vecinos de u (solo si aún no está allí).
Agrega u a la lista de vecinos de v (solo si aún no está allí). Si u == v, no lo agregues una segunda vez.

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);
            }
        }
    }
    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érticeAgregar AristaTiene Arista Obtener Vecinos Eliminar Arista Tamaño

3Desafíos de práctica

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