2021.12.02 TIL


グラフィック構造

これはグラフ構造の配列宣言を理解するためです.すべてのspotにアクセスするロジックを作成するには

アクセスするかどうかを示すブール配列を作成します.アクセスすると、アクセスされるサイトの要素がtrueになります.アクセス[]がfalseのspotであるindex,iを指定し、for文内で再帰呼び出しを行います.3から始まると、
visited[3] = true; print( "visit : 3") ;
i=2, visit( 2, visited, map)
visited[2] = true; print( "visit : 2");
に示すように、0番spotへのアクセスを再帰的に呼び出すと、1番spotへのアクセス後、1には関連するspotは存在しなくなるため、このfor文は終了し、再びi=0 for文、4番spotへのアクセス、[]のすべての要素がtrueであり、関数は終了する.
BFS (Breadth-First Search)
まずqueueに追加されたspotにアクセスし、次にqueueに追加/削除を繰り返し、すべてのspotにアクセスしてコードを記述します.
まず、次のシナリオを宣言します.

visitを定義します.visitは、メンバー変数としてアクセスするかどうかを示すアクセス済みキューを使用します.for文でアクセスされていないspotを検索し、順次アクセスし、キューに対応するspotを追加します.追加されたspotは、while文の条件が満たされる前に繰り返しアクセスします.
DFS (Depth-First Search)
移動してその位置を再移動する検索で最短点を探します.

spot間の距離に重み付け配列を宣言します.最短距離のアルゴリズムを見つけるために.

visit関数を定義します.最小値minは配列重み付け値よりかなり大きい値に設定され、idx minは配列が持つことができないインデックス値の負の値に設定されます.そして、出発地点に一番近い場所を見つけて訪問します.その後、再帰呼び出しにより、すべてのspotにアクセスする前にvisitを繰り返し実行します.上記のコードを作成する場合、直接アクセスできない場合は、すべてのspotがアクセスされず、コードが終了する可能性があります.これに対して,BFSと同じ順序で順次アクセスできるようにする解決策がある.