Menu
CoddyTech
Bắt đầu học

Xóa cạnh

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

Xóa một cạnh là thao tác ngược lại với thêm một cạnh: vì kết nối được lưu theo cả hai hướng, ta phải xóa nó ở cả hai phía. Xóa v khỏi danh sách láng giềng của u, rồi xóa u khỏi danh sách láng giềng của v.

Hãy cẩn thận với các trường hợp biên. Nếu u hoặc v không có trong đồ thị, hoặc cạnh đó chưa từng được thêm, phương thức nên không làm gì và không báo lỗi. Ta đang xóa cạnh, không phải các đỉnh: bản thân các đỉnh vẫn ở trong đồ thị (cùng với những cạnh khác mà chúng còn có).

challenge icon

Thử thách

Dễ

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

Phương thức nhận hai số nguyên u và v, rồi xóa cạnh nối chúng:

  • Nếu u có trong vertices, hãy xóa v khỏi danh sách láng giềng của nó.
  • Nếu v có trong vertices, hãy xóa u khỏi danh sách láng giềng của nó.
  • Nếu đỉnh hoặc cạnh không tồn tại, không làm gì cả. Các đỉnh vẫn nằm trong đồ thị.

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)); }
    }
    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