深さ優先探索 (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);