図の深さ優先検索と広さ優先検索

図の深さ優先探索と広さ優先探索には多くの実用価値があり、私はこの2つのアルゴリズムを書くのに長い時間がかかり、最終的にいくつかの宝物に着いて痛ましい経験をした.
以下にまとめる.
1、図の深さ優先探索は例がなく、この問題自体が再帰的な性質を持っているので、スタックを借りて深さ優先探索の非再帰アルゴリズムを実現してみたが、大きな力を費やしたのか、それとも出てこなかったのか.
問題自体が再帰的性質を有する場合,再帰アルゴリズムを用いることがほとんど最良の方法である.
2、複雑な問題に直面する場合、この問題には他の機能が用いられ、これらの機能を独立した関数として書くことがほとんど最良の方法である.『オペレーティングシステムの設計と実現』から、著者が複雑な問題を処理する際、その中で使用される機能がどのように実現されるかを考慮せず、1つの関数で表すだけで、問題の解答を簡略化し、複雑な問題を解決する方法であることが明らかになった.
3、ワンステップデバッグの威力は無限で、プログラムが多くの場合正常に動作している場合、問題は別の場所に発生します.
図の深さ優先探索アルゴリズムと広さ優先探索アルゴリズムを以下に示す.
/*広さ優先ループアルゴリズム:(類似階層ループ)1、現在の頂点vに最初にアクセスし、その頂点のアクセスフラグvisited[v]=trueを設定します.2、そして、vのそれぞれがアクセスされていない隣接頂点w 1,w 2,...wt,そしてw 1,w 2...,wtのすべてのアクセスされていない隣接頂点.ここでは、先にアクセスした頂点をエンキューし、エンキューする必要があります.3、これらの頂点から、アクセスされていない隣接点にアクセスします.
具体的なアルゴリズム:1、visited配列とbfs配列を宣言して、アクセスの有無とアクセス順序を記録します.2、まずノード0にアクセスします.3、STLの関数ライブラリqueueを使用して、キューのエンキューアウト操作を行う.最初の結点を入隊する.4、キューが空でない場合、キューを出て、要素の最初の隣接点を見つけます.5.隣接点が空でなく、かつアクセスされていない場合、アクセスしてそのノードをエンキューする.6、その接点の次の隣接点を探す.*/

void LinkedGraph::BFSGraph(LinkedGraph *lg)

{

	cout<<"---------      ---------"<<endl;



	bool visited[9];

	int count=0;

	for(int i=0;i<9;i++)	//          

		visited[i]=false;



	int  bfs[9];			//         

	//       

	for(int i=0;i<9;i++)

		bfs[i]=0;

	

	//GraphEdge *q;	//           ，   ,    

	visited[0]=true;

	bfs[0]=0;

	

	//          ，  C++     

	//Queue qg;

	//qg.EnQueue(0);	//    ,       

	queue<int> qg;

	qg.push(0);			//  

	while(!qg.empty())	//           

	{

		int d=qg.front();	//          

		qg.pop();			//  ，        ,   ,  

		int w=lg->getFirstNeighbour(d);	//    d      



		while(w!=-1)	//         

		{

			if(visited[lg->getVerPosition(w)]==false)	//          

			{

				count++	;	//    1

				bfs[count]=w;

				int loc=lg->getVerPosition(w);	//  w    

				visited[loc]=true;

				qg.push(w);	//          

			}

				w=lg->getNextNeighbour(d,w);	//    d      ，           



		}

	}



	//         

	for(int i=0;i<9;i++)

		cout<<bfs[i]<<"--";

	cout<<endl;

}

/*深度優先探索アルゴリズム:(連通図を例に)前回アクセスしたノードを使用するため、補助スタックで表される.1、開始頂点を指定し、各ステップの探査中に、まず現在の頂点にアクセスし、直ちにその頂点のアクセスフラグをtrueに設定します.2.次に、vのすべての隣接点のうち、現在のプローブノードとしてアクセスするものを1つ選択し、3.現在の頂点のすべての隣接点がすでにアクセスされている場合、前回アクセスした頂点をプローブの現在の頂点として取り出す.
*/
プログラムのアルゴリズムはプログラムの注釈に準ずる:

void LinkedGraph::DFSGraph(LinkedGraph *lg,int data)

{

	int i;

	bool visited[9];

	for(i=0;i<9;i++)visited[i]=false;

	DFSGraph(lg,data,visited);			//    

}



void LinkedGraph::DFSGraph(LinkedGraph *lg,int data,bool visited[])

{

	//     

	cout<<v[lg->getVerPosition(data)].data<<" ";	//     

	visited[lg->getVerPosition(data)]=true;			//           true

	int w=lg->getFirstNeighbour(data);	//       

	while(w!=-1)				//     

	{

		if(visited[lg->getVerPosition(w)]==false)	//            

		DFSGraph(lg,w,visited);	//         

		w=lg->getNextNeighbour(data,w);	//       

	}



}

実行結果は次のとおりです.
----------広さ優先遍歴------0-1-2--3--4--5--6--7--8---------図の深さ優先探索------0 1 4 6 2 5 3 8-----終了----------