إضافة حافة (Edge)
الدرس 5 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
تربط الحافة بين رأسين. بما أن الرسم البياني الخاص بنا غير موجه، فإن الاتصال يسير في كلا الاتجاهين: إذا كان u و v متصلين، فإن u يظهر في قائمة جيران v و v يظهر في قائمة جيران u.
قبل توصيل أي شيء، تأكد من وجود كلا الرأسين من خلال استدعاء addVertex لكل منهما (وهي عملية لا تفعل شيئاً إذا كانا موجودين بالفعل). ثم قم بإضافة كل منهما إلى قائمة جيران الآخر. تخطَّ الإضافة المتكررة إذا كانت الحافة موجودة بالفعل. بالنسبة للحلقة الذاتية (u == v)، أضفها مرة واحدة فقط.
الآن دعونا نكتبها.
التحدي
سهلأضف طريقة 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
2مشروع الـ Graph
فئة الـ Graphإضافة رأس (Vertex)إضافة حافة (Edge)هل توجد حافةالحصول على الجيرانحذف حافةالحجم