알고리즘 3 : 연결된 정점들, BFS

시작에 앞서

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점을 한번씩 방문 하는 것이 목적이다. 때문에 하나씩 모두 방문하여 찾아야 하는데 상황에 따라 효과적인 방법이 있다. 그 중 가장 대표적인 방법 BFS, DFS를 소개한다. 이 둘은 탐색 순서만 다를 뿐, 모든 자료를 한번씩 확인해 본다는 점은 같다.

 

아래 jpg는 코드스테이츠 학습자료이다.

 

DFS : 가장 가까운 길로 들어가서 막다른 길이 나올때까지 탐색한다. 그다음 다시 출발지점으로 와서 그 두번째로 가까운 길로 들어간다.

이를 반복하여 모든 길을 탐색함

 

BFS : 길을 끝까지 가지 않고 중간에 나온다. 그 후 다음 길에 들어가서 중간에 나온다. 반복하여 모든길을 얕게 탐색한 후, 다시 처음길로 들어가 더 깊게 탐색한다. 반복한다.

연결된 정점들

방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성한다.

인자1 :edges

• 2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열)
  ex) [[0, 1], [1, 2], [3, 4]]

출력 :

• Number타입 리턴
• 연결된 정점의 컴포넌트 수를 숫자로 반환한다.

주의사항 :

• 주어진 간선은 무향이다.

입출력 예시

const result = connectedVertices([
    [0, 1],
    [2, 3],
    [4, 5],
]);
console.log(result); // 3

const result = connectedVertices([
    [0, 1],
    [2, 3],
    [3, 4],
    [3, 5],
]);
console.log(result); // 2

코드

function connectedVertices(edges) {

let max = Math.max(...edges.flat())//matrix의 길이 구함
let matrix = new Array(max+1).fill(0).map(i=>Array(max+1).fill(0))//0으로 만들어진 정방행렬 matrix

edges.forEach(i=>{//edges가 간선을 보여준다. edges를 참고해서 연결된 정점들을 1로 표시한다.
  matrix[i[0]][i[1]]=1
  matrix[i[1]][i[0]]=1
})

let q = [];//Queue
let visited = new Array(max+1).fill(false) // 지나온 정점을 체크할 visited 배열, 지나온곳은 두번다시 지나지 않는다.

let count = 0;//컴퍼넌트가 몇개인지?
let current = 0;//현재위치를 할당할 변수 current
for(let i = 0;i<matrix.length;i++){
  if(visited[i]===true) continue//지나온 곳이라면 반복문의 현재단계를 생략하고 다음단계로 간다.
  q.unshift(i)//처음오는 곳이라면(visited[i]===false) 배열q에 현재 인덱스를 추가한다.
  visited[current]=true//현재위치를 체크하는 뜻에서 true로 바꿔준다.
  while(q.length>0){//Queue의 탈출조건은 아무것도 남아있지 않을 때 이다.

    current=q.shift()//현재위치(인덱스)를 current에 할당.

    for(let j = 0;j<matrix[current].length;j++){//현재 위치에서 연결된 곳, 값이 1인곳을 탐색한다.
      if(matrix[current][j]===1 && visited[j]===false){//연결되있으면서(값이 1), 아직 지나치지 않은곳 (visited[j]===true)라면
        visited[j]=true//현재 인덱스를 체크하고
        q.unshift(j)//현재 인덱스를 q배열에 추가한다.
      }
    }
  }count++//연결이 끝나면 while문이 종료되고 한 그룹을 탐색했다는 의미로 count+1 해준다.
}

return count
}

상세설명

let max = Math.max(...edges.flat())
let matrix = new Array(max+1).fill(0).map(i=>Array(max+1).fill(0))

edges.forEach(i=>{
  matrix[i[0]][i[1]]=1
  matrix[i[1]][i[0]]=1
})

아래 코드는 다음과 같은 matrix 행렬을 만든다.

아래 코드는 BFS 탐색 방식을 이용한 것이다.

for(let i = 0;i<matrix.length;i++){
  if(visited[i]===true) continue
  q.unshift(i)
  visited[current]=true
  while(q.length>0){
    current=q.shift()
    for(let j = 0;j<matrix[current].length;j++){
      if(matrix[current][j]===1 && visited[j]===false){
        visited[j]=true
        q.unshift(j)
      }
    }
  }count++
}

for(let i =0....)을 이용하여 각 배열의 모든 행을 탐색한다
visited 배열은 두번 방문하지 않게 하기 위한 장치이다.
그 다음은 해당 정점에서 연결된 마지막 정점까지의 경로를 추적하는 과정이다.
BFS라고 줄일 수 있다.

간선이 연결된 한 그룹을 찾을 때 마다 count를 1증가시킨다.

for(let i = 0;i<matrix.length;i++){
  if(visited[i]===true) continue
      BFS
    count++;
    }
}

BFS탐색방식

q.unshift(i)  //시작점 queue에 넣어준다.
  visited[current]=true // 방문했다고 표시
  while(q.length>0){ // queue에 모든게 없어질 때 까지 반복
    current=q.shift() //queue에서 하나 빼서 현재정점을 뜻하는 current변수에 할당
    for(let j = 0;j<matrix[current].length;j++){//정점순회하면서
      if(matrix[current][j]===1 && visited[j]===false){//연결되어 있고(값이 1), 한번도 지나지 않은곳(visited[j]===false)라면
        visited[j]=true//방문했다고 체크
        q.unshift(j)//큐에 현재 인덱스를 넣어준다. 
        //(현재 인덱스j 는 연결되어 있으며(값이1), 지금 처음 온 곳이다.(방금 visited[j]를 true로 바꿨음)
      }
    }
  }

BFS에서 if(matrix[current][j]===1 && visited[j]===false) 조건에 어긋나면 연결이 끝났음을 알고, while문이 종료된다.
그리고 count를 1 더해준다.