Как определить, существует ли путь между двумя вершинами в BGL

Question

Я хочу использовать библиотеку Boost Graph, чтобы решить, существует ли путь между двумя узлами на направленном невзвешенном графике.

Поэтому я стараюсь использовать либо Breath-First-Search, либо Dijkstra, но я запутался во всех этих списках параметров.

Что это самый простой способ создать такую ​​функцию:

bool isPath(src,dest); 

с BGL?

Answer 1

BFS/DFS - самый простой способ. Я нарисую решение DFS, потому что он меньше голоден.

Предположив вас есть матрица смежности adj размера N x N (N является числом вершин в графе) с:

1. 1 в adj[i][j] если вы ребро, выходящие из i вершины до j вершины,
2. 0 в противном случае.

В этом случае вы могли бы иметь что-то вроде этого:

// doing DFS... 
bool isPath(int src, int dest) { 
    bool visited[N] = {false}; 
    visited[src] = true; 
    std::stack<int> next; 
    next.push(src); 

    while(!next.empty()) { 
    int cv = next.top(); 
    next.pop(); 

    for (int nv = 0; nv < N; ++nv) { 
     if (!visited[nv] && adj[cv][nv] == 1) { 
     visited[nv] = true; 
     next.push(nv); 
     } 
    } 
    } 
    // dest was reached from src? 
    return visited[dest]; 
}