DFS/BFS

DFS는 스택/재귀로 구현 가능 -> 모든 노드 방문

BFS는 큐로 구현 가능 -> 최단 거리

 

1. 흐름

1) DFS - 재귀

시작 노드 받아서

방문했다 표시해주고

그래프 사이즈만큼 돌면서

    그 그래프에 붙어있는 애들 하나씩 빼서

    만약 방문하지 않은애면 다시 dfs 돌기

 

2) DFS - 스택

시작값 스택에 넣고, 방문했다 표시

스택이 빌때까지

    스택의 맨 위에 있는 애한테 붙어있는 애들 하나씩 빼서

        만약 방문하지 않았으면 방문했다하고 스택에 추가

    더이상 방문하지않거나, 인접한 노드 없으면 스택에서 pop

 

3) BFS

시작 노드 받아서

큐에 넣고 방문했다 표시

큐가 빌때까지

    큐의 앞에서 값 빼내고

    아까 빼낸애한테 붙어있는 애들 개수만큼 돌면서

        하나씩 빼내서 방문하지 않은애면 큐에 넣고 방문했다 표시

 

2. 구현

1) DFS

    a) 재귀(C++)

void dfs(int x)
{
    visited[x] = true;

    for(int i=0; i<graph[x].size(); i++)
    {
        int y = graph[x][i];
        if(!visited[y]) dfs(y);
    }
}

   

    b) 재귀(Python)

def dfs(x):
    visited[x] = True
    print(x, end=' ')
    for i in graph[x]:
        if not visited[i]: dfs(i)

 

    c) Stack(C++)

    d) Stack(Python)

 

2) BFS

    a) C++

void bfs(int start)
{
    fill_n(visited,1001,false);

    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i=0; i<graph[x].size(); i++)
        {
            int y = graph[x][i];
            if(!visited[y])
            {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

 

    b) Python

def bfs(start):
    queue = deque([start])
    visited[start] = True
    while len(queue) > 0:
        x = queue.popleft()

        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True