그래프 순회

너비 우선 탐색

2개의 큐를 이용

A큐 - 방문한 노드들을 쌓는다. 쌓일 때 연결된 노드들을 B큐에 추가한다.

B큐 -

초깃값을 설정한 뒤 큐에 값이 없을 때까지 실행한다.

맨 앞의 노드를 A로 내보낸 뒤 해당 노드와 연결된 노드를 큐에 추가한다.

이때 A에 중복된 노드가 있다면 A에 저장하지 않는다

 

자바스크립트 ver.

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }
    breadthFirst(start) {
        const queue = [start];
        const result = [];
        const visited = {};
        let currentVertex;
        visited[start] = true;

        while (queue.length) {
            currentVertex = queue.shift();
            result.push(currentVertex);


            this.adjacencyList[currentVertex].forEach(v => {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.push(v);
                }
            });
        }
        return result;
    }
}

파이썬 ver.

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

깊이 우선 탐색

1개의 큐와 1개의 스택을 이용

큐 - 방문한 노드들을 쌓는다. 쌓일 때 연결된 노드들을 스택에 추가한다.

스택 -

초깃값을 설정한 뒤 스택에 값이 없을 때까지 실행한다.

맨 뒤의 노드를 큐로 내보낸 뒤 해당 노드와 연결된 노드를 스택에 추가한다.

이때 큐에 중복된 노드가 있다면 큐에 저장하지 않는다

 

재귀적 용법 사용

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }
    depthFirstRecursive(start) {
        const result = [];
        const visited = {};
        const adjacencyList = this.adjacencyList;

        (function dfs(vertex) {
            if (!vertex) return null;
            visited[vertex] = true;
            result.push(vertex);
            adjacencyList[vertex].forEach(v => {
                if (!visited[v]) {
                    return dfs(v)
                }
            });
        })(start);

        return result;
    }
}

순환적 용법 사용

자바스크립트 ver.

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }
    depthFirstIterative(start) {
        const stack = [start];
        const result = [];
        const visited = {};
        let currentVertex;

        visited[start] = true;
        while (stack.length) {
            currentVertex = stack.pop();
            result.push(currentVertex);

            this.adjacencyList[currentVertex].forEach(v => {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v)
                }
            });
        }
        return result;
    }
}

파이썬 ver.

def dfs(graph, start_node):
    visited, to_visit = list(), list([start_node])

    while to_visit:
        node = to_visit.pop()
        if node not in visited:
            visited.append(node)
            to_visit.extend(graph[node])

    return visited