Supprimer une arête

Leçon 8 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.

La suppression d'une arête est l'opération inverse de son ajout : puisque la connexion est stockée dans les deux sens, nous devons annuler les deux côtés. Retirez v de la liste des voisins de u, et retirez u de celle de v.

Faites attention aux cas limites. Si u ou v n'est pas du tout dans le graphe, ou si l'arête n'a jamais été ajoutée, la méthode ne doit rien faire. Nous supprimons l'arête, pas les sommets : les sommets eux-mêmes restent dans le graphe (avec toutes les autres arêtes qu'ils possèdent encore).

Défi

Facile

Ajoutez une méthode removeEdge à la classe Graph.

Elle prend deux entiers u et v et supprime l'arête entre eux :

Si u est dans vertices, supprimez v de sa liste de voisins.
Si v est dans vertices, supprimez u de sa liste de voisins.
Si un sommet ou l'arête n'existe pas, ne faites rien. Les sommets eux-mêmes restent dans le graphe.

Essayez vous-même

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

Toutes les leçons de Graphes - Série Structures de données n°9

1Introduction

Introduction Qu'est-ce qu'un Graphe ?

2Projet Graphe

Classe Graphe Ajouter un sommet Ajouter une arête Possède une arête Obtenir les voisinsSupprimer une arêteTaille

3Défis d'entraînement

BFS DFS Plus court chemin Compter les composantes connexes Est biparti