DFS:スタック(FILO、タイリング、接続リスト)ですべてのパスを参照

BFS:最短距離ナビゲーション、ステップ頂点ナビゲーション、キュー(FIFO、配列、接続リスト)

Backtrakingによる改良

隣接マトリクス:メモリ密集型、トラック速度が速い

隣接リスト:メモリ使用量が少なく、ナビゲーション時間が遅い

Inputのサイズに応じて決定

1. DFS

DFSは、グラフィックにおいて深部を優先的に探索するアルゴリズムである.

DFSはスタック、再帰関数を使用し、具体的な操作手順は以下の通りである.

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

スタックの最上位ノードにアクセスされていない隣接ノードがある場合、アクセス処理はスタックに格納されます.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.

ステップ

は、第2のプロセスが実行されなくなるまで繰り返される.

ex)接続要素を検索

DFS、BFSともに、トップポイント数N、幹線数Eの時の時間複雑度

隣接表:O(N+E)O(N+E)O(N+E)

の隣接行列で示すパターン:O(N 2)O(N^2)O(N 2)

DFS:検索するノードが深ければ深いほど、または左側にあるほど、ガラス

が大きくなります.
💡 **Stack**:FILO、STLライブラリのスタックデータ構造、push()、pop()、empty()、top()などの関数を使用
**Queue*:FIFO、STLライブラリのキューデータ構造、push()、pop()、空()、front()などの関数を利用

スタックのpushアルゴリズム

#define STACK_SIZE 100

int stack[STACK_SIZE];
int top = 1;

void	push(int val)
{
	if (top >= STACK_SIZE - 1)
		return ;
	else
		stack[++top] = val;
}

スタック内のpopアルゴリズム

int	pop(void)
{
	if (top == -1)
		return (0); // empty
	else
		return (stack[top--]);
}

DFSアルゴリズム-再帰

int		graph[MAX_N][MAX_N];
bool	visited[MAX_N];

void	dfs(int node)
{
	visited[node] = true;
	// cout << node << ' ';
	for (int next = 0; next < N; ++next)
	{
		if (visited[next] == false && graph[node][next])
			dfs(next);
	}
}

DFSアルゴリズム-繰り返し

int	graph[MAX_N][MAX_N]
int	stack[STACK_SIZE];
int	top;

void dfs(int node)
{
	int		cur;
	bool	visited[MAX_N] = {false, };

	top = -1;
	stack[++top] = node;
	while (top != -1)
	{
		cur = stack[top--];
		if (visited[cur] == false)
		{
			visited[cur] = true;
			// cout << cur << ' ';
			for (int next = 0; next < N; ++next)
				if (visited[next] = false && graph[cur][next])
					stack[++top] = next;
		}
	}
}

2. BFS

BFSは幅優先探索とも呼ばれ,図形に近いノードから優先探索を開始するアルゴリズムである.

BFSはキューデータ構造を採用し、救済的な操作過程は以下の通りである.

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

キューからノードを取り出し、そのノードの隣接ノードのすべての未アクセスノードをキューに挿入してアクセス処理を行う.

ステップ

は、第2のプロセスが実行されなくなるまで繰り返される.

ex)迷路を探す

キュー内のenqueueアルゴリズム

#define QUEUE_SIZE 100

int	queue[QUEUE_SIZE];
int	front = -1, rear = -1;

void	enqueue(int val)
{
	if (rear >= QUEUE_SIZE - 1)
		return ; // overflow
	else
		queue[++rear] = val;
}

キューのdequeueアルゴリズム

int	dequeue(void)
{
	if (front == rear)
		return (0); // empty
	else
		return (queue[++front]);
}

円形キューのenqueueアルゴリズム

#define QUEUE_SIZE 100

int queue[QUEUE_SIZE];
int size = 0, front = -1, rear = -1;

void enqueue(int val)
{
	if (size >= QUEUE_SIZE)
		return ;
	else
	{
		++size;
		rear = (rear + 1) % QUEUE_SIZE;
		queue[rear] = val;
	}
}

円形キューのdequeueアルゴリズム

int dequeue()
{
	if (size == 0)
		return (0); // empty
	else
	{
		--size;
		front = (front + 1) % QUEUE_SIZE;
		return (queue[front]);
	}
}

BFSアルゴリズム

int	graph[MAX_N][MAX_N]
int	queue[QUEUE_SIZE];
int front, rear;

void	bfs(int node)
{
	int		cur;
	bool	visited[MAX_N] = {false, };

	front = rear = -1;
	queue[++rear] = node;
	while (front != rear)
	{
		cur = queue[++front];
		if (visited[cur] == false)
		{
			visited[cur] = true;
			for (int next = 0; next < N; ++next)
			{
				if (visited[next] == false && graph[cur][next])
					queue[++rear] = next;
			}
		}
	}
}

BFSアルゴリズム：Queueの使用を減らすために改善

int	graph[MAX_N][MAX_N]
int	queue[QUEUE_SIZE];
int front, rear;

void	bfs(int node)
{
	bool	visited[MAX_N] = {false, };
	int		cur;

	front = rear = -1;
	visited[node] = true;
	queue[++rear] = node;
	while (front != rear)
	{
		cur = queue[++front];
		// cout << cur << ' ';
		visited[cur] = true;
		for (int next = 0; next < N; ++next)
		{
			if (visited[next] == false && graph[cur][next])
			{
				visited[next] = true;
				queue[++rear] = next;
			}
		}
	}
}

最短距離計算アルゴリズム，無重みの図形からBFSへ

int	graph[MAX_N][MAX_N];
int dist[MAX_N];
int	queue[QUEUE_SIZE];
int front, rear;

void	bfs(int node)
{
	bool	visited[MAX_N] = {false, };
	int		cur;

	dist[node] = 0;
	front = rear = -1;
	visited[node] = true;
	queue[++rear] = node;
	while (front != rear)
	{
		cur = queue[++front];
		// cout << cur << ' ';
		visited[cur] = true;
		for (int next = 0; next < N; ++next)
		{
			if (visited[next] == false && graph[cur][next])
			{
				dist[next] = dist[cur] + 1;
				visited[next] = true;
				queue[++rear] = next;
		}
	}
}

3. Backtracking

backtrackingは、再帰的に問題を1つずつ解き、現在確認中の状態(ノード)が制限条件(望ましくない)に違反しているかどうかを再帰的に判断するアルゴリズムテクニックであり、そうであれば、その状態(ノード)を除いて次の段階に進む.

Backtrackingでは、現在の状態(ノード)から次の状態(ノード)までのすべての状況を見つけることができ、希望がなければ現在から進むのではなく、以前の状態(ノード)に戻り、次の状態(ノード)をチェックします.再探索を必要としない状態(ノード)を除去することを剪定(剪定)と呼ぶ.

バックグラウンドトラッキングを使用して解決できる問題には、意思決定、最適化、列挙などがあります.

DFSとBackstrackingの違い

を用いて再帰的にプローブを実行する部分では、完全プローブアルゴリズムの再帰/遡及(BackTracking)と同様の態様がある.

遡及(Backtracking)は再帰によってアルゴリズムを解く方法の一つであり、枝切り(Prunning)によって探索を試み、希望がなければさらなる探索を行わず、他の年を探す方法である.

DFSの基本的な目標は、すべてのノードをブラウズすることであるが、場合によってはbacktracking技術を混合して不要なブラウズを改善することができる.

アルゴリズム-遡及