📒DFS(Depth-First Search)

Depth First Searchとは?

韓国語で深さ優先探索を行い、図表を完璧に探索する.
始点から次のBranchまで、このBranchを完璧に探索します.

とくせい

📌特長

再帰関数またはスタックを使用します.

スタックの最上位ノードで、未アクセスのノードがある場合はスタックに入れてアクセス処理を行う.

ノードへのアクセス時にアクセスを確認します.

の深さが深すぎないように、深さ制限を使用します.

📌欠点

の利点
-現在のパス上のノードのみを記憶し、ストレージスペースを効率的に使用できます.

ターゲットノードが深い場合、ノードに到達する時間は少ない.

の欠点
-無害な経路に入ることができます.->深さの制限による保護
-得られた年が最短経路とは限らない->

(複数パス)

使用方法

📌インプリメンテーション

Vectorの使用
[例図表]

#include<iostream>
#include<vector>

using namespace std;

int check[10]
vector<vector<int> > graph(9)

void dfs(int x)
{
    check[x]=1;
    printf("%d ", x);
    
    for(int i=0; i<graph[x].size(); i++){
        	if(check[graph[x][i]]==0){
            	check[graph[x][i]]=1;
                dfs(graph[x][i]);
            }
    }
}

int main(){
	graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);
    
    graph[2].push_back(1);
    graph[2].push_back(7);
    
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    
    graph[4].push_back(3);
    graph[4].push_back(5);
    
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    graph[6].push_back(7);
    
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
    
    graph[8].push_back(1);
    graph[8].push_back(7);
	
    dfs(1);
}

出力結果:1 2 7 6 8

📒BFS(Breadth-First Search)

「Breadth-First Search」とは?

開始ノードにアクセスした後、隣接するすべてのノードにアクセスします.
未アクセスのノードがなくなるまでアクセスします.

とくせい

📌特長

キューを使用して実装します.

ナビゲーション開始ノードをキューに挿入し、アクセス処理を行う.

キューからノードを取り出し、隣接するすべてのノードをキューに挿入します.

最短経路

を探す場合に有利である.

📌欠点

の利点
-出発ノードからターゲットノードまでの最短長を保証します.

の欠点
-パスが長い場合は、ナビゲートするノードの数が増加します.多くの記憶空間が必要です.

解が存在しない場合は、結果を得るには、すべてのグラフィックブラウズ後にする必要があります.

解が存在しない無限図では,終了しない.

使用方法

📌インプリメンテーション

[例図表]

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int check[10]
queue<int> q;
vector<vector<int> > graph(9)

void bfs(int x)
{
 	while(!q.empty()){
    	int x=q.front();
        q.pop();
        printf("%d ", x);
        
        for(int i=0; i<graph[x].size(); i++){
        	if(check[graph[x][i]==0]){
            	q.push(graph[x][i]);
                check[graph[x][i]=1;
			}
        }
	}   
}

int main(){
	graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);
    
    graph[2].push_back(1);
    graph[2].push_back(7);
    
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    
    graph[4].push_back(3);
    graph[4].push_back(5);
    
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    graph[6].push_back(7);
    
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
    
    graph[8].push_back(1);
    graph[8].push_back(7);
	
    q.push(1);
    check[1]=1;
    
    bfs(1);
}

出力結果:1 2 3 8 7 4 6

ϥDFSとBFSの違い

ノードが格納されている場合、BFSはキューDFSを使用してスタックを使用する.

BFSは頂点ベースのアルゴリズムであり、DFSはエッジベースのアルゴリズムである.

DFSはメモリスペースの利用に優れている.

BFSは最適アルゴリズムである.