幅優先探索（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 bfsCategoryListWithLevel(root) {
const result = [];
const queue = [{ node: root, level: 0 }];
while (queue.length > 0) {
const { node, level } = queue.shift();
result.push({ name: node.name, level });
if (node.children) {
for (const child of node.children) {
queue.push({ node: child, level: level + 1 });
}
}
}
return result;
}
console.log(bfsCategoryListWithLevel(categoryTree));
// → [
// { name: "家電", level: 0 },
// { name: "テレビ", level: 1 },
// { name: "冷蔵庫", level: 1 },
// { name: "洗濯機", level: 1 },
// { name: "液晶テレビ", level: 2 },
// { name: "有機ELテレビ", level: 2 }
// ]
「親 → 全ての子（同階層）→ 全ての孫」の順で並びます。
データベースでもBFS？
実際のECサイトなどでは、カテゴリは次のようなシンプルなテーブル構造で管理されていることが多いです。
CREATE TABLE categories (
id INT PRIMARY KEY,
name VARCHAR(255) NOT NULL,
parent_id INT
);
parent_id が親カテゴリの id を示しており、これによって自己リレーション（親子関係）が構築されます。
この仕組みでツリー構造は表現できますが、SQLの ORDER BY は単純なカラムの並び順（例えば id や name）を決めるものであり、parent_id に基づく階層順（親→子→孫）には並びません。
そのため、実務では以下のような手順でカテゴリの階層順処理を行います：
-
データベースからカテゴリを全件取得する（id / parent_id 形式のフラットデータ）
-
アプリケーション側で必要に応じてツリー構造に組み立てる
-
ツリー構造またはフラットデータをBFSで親から順に探索・並び替える
こうすることで、UI上で自然な階層順のリスト表示やメニュー展開が可能になります。
BFSとORDER BYの違いは？
| 比較 | BFS | ORDER BY |
|---|---|---|
| 並び方 | 親→子→孫（階層順） | 値順（名前順、ID順） |
| 目的 | 階層表示・UI順序 | 並び替え表示・一覧表示 |
| 必要な情報 | parentId（自己リレーション） | 並びたいカラムだけ |
まとめ
| ポイント | 内容 |
|---|---|
| BFSとは？ | ツリー構造を横に広がる順に探索する手法 |
| 実務で使う場面 | カテゴリ表示、階層メニュー、浅い順の検索など |
| 実装方法 | JavaScriptでキュー（Queue）を使って処理 |
| データ構造 | 同じCategoryモデルの自己リレーションでOK |
株式会社シンシア
株式会社シンシアでは、実務未経験のエンジニアの方や学生エンジニアインターンを採用し一緒に働いています。
※ シンシアにおける働き方の様子はこちら
シンシアでは、年間100人程度の実務未経験の方が応募し技術面接を受けます。
その経験を通し、実務未経験者の方にぜひ身につけて欲しい技術力（文法）をここでは紹介していきます。