深さ優先アルゴリズムと広さ優先アルゴリズムの理解とよく使われるシーン

深度優先アルゴリズム:
私の理解は迷路を歩くようで、毎回分かれ道に出会うたびに1本の道を選んで歩いて、毎回路地に出会うたびに元の道に戻って前の交差点を見つけて他の道を選んで、出口を見つけるまで、明らかに最悪の状況はすべての道を遍歴した後にやっと道を見つけて、1つの大きい体内で1つのある条件あるいは最も優れた小さい全体を探すことに適用します.最適化は、最適化を見つけるためにすべての組合せスキームを巡回しなければならない.これが深さ優先アルゴリズムです.2つの例(よく使われるシーンでもあります)で理解します:(1)n件の物品があって、各物品の重量はw[i]で、価格c[i]に対応して、いくつかの物品を選んで最大荷重Vのリュックサックの中に入れて、リュックサックの中で物品の価値の和を最大にすることを要求します.最大価値を求めます.分析:明らかにこれは最良の方案を探して、すべての物品はすべて2種類の方案を選んで選ばないことがあって、これは分かれ道です;物品の重量の和はリュックサックの秤量より大きくなくて、これは袋小路です.このような分析を経て、私達は実は深さの優先アルゴリズムが再帰の方式で複数の再帰の口に入るのに適して対応して多種の選択があって、間違っていることを見ることができますreturnは他の選択に入ります:再帰関数を入力するパラメータは往々にして袋小路と私たちが計算する必要がある変数はこの問題のindexのようです:物品の件数の番号(<=n)、sumw:物品の重量の和(<=V)、sumc:物品の価値の和.

#define maxn 30
//             ，        
int n,V;
int w[maxn],c[maxn];
int maxc=0;//      
void DFS(int index,int sumw,int sumc)
{
	if(index==n)
		return;
	DFS(index+1,sumw,sumc);//  
	if(sumw+w[index]<=V){//    
		if(sumc+c[index]>maxc){
			maxc=sumc+c[index];
		}	
		DFS(index+1,sumw+w[index],sumc+c[index]);// 
	}
}
int main()
{
	cin>>n>>V;	
	for(int i=0;i<n;i++)
		cin>>w[i]>>c[i];
	DFS(0,0,0);
	cout<<maxc;
	return 0;
}

(2)N個の数からk個の数を選択して、このk個の数の和をXとし、複数のスキームがあれば、要素の二乗と最大のグループを出力する.(各数は一度しか選択できない)この問題の鍵は、スキーム全体を出力するには、各ステップに挿入された要素を格納する容器が必要であり、次のコードには、選択したA[index]をtmpで格納することである.その後,この分岐を選択した後にtmpから削除することで,選択しない分岐に影響を及ぼさず,再帰と深さ優先アルゴリズムを組み合わせた奥義を体現できる.

#include 
#include 
using namespace std;
#define maxN 30
int N,k,X;
int A[maxN];//N      
int maxsum=-1;//        
vector<int> tmp,ans;//tmp         ，ans          
void DFS(int index,int nowk,int sum,int sumq)
//          ，      ，    ，       
{
	if(nowk==k&&sum==X){
		if(sumq>maxsum){
			maxsum=sumq;
			ans=tmp;
		}
		return;
	} 
	if(index==N||nowk>k||sum>X)//           ，  index==N return            
		return;
	//  
	tmp.push_back(A[index]);
	DFS(index+1,nowk+1,sum+A[index],sumq+A[index]*A[index]);
	tmp.pop_back();
	//   
	DFS(index+1,nowk,sum,sumq);
} 
int main() 
{
//       cin cout        。。。。。。
	int i;
	scanf("%d %d %d",&N,&k,&X);
	for(i=0;i<N;i++)
		scanf("%d",&A[i]);
	DFS(0,0,0,0);
	for(i=0;i<ans.size();i++)
		printf("%d ",ans[i]);	
	return 0;
} 

また、各数を制限せずに1回しか選択できない場合は、選択したエントリを次のように変更する必要があります.

