Apakah Bipartit
Pelajaran 14 dari 14 dalam kursus Graf, Seri Struktur Data #9 di Coddy.
Sebuah graf disebut bipartit jika kamu bisa membagi simpulnya menjadi dua kelompok sehingga setiap sisi menghubungkan sebuah simpul di satu kelompok dengan simpul di kelompok lainnya. Bayangkan warna merah dan biru: setiap sisi memiliki satu ujung merah dan satu ujung biru.
BFS memberikan cara pengujian yang jelas. Mulai dari simpul mana pun, beri warna merah, lalu telusuri ke luar. Setiap tetangga baru mendapat warna yang berlawanan dengan warna simpul asalnya. Jika kita menemukan sisi yang menghubungkan dua simpul dengan warna sama, graf tersebut bukan bipartit. Contoh klasiknya adalah siklus dengan panjang ganjil: segitiga 0-1-2-0 memaksa simpul 0 menjadi merah sekaligus biru.
Satu hal yang perlu diingat: jika graf memiliki beberapa komponen terhubung, kamu harus memulai pewarnaan 2 warna yang baru pada setiap komponen. Pola paling mudah adalah melakukan satu perulangan pada semua simpul, lalu memulai BFS setiap kali menemukan simpul yang belum diwarnai.
Tantangan
MudahTulis fungsi isBipartite yang menerima array int 2D adjacency dan array int vertices, lalu mengembalikan true jika graf tersebut bipartit, dan false jika tidak.
Buat grafnya, tambahkan setiap vertex dengan addVertex, lalu setiap edge dengan addEdge. Kemudian lakukan pewarnaan 2 warna dengan BFS pada setiap komponen terhubung: tetapkan warna 0 pada titik awal, lalu beri setiap tetangga warna 1 - color[u]. Jika kamu menemukan edge yang kedua ujungnya sudah memiliki warna yang sama, kembalikan false. Jika tidak, kembalikan true.
Kamu harus menggunakan class Graph yang disediakan di graph. Jangan gunakan bawaan bahasa (maps, sets) untuk merepresentasikan adjacency. Data tambahan untuk algoritma, seperti peta warna dan antrean, boleh menggunakan tipe dari stdlib.
Coba sendiri
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}
Semua pelajaran di Graf, Seri Struktur Data #9
Latihan sendiri: Compiler C online