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로의 경로를 형성하는 일련의 꼭지점입니다.