DFS(index,nowk+1,sum+A[index],sumq+A[index]*A[index]);

このように袋小路に遭遇しても選択しない入り口を通じてindex+1を実現する.
広さ優先アルゴリズム
私の理解:もしあなたが知らない人を知りたいなら、直接彼に気まずいかもしれないと言って、私たちはあなたを知っていて、その知らない人を知っていることを通じてあなたと知らない人を知っています.まず私たちはあなたの知っている人(第1階)を遍歴して、すべてのあなたの知っている人がその見知らぬ人を知っているかどうかを検査して、遍歴が終わった後にもしあなたの知っている人がその見知らぬ人を知っていることを検出できないならば、それではすべてのあなたの知っている人が知っている人を遍歴します(第2層)、その見知らぬ人を認識するかどうかを遍歴するたびにチェックし、その見知らぬ人を認識する人が検出されるまで順番に類推します.明らかにこのような検出は随時で、キューの形式に合っています.先進的に先に出て、遍歴しながらチェックするので、キューの形式で実現します.そして、これは階層的な関係で検索されます.テンプレート:

void BFS(ElementType X)               //X   ，     
{
	flag[X]=0;                        //flag           
	queue<ElementType> Q;
	Q.push(X);
	while(!Q.empty()){
		Q.front();                     //      （    ）
		for(             Y){
			if(!flag[Y]){
				flag[Y]=1;
				Q.push(Y);
			/*}else{                ，     if   ，        */
				//  flag[Y]=1      ，          
				//            
			}
		}
		Q.pop();
	}
}

次は私の理解の中の例を通じて理解します.6度の空間理論があります.つまり、あなたと世界の誰とでも6人で連絡を取る必要があります.この理論を証明します.ソーシャルネットワーク図を入力します.(SNS図中の総人数N、相互に認識している2人の対数M及びMが相互に認識している人の番号)は、6度の空間で認識できる人数がSNS図中の総人数に占める割合を出力する.入力サンプル:------------------------出力サンプル:10 9-----------------------1:0.7 1 2----------------------2:0.8 2 3-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------見知らぬ人の考えは同じだ.ポイントは、層毎に遍歴することであり、層数が6に達すると6度の空間の上限となり、各層の終わりを判断するフラグは、現在遍歴されている人(コードの中のde)がその層の最後の人であることである.tmpとlastの役割をよく体得する.

#include 
#include 
#include 
#define maxN 1000
using namespace std;
int G[maxN][maxN];//                 
int visited[maxN]={0};//           
int N,M; 
int BFS(int v)
{
	visited[v]=1;
	int count=1,level=0;//count              ，level       
	queue<int> Q;
	Q.push(v);
	int last=v;//last      
	while(!Q.empty()){
		int de=Q.front();//      
		int tmp;//   for        
		for(int i=0;i<N;i++){
			if(G[de][i]&&!visited[i]){
				Q.push(i);
				visited[i]=1;
				tmp=i; 
				count++; 
			} 
		} 
		if(de==last){//             
			level++;
			last=tmp; 
		}
		if(level==6)
			break;
		Q.pop();
	} 
	return count;
}
void isvisited()//  visited[i]
{
	for(int i=0;i<N;i++)
		visited[i]=0;
}
int main()
{
	scanf("%d %d",&N,&M);
	int i,v,w;//v,w             
	for(i=0;i<M;i++){//      1-N， --
		scanf("%d %d",&v,&w);
		v--;
		w--;
		G[v][w]=1;
		G[w][v]=1;
	}
	int count;//                 
	double rate;//                              
	for(i=0;i<N;i++){
		isvisited();//    ，           visited[i]
		count=BFS(i);
		rate=count*1.0/N;
		printf("%d : %.1f
",i+1,rate);
	} 
}

広さ優先探索の核心は、その要素が直接関連する要素(第1層)のみを巡回し、それらを保存し(第2層)、最後の層まで同じ方法で順次巡回することである.必要に応じて他の操作を追加する.