Kích thước
Bài học 9 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Điều cuối cùng Graph cần là một cách nhanh để cho biết nó có bao nhiêu đỉnh. Vì vertices là một ánh xạ có khóa là khóa của đỉnh, nên câu trả lời chính là kích thước của ánh xạ đó.
Lưu ý rằng cách này đếm đỉnh, không phải cạnh. Gọi addEdge(1, 2) trên một đồ thị trống sẽ thêm hai đỉnh và một cạnh, nên kích thước tăng lên 2. Xóa cạnh sau đó không làm thay đổi kích thước: các đỉnh vẫn còn cho đến khi được xóa rõ ràng.
Thử thách
DễThêm phương thức size vào lớp Graph.
Phương thức này không nhận đầu vào và trả về số đỉnh hiện có trong đồ thị (số mục trong vertices).
Tự làm thử
#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;
}
Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9
Tự luyện tập: Trình biên dịch C online