Hapus Sisi

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

Menghapus sebuah sisi adalah kebalikan dari menambahkan sisi: karena koneksi disimpan dalam kedua arah, kita harus membatalkan kedua sisi. Hapus v dari daftar tetangga u, dan hapus u dari daftar tetangga v.

Perhatikan kasus-kasus khusus. Jika u atau v sama sekali tidak ada dalam graf, atau jika sisinya belum pernah ditambahkan, method harus diam-diam tidak melakukan apa pun. Kita menghapus sisi, bukan simpul: simpul-simpul itu sendiri tetap berada dalam graf (beserta sisi lain yang masih dimilikinya).

Tantangan

Mudah

Tambahkan method removeEdge ke class Graph.

Method ini menerima dua bilangan bulat u dan v, lalu menghapus edge di antara keduanya:

Jika u ada di vertices, hapus v dari daftar tetangganya.
Jika v ada di vertices, hapus u dari daftar tetangganya.
Jika vertex atau edge tidak ada, jangan lakukan apa pun. Vertex tetap ada di graph.

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

Semua pelajaran di Graf, Seri Struktur Data #9

1Pengenalan

Pengenalan Apa Itu Graph?

2Proyek Graf

Class Graf Tambahkan Simpul Tambahkan Sisi Apakah Ada Sisi Dapatkan TetanggaHapus SisiUkuran

3Tantangan Latihan

BFS DFS Jalur Terpendek Hitung Komponen Terhubung Apakah Bipartit

Latihan sendiri: Compiler C online