너비 우선 탐색 (Breadth-First Search, BFS)

너비 우선 탐색은 시작 정점으로부터 가까운 노드를 우선적으로 탐색하는 알고리즘으로, 이진 트리의 레벨 순회(Level-order traversal) 방식과 유사합니다. 탐색 과정에서 큐(Queue)를 사용하여 정점을 관리하고, 방문 여부를 기록하기 위한 불리언 배열을 사용합니다.

시작 정점을 큐에 넣고 방문 처리한 뒤, 큐가 비어있지 않을 때까지 다음 과정을 반복합니다.

• 큐에서 정점을 하나 꺼내 방문합니다.
• 해당 정점과 연결된 인접 정점 중 아직 방문하지 않은 정점을 모두 큐에 추가하고 즉시 방문 상태로 기록합니다.

void performBFS(const T& startNode) {
    size_t startIndex = getIndex(startNode);
    std::queue<int> frontier;
    std::vector<bool> isVisited(nodeCount, false);

    frontier.push(startIndex);
    isVisited[startIndex] = true;

    while (!frontier.empty()) {
        int current = frontier.front();
        frontier.pop();
        std::cout << current << ": " << nodeList[current] << std::endl;

        for (size_t neighbor = 0; neighbor << nodeCount; ++neighbor) {
            if (adjMatrix[current][neighbor] != INF && !isVisited[neighbor]) {
                isVisited[neighbor] = true;
                frontier.push(neighbor);
            }
        }
    }
}

깊이 우선 탐색 (Depth-First Search, DFS)

깊이 우선 탐색은 한 방향으로 갈 수 있는 최대한의 깊이까지 탐색한 후, 더 이상 진행할 곳이 없으면 이전 노드로 돌아와 다른 경로를 탐색합니다. 이는 트리의 전위 순회(Pre-order traversal)와 원리가 같습니다.

주로 재귀 호출을 사용하여 구현하며, 방문 상태를 기록하는 배열을 통해 중복 방문을 방지합니다.

• 현재 정점을 방문 처리합니다.
• 인접한 정점 중 아직 방문하지 않은 정점이 있다면 해당 정점을 대상으로 재귀적으로 DFS를 호출합니다.

void traverseDFS(size_t currentIndex, std::vector<bool>& visited) {
    visited[currentIndex] = true;
    std::cout << currentIndex << ": " << nodeList[currentIndex] << std::endl;

    for (size_t next = 0; next << nodeCount; ++next) {
        if (adjMatrix[currentIndex][next] != INF && !visited[next]) {
            traverseDFS(next, visited);
        }
    }
}

void runDFS(const T& startNode) {
    size_t startIndex = getIndex(startNode);
    std::vector<bool> visited(nodeCount, false);
    traverseDFS(startIndex, visited);
}