Dapatkan Tetangga

Pelajaran 7 dari 14 dalam kursus Graf, Seri Struktur Data #9 di Coddy.

Algoritma seperti BFS, DFS, dan jalur terpendek tidak melihat peta mentah: algoritma tersebut bertanya "apa saja tetangga vertex ini?" lalu menelusuri jawabannya. getNeighbors method kita menyediakan informasi itu.

Jika vertex ada di graph, kembalikan list tetangganya. Kembalikan salinan jika kamu ingin pemanggil mengubah hasilnya tanpa merusak graph (ini kebiasaan yang baik). Jika vertex tidak ada, kembalikan list kosong daripada membuat program crash. Dengan begitu, kode client tetap sederhana: kode tersebut bisa selalu mengiterasi hasilnya.

Tantangan

Mudah

Tambahkan method getNeighbors ke dalam class Graph.

Method ini menerima bilangan bulat key dan mengembalikan list tetangganya:

Jika key ada di dalam vertices, kembalikan list tetangganya. Salinannya boleh digunakan.
Jika key tidak ada di dalam graph, kembalikan list kosong.

Coba sendiri

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

Semua pelajaran di Graf, Seri Struktur Data #9

1Pengenalan

Pengenalan Apa Itu Graph?

2Proyek Graf

Class Graf Tambahkan Simpul Tambahkan Sisi Apakah Ada SisiDapatkan TetanggaHapus Sisi Ukuran

3Tantangan Latihan

BFS DFS Jalur Terpendek Hitung Komponen Terhubung Apakah Bipartit

Latihan sendiri: Compiler C online