Section 34.9 Search Example : Friend Finder
As a concrete example of using graph search, we will consider the problem of determining a way to get a message from one person to another. We will rely on the same friendship graph structure we saw earlier:
We want to figure out how Anna can get a message to Fred. Finding the shortest path would make sense, as it would minimize the number of intermediaries needed to deliver the message. So we will use breadth-first search.
First, we need to set up the graph. The
addEdge function will add an edge between two vertices, and if the vertices do not already exist, it will add them to the graph as well. We do not want edge weights, but we do want the edges to be undirected, so we will set the weight to 1 and the directed flag to false. That will cause adding an edge from Anna to Ben to also add an edge from Ben to Anna.
Graph<string> graph;
// edge between Anna and Ben with a weight of 1, undirected
graph.addEdge("Anna", "Ben", 1, false);
// add the rest of the edges in the graph
graph.addEdge("Anna", "Diego", 1, false);
...
We then need to implement the BFS algorithm. Translating our BFS pseudocode into actual code looks like this:
/**
* @brief Performs a breadth-first search on the graph starting from the given vertex
* @param graph The graph to search
* @param vertex The starting vertex
* @return A map of each vertex to its parent in the search tree
*/
unordered_map<string, string> bfs(const Graph<string>& graph,
const string& vertex) {
queue<string> searchQueue;
searchQueue.push(vertex);
unordered_set<string> known;
known.insert(vertex);
unordered_map<string, string> parentMap;
while (!searchQueue.empty()) {
string current = searchQueue.front();
searchQueue.pop();
for (const auto& neighbor : graph.getNeighbors(current)) {
if (!known.contains(neighbor)) {
known.insert(neighbor);
parentMap[neighbor] = current;
searchQueue.push(neighbor);
}
}
}
return parentMap;
}
Finally, we can perform the search and print the path from Anna to Fred:
You have attempted of activities on this page.
