Path Pada Dua Vertex Pada Directed Graph

9 views

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

Sebelumnya aku akan jelaskan apakah itu directed graph. Directed graph ialah sebuah grafik atau kumpulan dari titik yang saling terhubung melalui jalur-jalur dimana sebuah jalur-jalur penghubung tersebut memiliki 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 memiliki jalur ataukah tidak.

Berikut ini akan aku berikan contoh dari directed graph:

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 sanggup 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 kalau tidak return false.

Oke pribadi saja berikut aku akan membagikan C++ code memakai BFS dalam pengecekan jalur pada dua titik.

#include <iostream>#include <list>using namespace std;// class untuk directed graphclass Graph{int P; // Banyaknya titiklist<int> *adj; // List pointer untuk titik bersebranganpublic:  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 pencarianbool Graph::isReachable(int s, int d){// Base Caseif(s == d) return true;// Tandai semua titik sebagai belum dikunjungibool *visited = new bool[P];for (int i=0; i< P; i++) visited[i] = false; // Queue temporarylist<int> queue;// tandai titik awal sebagai telah dikunjungivisited[s] = true;queue.push_back(s);// Digunakan untuk mendapat jalur pada semua titik yang bersinggunganlist<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 Jalurif(*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";elsecout << "\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";elsecout << "\n Tidak ada jalan  dari " << u << " ke " << v << "\n"; return 0;}

 

Dari kegiatan diatas akan keluar output berupa:

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

Sekian terima kasih silakan komentar kalau terdapat pertanyaan.

Author: 
    author
    No related post!