Ajouter une arête

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

Une arête connecte deux sommets. Puisque notre graphe est non orienté, la connexion va dans les deux sens : si u and v sont connectés, alors u apparaît dans la liste des voisins de v et v apparaît dans celle de u.

Avant de relier quoi que ce soit, assurez-vous que les deux sommets existent en appelant addVertex sur chacun d'eux (c'est une opération sans effet s'ils existent déjà). Ensuite, ajoutez (push) chacun d'eux dans la liste des voisins de l'autre. Ignorez l'ajout s'il s'agit d'un doublon et que l'arête existe déjà. Pour une boucle sur soi-même (u == v), ne l'ajoutez qu'une seule fois.

Maintenant, écrivons-le.

Défi

Facile

Ajoutez une méthode addEdge à la classe Graph.

Elle prend deux entiers u et v et les connecte dans les deux sens :

Assurez-vous que u et v existent tous les deux (utilisez addVertex si ce n'est pas le cas).
Ajoutez v à la liste des voisins de u (uniquement s'il n'y est pas déjà).
Ajoutez u à la liste des voisins de v (uniquement s'il n'y est pas déjà). Si u == v, ne l'ajoutez pas une deuxième fois.

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);
            }
        }
    }
    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 sommetAjouter une arêtePossède une arête Obtenir les voisins Supprimer une arête Taille

3Défis d'entraînement

BFS DFS Plus court chemin Compter les composantes connexes Est biparti