Dodawanie krawędzi

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

Krawędź łączy dwa wierzchołki. Ponieważ nasz graf jest nieskierowany, połączenie działa w obie strony: jeśli u i v są połączone, to u pojawia się na liście sąsiadów v i v pojawia się na liście sąsiadów u.

Zanim cokolwiek połączysz, upewnij się, że oba wierzchołki istnieją, wywołując dla każdego z nich addVertex (jeśli już istnieją, nic się nie stanie). Następnie dodaj każdy z nich do listy sąsiadów drugiego. Pomiń dodawanie duplikatu, jeśli krawędź już istnieje. W przypadku pętli własnej (u == v) dodaj ją tylko raz.

Teraz napiszmy kod.

Wyzwanie

Łatwy

Dodaj metodę addEdge do klasy Graph.

Przyjmuje dwie liczby całkowite u i v oraz łączy je w obu kierunkach:

Upewnij się, że zarówno u, jak i v istnieją (jeśli nie, użyj addVertex).
Dodaj v do listy sąsiadów u (tylko jeśli jeszcze go tam nie ma).
Dodaj u do listy sąsiadów v (tylko jeśli jeszcze go tam nie ma). Jeśli u == v, nie dodawaj go ponownie.

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);
            }
        }
    }
    return 0;
}

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

1Wprowadzenie

Wprowadzenie Czym jest graf?

2Projekt grafu

Klasa grafu Dodawanie wierzchołkaDodawanie krawędziCzy istnieje krawędź Pobieranie sąsiadów Usuwanie krawędzi Rozmiar

3Wyzwania praktyczne

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

Poćwicz samodzielnie: Kompilator C online