DFS/BFSアルゴリズム

!!个人的に勉强するために间违った内容があるかもしれませんから!!間違った内容があれば、いつでも指摘してください.
DFSとBFSアルゴリズム
その名の通り深さ優先はDFS,幅優先はBFSアルゴリズムである.
これは符号化テストでよく発生する問題で、明らかにしたほうがいい.

DFS

이미지 출처: 위키피디아

写真の数字はアクセスの順番です.
ご覧のように、1つのノードで隣の兄弟ノードを検索するのではなく、まずサブノードを検索します.サブノードがなくなるまで移動した後、兄弟ノードをナビゲートし、この手順を繰り返し、すべてのノードに移動する方法は深さ優先ナビゲーションです.名前のように、最も深いノードを探索した後、隣のノードを探索する方法です.
私の場合、DFSを実現する際に主にこの方法を使用します.

/*
start	시작 노드 
n	노드의 개수
visit	방문 여부를 저장하는 bool 배열
arr	노드간에 간선이 존재하는지를 표시(1인 경우 간선 존재)
*/
void DFS(int start){
	visit[start] = true;
    for(int i=0; i<n; i++){
    	if(arr[start][i] == 1 && !visit[i])
        	DFS(i);
	}
}

BFS

이미지 출처: 위키피디아

写真の数字はアクセスの順番です.
DFSとは逆にBFSはまず兄弟ノードにアクセスする.
すべての兄弟ノードをブラウズした後、サブノードを繰り返しブラウズし、すべてのノードをブラウズする方法はBFS方式である.コードで実装する場合は、キューを使用して現在のノードに関連するすべてのノードを配置し、1つずつポップアップしてナビゲートします.

/*
start	시작 노드
n	노드의 개수
visit	방문여부를 저장하는 bool 배열
arr	간선 존재 여부(1이면 간선 존재)
queue	현재 노드에 연결된 모든 노드들을 담아줄 큐
*/
void BFS(int start){
	queue<int> q;
    q.push(start);
    visit[start] = true;
    
    while(!q.empty()){
    	int tmp = q.front();
        q.pop();
        for(int i=0; i<n; i++){
        	if(arr[start][i] == 1 && !visit[i]){
            	q.push(i);
                visit[i] = true
            }
        }
    }
}