นี่คือโปรแกรม C++ สำหรับตรวจสอบว่ามีเส้นทางระหว่าง 2 จุดที่กำหนดหรือไม่
อัลกอริทึม
เริ่มต้น ฟังก์ชัน isReach() เป็นฟังก์ชันแบบเรียกซ้ำ เพื่อตรวจสอบว่า d เข้าถึงได้จาก s หรือไม่: A) ทำเครื่องหมายให้ทุกจุดเป็นยังไม่ได้เยี่ยมชม B) ทำเครื่องหมายจุดปัจจุบันว่าเยี่ยมชมแล้ว และ enqueue มัน จะใช้เพื่อหาจุดติดกันทั้งหมดของจุดหนึ่ง C) Dequeue จุดจากคิวและพิมพ์มัน D) หาจุดติดกันทั้งหมดของจุด s ที่ dequeue มา E) ถ้าจุดติดกันยังไม่ถูกเยี่ยมชม ให้ทำเครื่องหมายว่าเยี่ยมชมแล้วและ enqueue มัน F) ถ้าจุดติดกันนี้คือจุดปลายทาง ให้คืนค่า true มิฉะนั้นทำ BFS ต่อ จบ
ตัวอย่างโค้ด
#include <iostream> #include <list> using namespace std; class G { int n; list<int> *adj; public: G(int n); void addEd(int x, int w); bool isReach(int s, int d); }; G::G(int n) { //constructor this->n = n; adj = new list<int> [n]; } void G::addEd(int x, int w) { //เพิ่มขอบในกราฟ adj[x].push_back(w); //เพิ่ม w ในลิสต์ของ x } bool G::isReach(int s, int d) { if (s == d) return true; bool *visited = new bool[n]; //ทำเครื่องหมายทุกจุดว่าไม่ได้เยี่ยมชม for (int i = 0; i < n; i++) visited[i] = false; list<int> queue; //ทำเครื่องหมายจุดปัจจุบันว่าเยี่ยมชมแล้วและ enqueue visited[s] = true; queue.push_back(s); list<int>::iterator i; while (!queue.empty()) { s = queue.front(); queue.pop_front(); //Dequeue จุดจากคิวและพิมพ์ //ถ้าจุดติดกันยังไม่ถูกเยี่ยมชม for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (*i == d) return true; if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } return false; } int main() { G g(4); g.addEd(1, 3); g.addEd(0, 1); g.addEd(2, 3); g.addEd(1, 0); g.addEd(2, 1); g.addEd(3, 1); cout << "Enter the source and destination vertices: (0-3)"; int a, b; cin >> a >> b; if (g.isReach(a, b)) cout << "\nThere is a path from " << a << " to " << b; else cout << "\nThere is no path from " << a << " to " << b; int t; t = a; a = b; b= t; if (g.isReach(a, b)) cout << "\nThere is a path from " << a << " to " << b; else cout << "\nThere is no path from " << a << " to " << b; return 0; }
ผลลัพธ์
Enter the source and destination vertices: (0-3) There is a path from 3 to 1 There is a path from 1 to 3
