C++ Boost Graph Connected Components

MUAZHAN

4 min read

·

Jul 01, 2024

36

Share

Menemukan Komponen Terhubung dalam Graf dengan Boost Graph Library di C++

Boost Graph Library (BGL) adalah pustaka C++ yang kuat untuk bekerja dengan graf. Salah satu fitur utamanya adalah kemampuan untuk menemukan komponen terhubung dalam graf. Komponen terhubung adalah himpunan simpul dalam graf yang saling terhubung satu sama lain melalui jalur.

Berikut adalah contoh bagaimana menemukan komponen terhubung dalam graf yang tidak berarah menggunakan BGL:

#include 
#include 
#include 
#include 

using namespace std;
using namespace boost;

int main() {
  // Deklarasikan graf menggunakan adjacency_list
  typedef adjacency_list Graph;
  Graph g;

  // Tambahkan simpul ke graf
  add_vertex(g);
  add_vertex(g);
  add_vertex(g);
  add_vertex(g);
  add_vertex(g);

  // Tambahkan edge ke graf
  add_edge(0, 1, g);
  add_edge(1, 2, g);
  add_edge(2, 3, g);
  add_edge(4, 4, g);

  // Deklarasikan vektor untuk menyimpan komponen terhubung
  vector component(num_vertices(g));

  // Temukan komponen terhubung
  connected_components(g, &component[0]);

  // Cetak komponen terhubung
  cout << "Komponen Terhubung:\n";
  for (int i = 0; i < num_vertices(g); ++i) {
    cout << "Simpul " << i << " berada di komponen " << component[i] << endl;
  }

  return 0;
}

Penjelasan Kode:

1. Deklarasikan Graf:
   • Kode menggunakan adjacency_list untuk membuat graf tidak berarah.
2. Tambahkan Simpul dan Edge:
   • Kode menambahkan 5 simpul ke graf dan menghubungkannya dengan edge.
3. Deklarasikan Vektor Komponen:
   • Sebuah vektor component dideklarasikan untuk menyimpan informasi tentang komponen terhubung. Ukurannya sama dengan jumlah simpul dalam graf.
4. Temukan Komponen Terhubung:
   • Fungsi connected_components digunakan untuk menemukan komponen terhubung dalam graf. Fungsi ini mengambil graf sebagai argumen dan sebuah pointer ke array integer sebagai argumen kedua. Array integer akan diisi dengan indeks komponen terhubung untuk setiap simpul.
5. Cetak Komponen Terhubung:
   • Kode mengulang melalui semua simpul dalam graf dan mencetak simpul dan indeks komponen terhubungnya.

Output:

Komponen Terhubung:
Simpul 0 berada di komponen 0
Simpul 1 berada di komponen 0
Simpul 2 berada di komponen 0
Simpul 3 berada di komponen 0
Simpul 4 berada di komponen 1

Kode ini menunjukkan bahwa graf memiliki dua komponen terhubung. Simpul 0, 1, 2, dan 3 termasuk dalam komponen terhubung pertama, sedangkan simpul 4 termasuk dalam komponen terhubung kedua.

Kesimpulan:

BGL menyediakan cara yang mudah dan efektif untuk menemukan komponen terhubung dalam graf. Ini sangat berguna dalam berbagai aplikasi, seperti analisis jaringan, pengolahan gambar, dan pemodelan data.