הוספת קשת
שיעור 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
תרגלו בעצמכם: קומפיילר C אונליין