[자료구조] 그래프 / 깊이,너비 우선탐색

깊이 너비 우선탐색을 알기전 그래프에 관하여 알고 넘어가야됩니다.
Graph(그래프)
그래프는 트리와 비슷하게 노드와 엣지로 구성되어있습니다. 그래프에서는 워딩이 다르지만 이해하기 쉽게 이 글에서는 노드와 엣지로 표현하겠습니다.(원래는 노드를 버텍스(vertex), 엣지를 아크라 합니다.)

노드와 엣지도 모르시는분이 계실까봐 쉽게 설명하자면 노드는 하나의 지점을 의미하고 노드와 노드사이의 선을 엣지라고 합니다.

크게보면 트리도 노드와 엣지를 가지고 있어 그래프에 포함되지만 그래프에서는 Depth 또는 Level이 존재하지 않습니다. 그래서 부모 자식이 존재하지 않습니다. 그리고 트리에서는 방향성이 존재하지만 그래프에서는 엣지의 방향성이 존재할수도 있고 존재하지 않을수도 있습니다.
그래프에서 방향성의 유무에 따라 방향그래프 무방향그래프로 나뉘게 되는것입니다.
그외 그래프의 종류에는 네트워크(Network)라고 불리는 가중치그래프와 사이클등 다양한 종류가 있지만 깊이 너비 우선탐색을 가중치를 주기 위하여 넘어가겠습니다.

컴퓨터에는 그래프를 표현할수있는방법이 많지 않습니다. 일단 이진법의 계산기인데다가 그것을 입력하는 방법은 많지 않아 크게 두가지로 나뉩니다. 인접리스트와 인접행렬!

위의 사진이 인접 리스트입니다. 주어진 사진으로 바로 인접되어진 노드들을 알수있고 그것으로 그림을 그리는 방식입니다.
아래는 인접행렬로 일단 행렬로 구현하여 어느노드에 어디가 연결되었는지 알기 쉽게 되어있습니다.

인접리스트의 장점은 공간효율성입니다. O(Edge)의 효율성만을 요구하기때문에 공간은 작게 차지하지만 시간의 효율성은 떨어집니다. O(Node)의 효율성이 들게 됩니다.

반대로 인접 행렬은 O(N^2)의 공간효율성으로 떨어지지만 시간효율성은 O(1)밖에 되지 않아 시간효율성은 상당히좋아집니다.

자바스크립트는 자료구조가 따로 있지 않아 배열과 생성자로 만들어야합니다.

    function Node(){// node 생성자 생성 && 방향성 없을때
        this.name = [];
        this.nextNode = [];
        this.addEdge = (node,next) =>{// 엣지 추가
            const nodeIdx = this.name.indexOf(node);
            if(nodeIdx === -1){
                this.name.push(node);
                this.nextNode.push([next]);
            }else{
                this.nextNode[nodeIdx].push(next);
            };
            const nextIdx = this.name.indexOf(next);//방향성 존재시 여기서부터 지우면 됨
            if(nextIdx === -1){
                this.name.push(next);
                this.nextNode.push([node]);
            }else{
                this.nextNode[nextIdx].push(node);
            };
        }
    }
    var node = new Node();
    node.addEdge(1,2);
    node.addEdge(2,3);
    node.addEdge(1,3);
    node.addEdge(3,4);
    node.addEdge(2,4);
    node.addEdge(4,5);
    node.addEdge(3,5);
    node.addEdge(5,6);

    console.log(node);
    

위의 코드는 인접리스트로 된 노드를 제가 따로 구현해본것입니다.

console.log 잘 나옵니다.
설명을 해드리면 첫번째 노드의 이름은 1이고 같은 인덱스에 nextNode는 연결된 노드들을 리스트화 시킨것입니다. 이제 이것을 어떻게 이용할지는 나중의 저에게 맡기고 다음 글로..

이제 우리가 진짜로 알아봐야할 그래프의 탐색방법 두가지입니다.
일반적인 방법으로는 깊이우선탐색(DFS, Depth-First Search)과 너비우선탐색(BFS, Breadth-First Search) 두가지가 있습니다.

1. 깊이 우선탐색
   루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.

• 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다.

• 자기자신을 탐색하는 알고리즘을 가지고 있어 반드시 어느노드를 방문했는지 확인하는 알고리즘을 가지고 있어야합니다.

• 트리의 순회역시 깊이우선탐색의 한종류입니다.

• 백트래킹을 하여 탐색되지 않은 노드가 있나 확인을 하여야합니다.
  위는 깊이 순환 방식의 순서입니다.

• 시작노드에서 or 현재노드에서 방문을 했다는 표시를 합니다. 이후 노드하나를 통해 이동합니다.

