그래프와 그래프를 탐색하는 기본적인 알고리즘인 깊이 우선 탐색과 너비 우선 탐색을 알아보자.

기본 용어

위 그래프에서 원 모양을 노드라 하며, 노드 간의 연결 선을 간선이라 한다. 그래프 중에는 트리도 있는데, 트리는 사이클이 없는 그래프이다. 노드를 도시로 보고 간선을 도로라고 볼 수 있다. 도로가 일방통행이라면 방향이 있다는 의미에서 유향 그래프 또는 단방향 그래프라고 부른다. 서울에서 인천으로 갈 수 있듯 인천에서 서울로도 갈 수 있다면 무향 그래프 또는 양방향 그래프라고 부른다. 참고로 트리는 무향 그래프이다. 트리도, 트리가 아닌 그래프도 기본적인 그래프 탐색 알고리즘인 깊이 우선 탐색과 너비 우선 탐색으로 모두 탐색할 수 있다. 자료구조로 대응하면 각각이 스택과 큐에 대응된다. 구현하는 방법과 특징을 알아보자.

입력 받기

n개의 노드가 있고 m개의 간선이 있다고 하자. 이 정보를 온전히 graph라는 배열에 받고 싶다.

• 1에서 → 2, 3, 7로 갈 수 있다고 했을 때

2번이 효율적이므로 2번 방식으로 코드를 짜자면 아래와 같다.

int n,m;cin>>n>>m;
    vector<int> graph[n+1];
    for(int i=0;i<m;i++){
        int x, y;cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

깊이 우선 탐색(DFS)

깊이 우선 탐색은 스택을 이용해서 구현하기 때문에 스택과 대응되는 재귀로도 구현할 수 있다. 1에서 시작해서, 모든 곳을 한 번만 방문하는 코드를 짜 보자. 방문했는지의 정보는 visisited라는 배열에 담겠다. visited[i]=1이면 i는 이미 방문했다는 소리이고, 0이면 그렇지 않다는 의미이다. “ 현재 위치 1에서, 갈 수 있는 곳 {2, 3, 7}을 보면서, 각각을 방문하지 않았으면 방문한다. ”를 일반화하여 i에서 갈 수 있는 곳 {a1, a2, …, ak}까지 각각을 방문하지 않았으면 방문한다고 짠 뒤, 재귀의 힘을 믿으면 구현된다. 그 코드는 아래와 같다. 편의 상 n의 최댓값을 10만으로 생각하고, graph벡터를 전역으로 옮겼다.

bool visited[101010]={0,};
vector<int> graph[101010];
void dfs(int location){
    visited[location]=1;
    for(int i=0;i<graph[location].size();i++){
        int next=graph[location][i];
        if(visited[next]) continue;
        dfs(next);
    }
}