Boyut
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 9 / 14.
Graph'ın ihtiyaç duyduğu son şey, bize kaç tane köşeye sahip olduğunu söyleyen hızlı bir yoldur. vertices, köşe anahtarı ile anahtarlanmış bir map olduğundan, cevap sadece bu map'in boyutudur.
Bunun kenarları değil, köşeleri saydığına dikkat edin. Boş bir graph üzerinde addEdge(1, 2) çağırmak iki köşe ve bir kenar ekler, bu nedenle boyut 2 olur. Kenarı daha sonra kaldırmak boyutu değiştirmez: köşeler açıkça kaldırılana kadar kalırlar.
Görev
KolayGraph sınıfına bir size metodu ekleyin.
Bu metod girdi almaz ve grafikte şu anda bulunan köşe sayısını (vertices içindeki girdi sayısını) döndürür.
Kendin dene
#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);
}
}
if (strcmp(cmd, "hasEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) printf("%s\n", Graph_hasEdge(&g, atoi(a1), atoi(a2)) ? "true" : "false"); }
if (strcmp(cmd, "neighbors") == 0) {
char* arg = strtok(NULL, " \t");
if (arg) {
int buf[MAX_NEIGHBORS];
int n = Graph_getNeighbors(&g, atoi(arg), buf);
qsort(buf, n, sizeof(int), _cmp_int);
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", buf[i]);
}
printf("\n");
}
}
if (strcmp(cmd, "removeEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_removeEdge(&g, atoi(a1), atoi(a2)); }
if (strcmp(cmd, "size") == 0) { printf("%d\n", Graph_size(&g)); }
}
return 0;
}