Lớp đồ thị
Bài học 3 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Lớp Graph xoay quanh một trường duy nhất, vertices, đó là danh sách kề (adjacency list): một ánh xạ từ khóa của mỗi đỉnh đến danh sách các đỉnh kề với nó. Mỗi thao tác chúng ta thêm sau này, như thêm cạnh, liệt kê các đỉnh kề và xóa cạnh, chỉ là một thay đổi nhỏ đối với ánh xạ này.
Hàm khởi tạo bắt đầu đồ thị ở trạng thái rỗng: không có đỉnh nào, cũng không có cạnh nào. Vì vậy, ánh xạ chỉ là một ánh xạ rỗng. Các phương thức chúng ta thêm trong những bài học tiếp theo sẽ làm nó phát triển.
Thử thách
DễViết một lớp Graph có hàm khởi tạo không nhận đầu vào.
Khởi tạo một trường vertices dưới dạng từ điển rỗng (hoặc cấu trúc tương đương trong ngôn ngữ của bạn để ánh xạ khóa tới danh sách kề).
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"); }
}
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