C++ Boost Graph

Membuat Graf Tak Berarah C++ Boost dan Menelusurinya dalam Urutan Depth First Search

Teori graf adalah area kunci dalam ilmu komputer dan pemrograman, dan salah satu perpustakaan yang paling umum digunakan untuk mengimplementasikan algoritma graf di C++ adalah Boost. Dalam posting blog ini, kita akan menghadapi tantangan membuat graf tak berarah menggunakan perpustakaan Boost dan kemudian menelusurinya dengan metode Depth First Search (DFS).

Pengenalan Masalah

Membuat dan bekerja dengan graf bisa menakutkan, tetapi dengan Boost, itu menjadi jauh lebih sederhana. Depth First Search (DFS) adalah algoritma dasar yang digunakan untuk mengeksplorasi simpul dan tepi dari sebuah graf. Baik Anda mencari jalur, memeriksa konektivitas, atau memecahkan teka-teki, DFS adalah cara yang efisien untuk bernavigasi melalui graf.

Dalam pos ini, kita akan menjelajahi contoh konkret penyiapan graf tak berarah dan mengimplementasikan penelusuran DFS.

Ikhtisar Solusi

Kami akan mencakup langkah-langkah berikut:

  1. Sertakan header Boost yang diperlukan.
  2. Tentukan struktur graf.
  3. Buat kelas pengunjung untuk menangani penemuan simpul.
  4. Siapkan fungsi utama untuk membangun graf dan melakukan DFS.

Langkah 1: Sertakan Header Boost yang Diperlukan

Pertama dan yang utama, Anda perlu menyertakan header Graf Boost, yang menyediakan kelas dan fungsi dasar untuk operasi terkait graf.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

Langkah 2: Tentukan Struktur Graf

Kami mendefinisikan graf tak berarah kami menggunakan boost::adjacency_list. Berikut cara mendefinisikannya:

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> MyGraph;
typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;
  • Dalam kode di atas:
    • listS menunjukkan bahwa graf akan menggunakan daftar tepi.
    • vecS berarti kita akan menggunakan vektor untuk menyimpan simpul.
    • undirectedS menetapkan bahwa graf tersebut tak berarah.

Langkah 3: Buat Kelas Pengunjung

Kelas pengunjung sangat penting untuk mendefinisikan apa yang terjadi ketika sebuah simpul ditemukan selama DFS. Berikut adalah contoh kelas pengunjung sederhana:

class MyVisitor : public boost::default_dfs_visitor {
public:
  void discover_vertex(MyVertex v, const MyGraph& g) const {
    std::cerr << v << std::endl; // Cetak nomor simpul
    return;
  }
};

Langkah 4: Siapkan Fungsi Utama

Akhirnya, kita perlu membuat graf, menambahkan tepi, dan memanggil algoritma DFS.

int main() {
  MyGraph g;
  boost::add_edge(0, 1, g); // Hubungkan simpul 0 dan 1
  boost::add_edge(0, 2, g); // Hubungkan simpul 0 dan 2
  boost::add_edge(1, 2, g); // Hubungkan simpul 1 dan 2
  boost::add_edge(1, 3, g); // Hubungkan simpul 1 dan 3

  MyVisitor vis;
  boost::depth_first_search(g, boost::visitor(vis)); // Lakukan penelusuran DFS

  return 0;
}

Penjelasan Kode

  • Membuat Graf: Kita membuat sebuah instansi MyGraph yang disebut g. Kemudian kita menambahkan tepi yang menentukan koneksi antara simpul.
  • Menjalankan DFS: Dengan membuat instansi MyVisitor, kita mengirimkannya sebagai pengunjung ke depth_first_search, yang menelusuri graf dan memanggil discover_vertex untuk setiap simpul.

Kesimpulan

Menggunakan perpustakaan Boost untuk membuat dan menelusuri graf dapat secara signifikan menyederhanakan tugas-tugas kompleks di C++. Dengan mengikuti langkah-langkah yang dijelaskan di atas, Anda dapat berhasil menerapkan Depth First Search (DFS) pada graf tak berarah.

Aplikasi praktis dari graf sangat luas, dan memahami DFS sangat penting bagi siapa saja yang ingin menyelami lebih dalam algoritma graf. Eksperimenlah dengan kode ini dan modifikasi struktur graf agar sesuai dengan kebutuhan Anda!