21 그래프 순회

21.1 그래프 순회

  그래프 순회란 말 그대로 모든 노드, 즉 그래프에 있는 모든 정점을 다 방문한다는 말이다. 트리의 경우에는 찾고자하는 노드에 접근하는 길은 루트에서 출발해서 도착하는 한 가지 방법밖에 없다. 하지만 트리와 다르게 그래프를 순회하는 경우에는 루트가 따로 없기 때문에 코드를 구현할 때는 시작점을 정해줘야 한다. 또한 그래프의 한 노드에서 다른 노드로 가는 방법은 유일한 하나의 방법만 존재한다는 보장이 없다.

 

22.2 깊이 우선 그래프 순회(DFS)

  앞서 배운 이진 탐색 트리의 DFS와 동일한 개념이다. 하지만 그래프에서는 루트가 없기 때문에 하나의 정점을 지정하고 시작해야 한다. 그리고 그래프에서의 깊이 우선 그래프 순회는 한 인접점을 찾고 이어서 인접점을 또 찾는다는 의미이다. 다시 말해 한 번 방문했던 곳을 제외한 간선을 통해 다른 연결된 정점으로 길이 막힐 때까지 이동하는 것이다. 그렇기 때문에 깊이 우선 그래프 순회는 재귀형으로 만들기도 하고, 반복형으로 만들기도 한다. 그래프는 순회시 방문했던 곳을 기억하는 것이 매우 중요하다.

 

◎재귀적 용법 수도코드

1) 시작하는 노드를 입력하는 함수를 만든다.(루트가 없으니 시작할 노드를 직접 인수로 받음)

2) 빈 배열을 만들어서 최종 결과를 저장할 변수를 만들고 마지막에 이를 반환한다.(결과 배열)

3) 순회한 정점들을 추적 할 수 있는 객체를 만들어 준다.(방문 객체)

4) 정점을 입력하는 헬퍼 함수를 만든다.(이 중첩 함수가 재귀 함수임)

5) 헬퍼 함수는 방문한 정점을  방문 객체에 넣어야 한다.

6) 방문한 정점은 방문 객체에 방문했다는 표시를 하고 결과 배열에 추가해 준다.

7) 그리고 나면 해당 정점의 모든 인접점에 대한 루프를 돌린다.

8) 만약 방문하지 않은 정점이라면, 해당 정점에 대해 헬퍼 함수를 재귀 방식으로 호출한다.

9) 내부 함수는 결과 배열과 방문 객체를 최신화하면서 반복하게 된다.

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
    removeEdge(vertex1,vertex2){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
            v => v !== vertex2
        );
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
            v => v !== vertex1
        );
    }
    removeVertex(vertex){
        while(this.adjacencyList[vertex].length){
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }
    depthFirstRecursive(start){
        const result = []; // 순회한 정점들 모아놓는것
        const visited = {}; // 방문한 정점들 확인하는것
        const adjacencyList = this.adjacencyList; // 이걸 따로 만들어 줘야 한다는것을 꼭 기억하셈!
        //아님 에러남

        (function dfs(vertex){
            if(!vertex) return null; // 시작점을 인수로 전달하지 않으면 null을 반환해라 
            visited[vertex] = true;
            result.push(vertex);
            adjacencyList[vertex].forEach(neighbor => {
                if(!visited[neighbor]){
                    return dfs(neighbor)
                }
            });
        })(start);

        return result;
    }
}
//정점에서 시작 -> 정점의 간선 배열 반복 -> 방문한적 없으면 해당 정점으로 이동 -> 반복 -> 
//이동 -> 반복 -> 결국 다 방문하게 되면 -> 그 전 재귀로 -> 그 전 재귀로 -> 그 전 재귀로 -> 배열 반환

◎반복적 용법 수도코드

1) 스택으로 활용할 빈 배열을 만든다.

2) 스택에 시작점으로 활용할 정점을 넣는다.

3) 만약 스택이 빈 배열이 상태가 아니라면 루프를 돌린다. 스택에 정점이 있다면 해당 정점을 pop() 한 다음 방문을 했었는지 확인한다.

4) 아직 방문하지 않았다면 방문 객체에 추가해 준다.

5) 그리고 해당 정점의 인접점에 대해 반복문을 호출하고 스택에 요소들을 추가해 준다.

(재귀형과 같은 DFS 방식이지만 반환하는 결과의 순서는 다르다.)

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
    removeEdge(vertex1,vertex2){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
            v => v !== vertex2
        );
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
            v => v !== vertex1
        );
    }
    removeVertex(vertex){
        while(this.adjacencyList[vertex].length){
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }
 
    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(neighbor => {
               if(!visited[neighbor]){
                   visited[neighbor] = true; // 방문목록에 넣기
                   stack.push(neighbor) // 스택에 넣고
               } 
            });
        }
        return result;
    }
}

22.3 너비 우선 그래프 순회(BFS)

  너비 우선 그래프 순회는 주어진 정점에 대해서 모든 인접점을 다 방문한 다음에 인접점의 인접점을 방문하는 방식으로 순회한다. 즉, 하나의 정점에서 시작하고 그 시작하는 정점과 연결되어 있는 모든 정점들을 다 방문한 후에 정점의 정점으로 이동하여 같은 작업을 반복해서 순회한다. 

 

◎수도코드

반복형 DFS와 거의 유사하지만 다른 점은 스택이 아닌 큐를 사용해서 구현하는 것이다.

1) 함수는 시작할 정점을 인수로 받고, 큐 배열을 만든다.

2) 그리고 시작할 정점을 큐 배열에 추가한다.

3) 그리고 결과로 반환할 배열을 만들어 순회한 정점들을 추가하고 마지막에 반환해 준다.(결과 배열)

4) 이미 방문한 정점들을 저장하기 위해 객체를 만들고 시작 정점을 방문한 것으로 표시한다.(방문 객체)

5) 큐 안에 정점이 들어가 있는한 while 루프를 통해 반복하고 shift 메서드를 통해 배열의 가장 앞에 있는 노드를 빼낸다.

6) 그리고 결과 배열에 추가해 준다.

7) 그리고 해당 점점에 있는 각 인접점들에 대해 아직 방문하지 않았다면 방문한 것으로 표시하고 큐에 추가해준 다음 결과 배열에 하나씩 빼내어 추가해 준다.

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
    removeEdge(vertex1,vertex2){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
            v => v !== vertex2
        );
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
            v => v !== vertex1
        );
    }
    removeVertex(vertex){
        while(this.adjacencyList[vertex].length){
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }

    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(neighbor => {
                if(!visited[neighbor]){
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            });
        }
        return result;
    }
}