Usuwanie krawędzi

Lekcja 8 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.

Usuwanie krawędzi jest odwrotnością jej dodawania: ponieważ połączenie jest przechowywane w obu kierunkach, musimy usunąć je z obu stron. Usuń v z listy sąsiadów u i usuń u z listy sąsiadów v.

Zwróć uwagę na sytuacje brzegowe. Jeśli u lub v w ogóle nie występuje w grafie albo krawędź nigdy nie została dodana, metoda powinna po prostu nic nie robić. Usuwamy krawędź, a nie wierzchołki: same wierzchołki pozostają w grafie (wraz z innymi krawędziami, które nadal mają).

Wyzwanie

Łatwy

Dodaj metodę removeEdge do klasy Graph.

Przyjmuje dwie liczby całkowite u i v i usuwa krawędź między nimi:

Jeśli u znajduje się w vertices, usuń v z listy jego sąsiadów.
Jeśli v znajduje się w vertices, usuń u z listy jego sąsiadów.
Jeśli wierzchołek lub krawędź nie istnieje, nic nie rób. Same wierzchołki pozostają w grafie.

Spróbuj swoich sił

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

Wszystkie lekcje w sekcji Grafy – struktury danych, seria nr 9

1Wprowadzenie

Wprowadzenie Czym jest graf?

2Projekt grafu

Klasa grafu Dodawanie wierzchołka Dodawanie krawędzi Czy istnieje krawędź Pobieranie sąsiadówUsuwanie krawędziRozmiar

3Wyzwania praktyczne

BFS DFS Najkrótsza ścieżka Policz spójne składowe Czy jest dwudzielny?

Poćwicz samodzielnie: Kompilator C online