Menu
CoddyTech
Bắt đầu học

Lấy các đỉnh kề

Bài học 7 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.

Các thuật toán như BFS, DFS và tìm đường đi ngắn nhất không xem bản đồ thô: chúng hỏi “các đỉnh kề với đỉnh này là gì?” rồi duyệt qua câu trả lời. Phương thức getNeighbors của chúng ta cung cấp thông tin đó.

Nếu đỉnh có trong đồ thị, hãy trả về danh sách đỉnh kề của nó. Bạn có thể trả về một bản sao để bên gọi sửa đổi kết quả mà không làm hỏng đồ thị (đây là một thói quen tốt). Nếu đỉnh không tồn tại, hãy trả về một danh sách rỗng thay vì gây lỗi. Nhờ vậy, code phía gọi sẽ đơn giản: nó luôn có thể duyệt qua kết quả.

challenge icon

Thử thách

Dễ

Thêm phương thức getNeighbors vào lớp Graph.

Phương thức này nhận một số nguyên key và trả về danh sách các đỉnh kề:

  • Nếu key có trong vertices, hãy trả về danh sách các đỉnh kề của nó (có thể trả về bản sao).
  • Nếu key không có trong đồ thị, hãy trả về một danh sách rỗ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"); }
        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");
            }
        }
    }
    return 0;
}

Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9

1Giới thiệu

Giới thiệuĐồ thị là gì?

2Dự án đồ thị

Lớp đồ thịThêm đỉnhThêm cạnhCó cạnhLấy các đỉnh kềXóa cạnhKích thước

3Thử thách luyện tập

BFSDFSĐường đi ngắn nhấtĐếm thành phần liên thôngCó phải đồ thị hai phía không

Tự luyện tập: Trình biên dịch C online