Thêm cạnh

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

Một cạnh nối hai đỉnh. Vì đồ thị của chúng ta là vô hướng, kết nối đi theo cả hai chiều: nếu u và v được nối với nhau, thì u xuất hiện trong danh sách láng giềng của v và v xuất hiện trong danh sách của u.

Trước khi thêm cạnh, hãy gọi addVertex cho từng đỉnh để đảm bảo cả hai đều tồn tại. Hàm này không làm gì nếu đỉnh đã tồn tại. Sau đó, thêm mỗi đỉnh vào danh sách láng giềng của đỉnh kia. Bỏ qua thao tác thêm trùng nếu cạnh đã có. Với cạnh khuyên (u == v), chỉ thêm một lần.

Giờ hãy viết đoạn code này.

Thử thách

Dễ

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

Phương thức nhận hai số nguyên u và v, rồi kết nối chúng theo cả hai hướng:

Đảm bảo cả u và v đều tồn tại. Nếu chưa có, hãy dùng addVertex.
Thêm v vào danh sách láng giềng của u, chỉ khi v chưa có trong danh sách.
Thêm u vào danh sách láng giềng của v, chỉ khi u chưa có trong danh sách. Nếu u == v, không thêm lần thứ hai.

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);
            }
        }
    }
    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ạnh Lấy các đỉnh kề Xóa cạnh Kích thước

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

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

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