Menu
Coddy logo textTech
flag Ar iconالعربيةdown icon

إضافة حافة (Edge)

الدرس 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