Hello sobat,Tutorial kali ini adalah mencari apakah ada jalur pada 2 vertex pada sebuah directed graph. Sebelumnya saya akan jelaskan apakah itu directed graph. Directed graph adalah sebuah grafik atau kumpulan dari titik yang saling terhubung melalui jalur-jalur dimana sebuah jalur-jalur penghubung ters...

Path pada dua vertex pada Directed graph

Hello sobat,
Tutorial kali ini adalah mencari apakah ada jalur pada 2 vertex pada sebuah directed graph.

Sebelumnya saya akan jelaskan apakah itu directed graph. Directed graph adalah sebuah grafik atau kumpulan dari titik yang saling terhubung melalui jalur-jalur dimana sebuah jalur-jalur penghubung tersebut mempunyai arah.

Baik kita akan masuk ke permasalahannya..
Jika diberikan suatu directed graph dan terdapat titik-titik di dalamnya, kemudian diberikan 2 titik periksa apakah dua titik tersebut mempunyai jalur ataukah tidak.

Berikut ini akan saya berikan contoh dari directed graph:
directed

Dari gambar tersebut terdapat jalur dari titik 4 ke titik 1 dan tidak ada jalur dari titik 1 ke titik 3.

Untuk permasalahan ini kita dapat gunakan metode BFS maupun DFS untuk mencari jalur dari 2 titik. Gunakan titik pertama sebagai titik awal dan titik kedua sebagai tujuan. Jika dalam perjalanan ditemukan titik tujuan maka return true jika tidak return false.

Oke langsung saja berikut saya akan membagikan C++ code menggunakan BFS dalam pengecekan jalur pada dua titik.

#include <iostream>
#include <list>

using namespace std;

// class untuk directed graph
class Graph{
    int P; // Banyaknya titik
    list<int> *adj; // List pointer untuk titik bersebrangan
    public:
      Graph(int P); //Constructor
      void addEdge(int a, int b); // untuk menambahkan jalur pada titik
      bool isReachable(int s, int d); // pencarian jalur
};
Graph::Graph(int P){
    this->P = P;
    adj = new list<int>[P];
}
void Graph::addEdge(int a, int b){
    adj[a].push_back(b);
}

//menggunakan metode BFS dalam pencarian
bool Graph::isReachable(int s, int d){
    // Base Case
    if(s == d)
       return true;
    // Tandai semua titik sebagai belum dikunjungi
    bool *visited = new bool[P];
    for (int i=0; i< P; i++)
       visited[i] = false;

     // Queue temporary
    list<int> queue;
    // tandai titik awal sebagai telah dikunjungi
    visited[s] = true;
    queue.push_back(s);

    // Digunakan untuk mendapatkan jalur pada semua titik yang bersinggungan
    list<int>::iterator i;

    while (!queue.empty())
    {
         s = queue.front();
         queue.pop_front();

         // Dapatkan semua titik berseberangan pada queue s
         // Jika titik belum dikunjungi maka tandai telah dikunjungi
         for(i = adj[s].begin(); i != adj[s].end(); i++)
         {
               //terdapat jalur Jalur 
               if(*i == d) return true;
    
               if(!visited[*i]){
                  visited[*i] = true;
                  queue.push_back(*i);
               }
         }
   }
   // tidak ada jalur
   return false;
}

int main()
{
    Graph g(4);
    g.addEdge(1,1);
    g.addEdge(2,1);
    g.addEdge(3,2);
    g.addEdge(3,4);
    g.addEdge(4,3);
    
    int u = 4, v = 1;
    if(g.isReachable(u,v))
       cout << "\n Ada jalan dari " << u << " ke " << v << "\n";
    else 
       cout << "\n Tidak ada jalan  dari " << u << " ke " << v << "\n";

    u = 1; 
    v = 3;
    if(g.isReachable(u,v))
       cout << "\n Ada jalan dari " << u << " ke " << v << "\n";
    else 
       cout << "\n Tidak ada jalan  dari " << u << " ke " << v << "\n";
 return 0;
}

 

Dari program diatas akan keluar output berupa:

Ada jalan dari 4 ke 1
Tidak ada jalan dari 1 ke 3

Sekian terima kasih silakan komentar jika terdapat pertanyaan.


About Author

(:)

no comment


Comment & Discussions

    Please LOGIN before if you want to give the comment.