• 다음노드에서 방문하지 않은 노드 하나를 정하여 이동합니다. 위사진에서는 하나씩밖에 있지 않아 다음노드로 이동합니다.

• 마지막 노드까지 이동하였을때, 한 노드씩 다시 돌아와 탐색하지 않은 노드가 있는지 확인합니다.

• 확인하지 않은 노드가 있을때는 첫번째 과정을 다시시작합니다.

• 시작노드(root)까지 왔다면 탐색결과를 도출합니다.

  구현방법
  1 순환호출
  2 명시적 스택 사용
  (자바스크립트는 그런거 없습니다. 배열로하세요.)

     function DFScall(nodes){// 원래 노드를 건드리지 않도록 하기위한 새로운 생성자 생성
         this.nodes = nodes.name;
         this.nextNode = nodes.nextNode;
         this.visitedNode = new Array(nodes.name.length); // 방문여부를 확인
         this.order = [];// 순서입력을 위한 
         this.findOrder = (node) =>{// 제일처음은 루트노드 입력
             let nodeIdx = this.nodes.indexOf(node);
             if(this.visitedNode[nodeIdx]){
                 return ;
             }else{
                 this.visitedNode[nodeIdx] = true; // 방문 확인
                 this.order.push(node); // 순서 입력
                 this.nextNode[nodeIdx].forEach(v => {
                     this.findOrder(v);
                 });
             }
         }
     }
  
     var First = new DFScall(nodes);
     console.log(First);
     First.findOrder(1);// 1번 노드가 root 
     console.log(First);
     

자바스크립트로 순환 호출로 구현해 봤습니다. 처음에 생성되었던 노드를 구현해야되는 단점이 있지만 구현해본 결과

아주 잘 나왔습니다. 미래의 나에게 맡겼었는데 그게 15분 뒤일줄을 몰랐지만 잘나와서 기분이 좋네요 ㅎㅎㅎ

2. 너비 우선탐색
   하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다.

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다.
• 따라서 너비 우선탐색이 깊이 우선탐색에 비하여 어렵습니다.
• 자료구조 큐를 이용한 선입선출을 이용한 구조로 탐색하는것이 가장 쉽다고 합니다.

위는 넓이 순환 방식의 순서를 그림화 해놓은 것입니다.

• 시작노드에서 or 현재노드에서 방문을 했다는 표시를 합니다. 인접한 노드를 전부 방문 합니다. 그리고 나서 자료구조 큐에 하위 노드들을 입력해 놓습니다.
• 큐에 맨 앞에 있는 노드로 이동하고 큐에 있는 방문한 노드를 지웁니다.
• 그리고 나서 현재 노드에서 인접한 노드중 방문하지 않은 노드 방문으로 변경해놓고 그 노드를 큐에 맨 뒤에 넣어 놓습니다.
• 이후에는 다시 2번째 순서를 반복합니다.
• 이제 더이상 방문할 노드가 없다면 탐색을 마칩니다.

    function BFScall(nodes){
        this.nodes = nodes.name;
        this.nextNode = nodes.nextNode;
        this.visitedNode = new Array(nodes.name.length); // 방문여부를 확인
        this.order = [];// 순서입력을 위한 
        this.findOrder = (node)=>{
            this.order.push(node); // 순서 입력
            for(let i = 0; this.order.length!==this.nodes.length; i++){
                const nodeIdx = this.nodes.indexOf(this.order[i]);
                this.visitedNode[nodeIdx] = true;//방문 확인
                for(let j = 0 ; j < this.nextNode[nodeIdx].length;j++){
                    const nextIdx = this.nodes.indexOf(this.nextNode[nodeIdx][j]);
                    if(this.visitedNode[nextIdx]){
                    }else{
                        this.order.push(this.nextNode[nodeIdx][j]);
                        this.visitedNode[nextIdx] = true;//방문 확인
                    }
                }
            }
        }
    }
    var second = new BFScall(nodes);
    console.log(second);
    second.findOrder(1);// 1번 노드가 root 
    console.log(second);
    
    

그래서 제가 직접 구현해 봤습니다. 이번에는 좀 오래걸렸습니다.
하루만에 모든걸 다 완료 해버리니 제가 재미없는 인간이라는 생각이 좀 들었지만 그래도 자바스크립트 자체에 구조형이 배열과 구조체밖에 없어 어떻게든 구현해봤습니다.

결과가 아주 잘 나왔습니다. 순서가 앞에것과 같지만 그건 node의 연결차이라서 그렇습니다.
1차로는 여기까지만 해놓고 이것을 알고리즘 문제에 적용한뒤 다시 오겠습니다.