โปรแกรม C++ หาเส้นทางระหว่างสองโหนดในกราฟ

ในโปรแกรมนี้สามารถหาได้ว่าเส้นทางมีอยู่ระหว่างสองโหนดหรือไม่ โดยใช้ DFS บนกราฟที่กำหนด

อัลกอริทึม

Begin
  function isReach() เป็น recursive function ตรวจสอบว่า d เข้าถึงได้จาก s:
    A) ทำเครื่องหมายโหนดทั้งหมดว่า unvisited
    B) ทำเครื่องหมายโหนดปัจจุบัน visited และ enqueue ใช้เพื่อดึงโหนดติดกันทั้งหมด
    C) Dequeue โหนดจาก queue และพิมพ์
    D) ดึงโหนดติดกันทั้งหมดของโหนด s ที่ dequeue
    E) ถ้าโหนดติดกันยังไม่ถูกเยี่ยมชม ทำเครื่องหมาย visited และ enqueue
    F) ถ้าโหนดติดกันนี้คือ destination node คืนค่า true มิฉะนั้นทำ BFS ต่อ
End

ตัวอย่างโค้ด

#include <iostream>
#include <list>
using namespace std;

class G {
  int n;
  list<int> *adj;
public:
  G(int n);
  void addEd(int v, int u);
  bool isReach(int s, int d);
};

G::G(int n) {
  this->n = n;
  adj = new list<int>[n];
}

void G::addEd(int v, int u) {
  adj[v].push_back(u);
}

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;
  visited[s] = true;
  queue.push_back(s);
  list<int>::iterator i;
  while (!queue.empty()) {
    s = queue.front();
    queue.pop_front();
    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 = 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