close

C++ 中的图搜索 (Graph Search) 算法- 解释、示例和代码

图搜索算法是图处理和信息检索领域的一项基础技术。 该算法使我们能够根据特定规则或搜索算法在图中查找路径或组件。

怎么运行的

  1. 从图中的特定顶点（节点）开始。
  2. 根据特定规则执行搜索过程，例如深度优先搜索（DFS）或广度优先搜索（BFS）。
  3. 遍历图的顶点和边来搜索要查找的目标或对象。
  4. 记录路径或搜索结果。

例子

考虑下图： 

A -- B -- C -- E  
|      |  
D --------

我们希望使用深度优先搜索(DFS) 算法在此图中找到从顶点 A 到顶点 E 的路径。

  1. 从顶点 A 开始。
  2. 移动到顶点 B。
  3. 继续到顶点C。
  4. C 中没有邻居，回溯到顶点 B。
  5. 移动到顶点 D。
  6. 继续到达顶点 A（因为 D 连接到 A）。
  7. 移动到顶点 B。
  8. 移动到顶点C。
  9. 移动到顶点E。

从A到E的路径是A->B->C->E。

C++ 示例代码 

#include <iostream>  
#include <vector>  
#include <stack>  
#include <unordered_map>  
  
class Graph {  
public:  
    void addEdge(char from, char to);  
    std::vector<char> depthFirstSearch(char start, char end);  
  
private:  
    std::unordered_map<char, std::vector<char>> adjList;  
};  
  
void Graph::addEdge(char from, char to) {  
    adjList[from].push_back(to);  
    adjList[to].push_back(from);  
}  
  
std::vector<char> Graph::depthFirstSearch(char start, char end) {  
    std::vector<char> path;  
    std::unordered_map<char, char> parent;  
    std::stack<char> stack;  
  
    stack.push(start);  
    parent[start] = '\0';  
  
    while(!stack.empty()) {  
        char current = stack.top();  
        stack.pop();  
  
        if(current == end) {  
            // Build the path from end to start using the parent map  
            char node = end;  
            while(node != '\0') {  
                path.insert(path.begin(), node);  
                node = parent[node];  
            }  
            break;  
        }  
  
        for(char neighbor: adjList[current]) {  
            if(parent.find(neighbor) == parent.end()) {  
                parent[neighbor] = current;  
                stack.push(neighbor);  
            }  
        }  
    }  
  
    return path;  
}  
  
int main() {  
    Graph graph;  
    graph.addEdge('A', 'B');  
    graph.addEdge('A', 'D');  
    graph.addEdge('B', 'C');  
    graph.addEdge('C', 'E');  
    graph.addEdge('D', 'B');  
  
    char start = 'A';  
    char end = 'E';  
  
    std::vector<char> path = graph.depthFirstSearch(start, end);  
  
    std::cout << "Path from " << start << " to " << end << ": ";  
    for(char node: path) {  
        std::cout << node << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

在这个例子中，我们使用DFS算法来寻找图中从顶点A到顶点E的路径。 结果将是形成从 A 到 E 的路径的一系列顶点。