深さ優先探索 (Depth-First Search, DFS) と 幅優先探索 (Breadth-First Search, BFS)
C
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// グラフの隣接リストのノード
struct Node {
int vertex;
struct Node* next;
};
// グラフ
struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};
// 新しいノードの生成
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// グラフの生成
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
graph->visited = (int*)malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// エッジの追加
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// DFS
void DFS(struct Graph* graph, int vertex) {
struct Node* adjList = graph->adjLists[vertex];
struct Node* temp = adjList;
graph->visited[vertex] = 1;
printf("Visited %d\n", vertex);
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
// BFS
void BFS(struct Graph* graph, int startVertex) {
int queue[MAX];
int front = 0;
int rear = -1;
graph->visited[startVertex] = 1;
queue[++rear] = startVertex;
while (front <= rear) {
int currentVertex = queue[front++];
printf("Visited %d\n", currentVertex);
struct Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
queue[++rear] = adjVertex;
graph->visited[adjVertex] = 1;
}
temp = temp->next;
}
}
}
int main() {
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printf("DFS:\n");
DFS(graph, 0);
// Reset visited array for BFS
for (int i = 0; i < 4; i++) {
graph->visited[i] = 0;
}
printf("BFS:\n");
BFS(graph, 0);
return 0;
}
C++
#include <iostream>
#include <list>
#include <stack>
#include <queue>
using namespace std;
class Graph {
int V;
list<int>* adj;
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int v);
void BFS(int v);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFS(int v) {
vector<bool> visited(V, false);
stack<int> stack;
stack.push(v);
while (!stack.empty()) {
v = stack.top();
stack.pop();
if (!visited[v]) {
cout << "Visited " << v << endl;
visited[v] = true;
}
for (auto i = adj[v].rbegin(); i != adj[v].rend(); ++i) {
if (!visited[*i]) {
stack.push(*i);
}
}
}
}
void Graph::BFS(int v) {
vector<bool> visited(V, false);
queue<int> queue;
visited[v] = true;
queue.push(v);
while (!queue.empty()) {
v = queue.front();
queue.pop();
cout << "Visited " << v << endl;
for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
queue.push(*i);
}
}
}
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "DFS:" << endl;
g.DFS(2);
cout << "BFS:" << endl;
g.BFS(2);
return 0;
}
C#
using System;
using System.Collections.Generic;
class Graph {
private readonly int V;
private readonly List<int>[] adj;
public Graph(int V) {
this.V = V;
adj = new List<int>[V];
for (int i = 0; i < V; i++) {
adj[i] = new List<int>();
}
}
public void AddEdge(int v, int w) {
adj[v].Add(w);
}
public void DFS(int v) {
bool[] visited = new bool[V];
Stack<int> stack = new Stack<int>();
stack.Push(v);
while (stack.Count != 0) {
v = stack.Pop();
if (!visited[v]) {
Console.WriteLine("Visited " + v);
visited[v] = true;
}
foreach (var i in adj[v]) {
if (!visited[i]) {
stack.Push(i);
}
}
}
}
public void BFS(int v) {
bool[] visited = new bool[V];
Queue<int> queue = new Queue<int>();
visited[v] = true;
queue.Enqueue(v);
while (queue.Count != 0) {
v = queue.Dequeue();
Console.WriteLine("Visited " + v);
foreach (var i in adj[v]) {
if (!visited[i]) {
visited[i] = true;
queue.Enqueue(i);
}
}
}
}
}
class Program {
static void Main() {
Graph g = new Graph(4);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(2, 0);
g.AddEdge(2, 3);
g.AddEdge(3, 3);
Console.WriteLine("DFS:");
g.DFS(2);
Console.WriteLine("BFS:");
g.BFS(2);
}
}
Java
import java.util.*;
class Graph {
private final int V;
private final LinkedList<Integer>[] adj;
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList<>();
}
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void DFS(int v) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(v);
while (!stack.isEmpty()) {
v = stack.pop();
if (!visited[v]) {
System.out.println("Visited " + v);
visited[v] = true;
}
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
stack.push(n);
}
}
}
}
void BFS(int v) {
boolean[] visited = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[v] = true;
queue.add(v);
while (!queue.isEmpty()) {
v = queue.poll();
System.out.println("Visited " + v);
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("DFS:");
g.DFS(2);
System.out.println("BFS:");
g.BFS(2);
}
}
Python
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, v):
visited = set()
stack = [v]
while stack:
node = stack.pop()
if node not in visited:
print(f"Visited {node}")
visited.add(node)
stack.extend(reversed(self.graph[node]))
def bfs(self, v):
visited = set()
queue = deque([v])
visited.add(v)
while queue:
node = queue.popleft()
print(f"Visited {node}")
for neighbour in self.graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("DFS:")
g.dfs(2)
print("BFS:")
g.bfs(2)
JavaScript
class Graph {
constructor() {
this.adjList = new Map();
}
addEdge(v, w) {
if (!this.adjList.has(v)) this.adjList.set(v, []);
if (!this.adjList.has(w)) this.adjList.set(w, []);
this.adjList.get(v).push(w);
}
dfs(v) {
const visited = new Set();
const stack = [v];
while (stack.length) {
const node = stack.pop();
if (!visited.has(node)) {
console.log(`Visited ${node}`);
visited.add(node);
stack.push(...this.adjList.get(node).reverse());
}
}
}
bfs(v) {
const visited = new Set();
const queue = [v];
visited.add(v);
while (queue.length) {
const node = queue.shift();
console.log(`Visited ${node}`);
for (const neighbour of this.adjList.get(node)) {
if (!visited.has(neighbour)) {
visited.add(neighbour);
queue.push(neighbour);
}
}
}
}
}
const g = new Graph();
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
console.log("DFS:");
g.dfs(2);
console.log("BFS:");
g.bfs(2);
この記事が気に入ったらサポートをしてみませんか?