Breadth First Search幅を優先的に参照

10711 ワード
algorithm テキストリンク

Breadth First Search幅を優先的に参照


  • ルートノードまたは任意のノードから、まず隣接ノードのグラフィックナビゲーション方法を参照します.

  • これは,まず開始頂点に近い頂点を探索する方法である.

  • そのため、深さというより広さです.

  • このメソッドは、最短パスまたは任意のパスを検索するときに使用します.
  • ex)A~Zのノードがある場合は、AからFへの経路
    • を探す必要がある.
  • 深度優先ブラウズ:最悪の場合、すべての接続関係をブラウズします.
  • 幅優先ナビゲーション:Aに近いノードからナビゲーションを開始します.
    • void Bfs(int here)
{
	// 루트노드를 push하여 탐색 "예약"을 해준다.
	queue<int> q;
	q.push(here);
	discovered[here] = true;

	while (q.empty() == false)
	{
    		// 가장 우선순위로 예약된 노드부터 탐색을 시작한다.
		here = q.front();
        	// 탐색이 실행될 것이니 예약 순위에서 제거한다.
		q.pop();

		cout << "Visited: " << here << endl;
		
        
		for (int there : adjacent[here])
		{
        		// 이미 방문한 노드라면 다시 방문하지 않는다. 
			if (discovered[there])
				continue;
			// 방문한적 없는 노드라면 
            		// 해당 노드에 대한 탐색을 예약한다.
			q.push(there);
           		 // 노드 방문 여부를 true로 처리한다.
			discovered[there] = true;
		}
	}
}

void BfsAll()
{
	// 서로 연결이 안된 정점을 탐색하기 위함
	for (int i = 0;i < 6;i++)
	{
		if (discovered[i] == false)
			Bfs(i);
	}
}

  • 「予約」のように、スタートに近い頂点をpushで検索します.

  • アクセスした場合は、discoveryをtrueに設定して無限ループを防止します.

  • Queueの先入先出特徴を用いて所定の順序で探索する.

  • いくつかのセグメントコードを追加すると、自分のノードを発見する情報と、開始点からの距離についても理解できます.
    • void Bfs(int here)
{
	// 누구에 의해 발견 되었는지?
	vector<int> parent(6, -1);
	// 시작점에서 얼만큼 떨어져 있는지?
	vector<int> distance(6, -1);

	queue<int> q;
	q.push(here);
	discovered[here] = true;
	parent[here] = here;
	distance[here] = 0;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited: " << here << endl;

		for (int there : adjacent[here])
		{
			if (discovered[there])
				continue;

			q.push(there);
			discovered[there] = true;

			parent[there] = here;
			distance[there] = distance[here] + 1;
		}
	}
}
  • を用いて探索する場合,上記のアルゴリズムを用いて,最短経路の情報を距離とparentで知ることができる.
    • [プログラマ]柱とビームのインストール
    ジャバスクリプト — クラスと関数