Graph-DFS、BFS深化

20830 ワード
データ構造 テキストリンク

接続された頂点


質問する
方向のない幹線のリストが与えられると、
頂点を接続する複数の構成部品(グループ)を返す関数を作成します.
入力
パラメータ1:edge
要素の始点と終点として2 D Arrayタイプが含まれる配列のリスト.
ex) [[0, 1], [1, 2], [3, 4]]
しゅつりょく
番号タイプを返す必要があります.
頂点を接続する構成部品の数を数値で返します.
注意事項
与えられた幹線は故郷がない.
[1,2]頂点1から頂点2まで、または頂点2から頂点1まで.
function connectedVertices(edges) {
  
  // 1. 주어진 정점을 통해 matrix를 완성하자.

  // 가장 큰 정점 찾기
  let biggestV = Math.max(...edges.flat())    
  // 최댓값으로 matrix 만들기
  let matrix = Array(biggestV + 1).fill(0)
  			.map((el) => Array(biggestV + 1).fill(0))

  // 매트릭스에 edges 반영하기 -> 간선 추가하기
  edges.forEach( edge => {
    let [from, to] = edge
    matrix[from][to] = 1;
    matrix[to][from] = 1;
  }) // 주어진 간선은 무향(쌍방)이다!
  
// -------------- 인접행렬 완성!
  
  let isVisited = [] // 중복 방지 배열
  let groups = 0; // 연결된 정점들을 하나의 그룹으로 만들 것이다.

  for (let start = 0; start < matrix.length; start++) {
    if (!isVisited.includes(start)) {
      dfs(matrix, start) // start와 연결된 정점을 다 탐색하고
      groups++; // 그것을 한 그룹으로 친다.
    }
  }

  function bfs(matrix, vertex) {
  let Q = [vertex];
      while (Q.length) {
        let now = Q.shift()
        isVisited.push(now)
        for (let next = 0; next < matrix[now].length; next++) {
          if(matrix[now][next] && !isVisited.includes(next)) {
            Q.push(next)
          }
        }
      }
    }

  function dfs(matrix, vertex) {
    isVisited.push(vertex)
    for (let next = 0; next < matrix[vertex].length; next++) {
      if (matrix[vertex][next] && !isVisited.includes(next)) {
      dfs(matrix, next)
      }
    }
  }
  return groups;
}
上記のプールでは、bfsおよびdfs関数が補助関数である.
connectedVerticesプライマリ関数のisVisited変数にアクセスできます.
パラメータを使用してisVisitedを追加する必要はありません.
function connectedVertices(edges) {
  
  let biggestV = Math.max(...edges.flat())    
  let matrix = Array(biggestV + 1).fill(0)
  		.map((el) => Array(biggestV + 1).fill(0))

  edges.forEach( edge => {
    let [from, to] = edge
    matrix[from][to] = 1;
    matrix[to][from] = 1;
  }) 
  
  let isVisited = []
  let groups = 0; 

  for (let start = 0; start < matrix.length; start++) {
    if (!isVisited.includes(start)) {
      bfs(matrix, start, isVisited) 
      groups++; 
    }
  }
  return groups;
}

function bfs(matrix, vertex, isVisited) {
  let Q = [vertex];
      while (Q.length) {
        let now = Q.shift()
        isVisited.push(now)
        for (let next = 0; next < matrix[now].length; next++) {
          if(matrix[now][next] && !isVisited.includes(next)) {
            Q.push(next)
          }
        }
      }
    }

  function dfs(matrix, vertex, isVisited) {
    isVisited.push(vertex)
    for (let next = 0; next < matrix[vertex].length; next++) {
      if (matrix[vertex][next] && !isVisited.includes(next)) {
      dfs(matrix, next, isVisited)
      }
    }
  }
上記のdfs,bfs関数は独立している.
一緒に使うためにisVisited情報をパラメータで渡す必要があります.
プログラマー-入国審査
101.git