幅優先探索（Breadth-First Search, BFS）は、グラフやツリー構造を探索する基本的なアルゴリズムの一つですが、「実務で使うイメージが湧かない…」という方も多いかもしれません。
私自身、最近実務でBFSを使う機会があり、改めて理解を深めたいと思い整理しました。今回は、よりイメージしやすいように、ECサイトでよくある「商品カテゴリツリー」を題材にしています。
この記事では、
- BFSの考え方
- どんな場面で使えるのか（実務例）
- 実装例（商品カテゴリツリー）
を、初学者でも実務者でも分かるように解説していきます。
🛒 商品カテゴリのツリー構造とは？
ECサイトでは、商品をカテゴリで分類するのが一般的です。そのカテゴリは次のように**階層構造（ツリー）**になっています：
家電
├── テレビ
│ ├── 液晶テレビ
│ └── 有機ELテレビ
├── 冷蔵庫
└── 洗濯機
この構造をデータで持つには、カテゴリが親子関係を持つ自己リレーション構造になります。
const categoryTree = {
id: 1,
name: "家電",
children: [
{
id: 2,
name: "テレビ",
children: [
{ id: 3, name: "液晶テレビ", children: [] },
{ id: 4, name: "有機ELテレビ", children: [] }
]
},
{ id: 5, name: "冷蔵庫", children: [] },
{ id: 6, name: "洗濯機", children: [] }
]
};
BFSとは？
BFS（幅優先探索）は、あるノードの近くにあるものを先に処理してから、遠くのノードを処理する探索方法です。
ツリー構造で言うと：
-
親 → 子 → 孫 の順に探索します
-
「横に広がるように」見ていくのが特徴です
BFSが必要になる実務シーン
例1: 全カテゴリを「階層順」に表示したい
「親 → 子 → 孫」の順でリストにしたい → BFS！
例2: 特定の階層（例：第2階層）だけ抽出したい
→ BFSならレベル情報を扱える！
例3: 最も近い一致（例：カテゴリ名）を探したい
→ 浅いところから順に探索できるので効率的！
実装してみよう！カテゴリをBFSで並べる
function bfsCategoryList(root) {
const result = [];
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
result.push(node.name);
if (node.children) {
queue.push(...node.children);
}
}
return result;
}
console.log(bfsCategoryList(categoryTree));
// → ["家電", "テレビ", "冷蔵庫", "洗濯機", "液晶テレビ", "有機ELテレビ"]
上から順に親 → 子 → 孫 の順で並びます。これがBFS！
データベースでもBFS？
実際のECサイトなどでは、カテゴリは次のようなシンプルなテーブル構造で管理されていることが多いです。
CREATE TABLE categories (
id INT PRIMARY KEY,
name VARCHAR(255) NOT NULL,
parent_id INT
);
parent_id が親カテゴリの id を示しており、これによって**自己リレーション（親子関係）**が構築されます。
この仕組みでツリー構造は表現できますが、SQLの ORDER BY では「親→子→孫」のような階層順には並びません。
そのため、実務では以下のような手順でアプリケーション側にてBFSの処理を行います：
データベースからカテゴリを全件取得
プログラム内でツリー構造に組み立てる
BFSで親から順に探索・並び替え
こうすることで、UIで自然な階層順のリスト表示やメニュー展開が可能になります。
BFSとORDER BYの違いは？
| 比較 | BFS | ORDER BY |
|---|---|---|
| 並び方 | 親→子→孫（階層順） | 値順（名前順、ID順） |
| 目的 | 階層表示・UI順序 | 並び替え表示・一覧表示 |
| 必要な情報 | parentId（自己リレーション） | 並びたいカラムだけ |
まとめ
| ポイント | 内容 |
|---|---|
| BFSとは？ | ツリー構造を横に広がる順に探索する手法 |
| 実務で使う場面 | カテゴリ表示、階層メニュー、浅い順の検索など |
| 実装方法 | JavaScriptでキュー（Queue）を使って処理 |
| データ構造 | 同じCategoryモデルの自己リレーションでOK |