目次
概要:
今日のトピックは、グラフ探索アルゴリズムである深さ優先探索 (DFS) と幅優先探索 (BFS) についてです。これらの探索アルゴリズムは、グラフ構造のデータ処理やパス検索、連結性の判定など、多くのアプリケーションで使用されます。
基本概念の説明:
深さ優先探索 (DFS)
グラフの探索において、まず深く進み、行き止まりに達したらバックトラックして他の経路を探索します。これにより、ある頂点から始めて全ての頂点に到達する方法を効率的に探索できます。
幅優先探索 (BFS)
最初に最も近い頂点を全て探索し、その後に次のレベルの頂点を探索します。これにより、始点から最短経路を見つけるのに適した方法です。
各言語でのサンプルコード:
Python:
Python:
# 深さ優先探索 (DFS)
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for next in graph[start] - visited:
dfs(graph, next, visited)
# 幅優先探索 (BFS)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
C#:
using System;
using System.Collections.Generic;
// 深さ優先探索 (DFS)
void DFS(Dictionary<int, List<int>> graph, int start, HashSet<int> visited)
{
if (!visited.Contains(start))
{
Console.Write(start + " ");
visited.Add(start);
foreach (var neighbor in graph[start])
{
DFS(graph, neighbor, visited);
}
}
}
// 幅優先探索 (BFS)
void BFS(Dictionary<int, List<int>> graph, int start)
{
var visited = new HashSet<int>();
var queue = new Queue<int>();
visited.Add(start);
queue.Enqueue(start);
while (queue.Count > 0)
{
var vertex = queue.Dequeue();
Console.Write(vertex + " ");
foreach (var neighbor in graph[vertex])
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
}
C++:
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
// 深さ優先探索 (DFS)
void DFS(std::vector<std::vector<int>>& graph, int start, std::set<int>& visited)
{
visited.insert(start);
std::cout << start << " ";
for (int neighbor : graph[start])
{
if (visited.find(neighbor) == visited.end())
{
DFS(graph, neighbor, visited);
}
}
}
// 幅優先探索 (BFS)
void BFS(std::vector<std::vector<int>>& graph, int start)
{
std::set<int> visited;
std::queue<int> queue;
visited.insert(start);
queue.push(start);
while (!queue.empty())
{
int vertex = queue.front();
queue.pop();
std::cout << vertex << " ";
for (int neighbor : graph[vertex])
{
if (visited.find(neighbor) == visited.end())
{
visited.insert(neighbor);
queue.push(neighbor);
}
}
}
}
Java:
import java.util.*;
// 深さ優先探索 (DFS)
void DFS(Map<Integer, List<Integer>> graph, int start, Set<Integer> visited)
{
if (!visited.contains(start))
{
System.out.print(start + " ");
visited.add(start);
for (int neighbor : graph.get(start))
{
DFS(graph, neighbor, visited);
}
}
}
// 幅優先探索 (BFS)
void BFS(Map<Integer, List<Integer>> graph, int start)
{
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty())
{
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int neighbor : graph.get(vertex))
{
if (!visited.contains(neighbor))
{
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
JavaScript:
// 深さ優先探索 (DFS)
function dfs(graph, start, visited = new Set()) {
if (!visited.has(start)) {
console.log(start);
visited.add(start);
for (let neighbor of graph[start]) {
dfs(graph, neighbor, visited);
}
}
}
// 幅優先探索 (BFS)
function bfs(graph, start) {
let visited = new Set();
let queue = [start];
visited.add(start);
while (queue.length > 0) {
let vertex = queue.shift();
console.log(vertex);
for (let neighbor of graph[vertex]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
各言語の解説:
| 言語 | 特徴 | メリット | デメリット |
|---|---|---|---|
| Python | 簡潔で柔軟 | コードが読みやすい | 実行速度が遅い |
| C# | 型安全で.NETと統合 | 高いパフォーマンス | クロスプラットフォームの柔軟性に欠ける |
| C++ | 高速処理が可能 | メモリ管理が細かい | コードが複雑 |
| Java | プラットフォームに依存しない | 大規模開発に最適 | メモリ消費が多い |
| JavaScript | Web開発に適している | 非同期処理が簡単 | ブラウザ依存が強い |
まとめ:
深さ優先探索 (DFS) と幅優先探索 (BFS) は、グラフ探索の基本であり、それぞれ異なる特性を持っています。DFSは深く探索するのに適しており、BFSは最短経路の発見に適しています。次に、これらの探索アルゴリズムをどのように応用できるかについて学習しましょう。
コメント