Có cạnh
Bài học 6 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Câu hỏi đơn giản nhất để đặt ra về một đồ thị là: “hai đỉnh này có nối với nhau không?”. Với danh sách kề, câu trả lời cần một lần tra cứu trong từ điển và một lượt quét danh sách: tra cứu các đỉnh kề với u rồi kiểm tra xem v có nằm trong danh sách đó không.
Nếu u thậm chí không có trong đồ thị thì không có danh sách nào để quét, vậy hãy trả về false. Vì addEdge đã nối cạnh theo cả hai hướng, bạn chỉ cần kiểm tra một phía: nếu v nằm trong danh sách các đỉnh kề với u thì theo cách xây dựng này, u cũng nằm trong danh sách các đỉnh kề với v.
Giờ hãy viết hàm.
Thử thách
DễThêm phương thức hasEdge vào lớp Graph.
Phương thức này nhận hai số nguyên u và v, rồi trả về true nếu có cạnh nối chúng, nếu không thì trả về false.
Nếu u không có trong vertices, hãy trả về false. Nếu có, hãy trả về kết quả cho biết v có trong danh sách các đỉnh kề của u hay không.
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"); }
}
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