자료구조 - 그래프의 탐색(DFS)

[그래프의 탐색]

그래프의 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다.

그래프의 탐색은 매우 중요하며 크게 두 가지 방법이 있습니다.

 

[깊이 우선 탐색(DFS : depth first search)]

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 한 정점의 모든 인접 정점을 방문한 후 다음 정점으로 이동하는 방식으로 그래프를 탐색합니다. DFS는 스택 자료구조를 이용하거나 재귀 호출을 통해 구현할 수 있습니다.

DFS 알고리즘

1. 시작 정점을 방문하고 이를 방문했다고 표시한다.
2. 현재 정점에서 인접한 정점 중 방문하지 않은 정점이 있으면, 그 정점으로 이동하여 1번 과정을 반복한다.
3. 더 이상 방문할 정점이 없다면, 이전 정점으로 돌아가서 다른 인접 정점을 탐색한다.
4. 모든 정점을 방문할 때까지 1-3번 과정을 반복한다.

 

 

 

 

 

 

DFS 구현 : 인접 행렬

#include <iostream>
#include <vector>

void DFSUtil(const std::vector<std::vector<int>>& adjMatrix, std::vector<bool>& visited, int v) 
{
    // 현재 정점을 방문했다고 표시
    visited[v] = true;
    std::cout << v << " ";

    // 인접한 모든 정점을 확인
    for (int i = 0; i < adjMatrix.size(); ++i) 
    {
        // 인접 정점이며 아직 방문하지 않았다면 재귀 호출
        if (adjMatrix[v][i] == 1 && !visited[i]) 
        {
            DFSUtil(adjMatrix, visited, i);
        }
    }
}

void DFS(const std::vector<std::vector<int>>& adjMatrix, int start) 
{
    // 정점의 방문 여부를 저장하는 벡터 초기화
    std::vector<bool> visited(adjMatrix.size(), false);

    // 시작 정점에서 DFS 시작
    DFSUtil(adjMatrix, visited, start);
}

 

 

 

DFS 구현 : 인접 리스트

#include <iostream>
#include <vector>
#include <list>

void DFSUtil(const std::vector<std::list<int>>& adjList, std::vector<bool>& visited, int v) 
{
    // 현재 정점을 방문했다고 표시
    visited[v] = true;
    std::cout << v << " ";

    // 인접한 모든 정점을 확인
    for (int neighbor : adjList[v]) 
    {
        // 인접 정점이며 아직 방문하지 않았다면 재귀 호출
        if (!visited[neighbor]) 
        {
            DFSUtil(adjList, visited, neighbor);
        }
    }
}

void DFS(const std::vector<std::list<int>>& adjList, int start) 
{
    // 정점의 방문 여부를 저장하는 벡터 초기화
    std::vector<bool> visited(adjList.size(), false);

    // 시작 정점에서 DFS 시작
    DFSUtil(adjList, visited, start);
}

 

 

 

[시간 복잡도 분석]

 

인접 행렬

• 각 정점에 대해 모든 정점을 확인하므로, 시간 복잡도는 O(V^2) 입니다.
• 여기서 VVV는 정점의 수입니다.

인접 리스트

• 각 정점에 대해 인접한 정점을 확인하므로, 시간 복잡도는 O(V + E) 입니다.
• 여기서 V는 정점의 수, E는 간선의 수입니다.

 

 

 

 

 

 

 

 

 

ㅇㅅㅇ