Menu
Coddy logo textTech

הוספת קשת

שיעור 5 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.

קשת מחברת בין שני קודקודים. מכיוון שהגרף שלנו לא מכוון, החיבור הוא דו־כיווני: אם u ו־v מחוברים, אז u מופיע ברשימת השכנים של v וגם v מופיע ברשימת השכנים של u.

לפני שמחברים משהו, יש לוודא ששני הקודקודים קיימים באמצעות קריאה ל־addVertex עבור כל אחד מהם (הפעולה לא עושה כלום אם הם כבר קיימים). לאחר מכן מוסיפים כל אחד מהם לרשימת השכנים של האחר. אם הקשת כבר קיימת, אין להוסיף כפילות. עבור לולאה עצמית (u == v), מוסיפים אותה פעם אחת בלבד.

עכשיו נכתוב את הקוד.

challenge icon

אתגר

קל

הוסף מתודה addEdge למחלקה Graph.

היא מקבלת שני מספרים שלמים u ו-v ומחברת ביניהם בשני הכיוונים:

  • ודא שגם u וגם v קיימים (השתמש ב-addVertex אם לא).
  • הוסף את v לרשימת השכנים של u (רק אם הוא עדיין לא נמצא בה).
  • הוסף את u לרשימת השכנים של v (רק אם הוא עדיין לא נמצא בה). אם u == v, אל תוסיף אותו פעם נוספת.

נסו בעצמכם

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

כל השיעורים ביחידה גרפים – סדרת מבני נתונים מס' 9

תרגלו בעצמכם: קומפיילר C אונליין