Tambahkan Sisi

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

Sebuah sisi menghubungkan dua simpul. Karena graf kita tidak berarah, hubungan berjalan dua arah: jika u dan v terhubung, maka u muncul dalam daftar tetangga v dan v muncul dalam daftar tetangga u.

Sebelum menghubungkan apa pun, pastikan kedua simpul ada dengan memanggil addVertex pada masing-masing simpul (tidak melakukan apa pun jika simpul tersebut sudah ada). Lalu tambahkan masing-masing simpul ke daftar tetangga simpul lainnya. Lewati penambahan duplikat jika sisi tersebut sudah ada. Untuk self-loop (u == v), tambahkan hanya sekali.

Sekarang mari kita tulis.

Tantangan

Mudah

Tambahkan method addEdge ke class Graph.

Method ini menerima dua bilangan bulat u dan v, lalu menghubungkan keduanya dalam kedua arah:

Pastikan u dan v ada, gunakan addVertex jika belum ada.
Tambahkan v ke list tetangga u, hanya jika belum ada di sana.
Tambahkan u ke list tetangga v, hanya jika belum ada di sana. Jika u == v, jangan tambahkan untuk kedua kalinya.

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

Semua pelajaran di Graf, Seri Struktur Data #9

1Pengenalan

Pengenalan Apa Itu Graph?

2Proyek Graf

Class Graf Tambahkan SimpulTambahkan SisiApakah Ada Sisi Dapatkan Tetangga Hapus Sisi Ukuran

3Tantangan Latihan

BFS DFS Jalur Terpendek Hitung Komponen Terhubung Apakah Bipartit

Latihan sendiri: Compiler C online