ST Connected
Tests whether two vertices s and t are connected by a path. Uses a bidirectional BFS that searches simultaneously from s and t.
Complexity: O(V + E) worst case, typically much faster
Defined in: <boost/graph/st_connected.hpp>
Both overloads live in namespace boost::graph (not boost).
Example
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/st_connected.hpp>
#include <iostream>
using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS>;
int main() {
Graph g(5);
add_edge(0, 1, g); add_edge(1, 2, g);
// vertices 3 and 4 are isolated from 0-1-2
bool connected_0_2 = graph::st_connected(g, vertex(0, g), vertex(2, g));
bool connected_0_3 = graph::st_connected(g, vertex(0, g), vertex(3, g));
std::cout << "0 connected to 2: " << std::boolalpha << connected_0_2 << "\n";
std::cout << "0 connected to 3: " << std::boolalpha << connected_0_3 << "\n";
}0 connected to 2: true
0 connected to 3: false(1) With explicit color map
template <typename Graph, typename ColorMap>
bool st_connected(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor t,
ColorMap color);| Direction | Parameter | Description |
|---|---|---|
IN |
|
Must model Incidence Graph. |
IN |
|
Source vertex. |
IN |
|
Target vertex. |
UTIL |
|
ReadWritePropertyMap for working storage. One entry per vertex, initialized to white. The value type must model Color Value. |
(2) With default color map
template <typename Graph>
bool st_connected(const Graph& g,
typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor t);Equivalent to overload (1) using a default two_bit_color_map of size num_vertices(g) indexed by get(vertex_index, g).
Returns true if there is a path from s to t.
| This is faster than running a full BFS when you only need to check reachability between two specific vertices. |