2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 15

エアークローゼット Advent Calendar 2025

@same_ac
in

深さ優先探索で分散データを変換する

2
Last updated at Posted at 2025-12-15

みなさまこんにちは！エアークローゼットエアークローゼットでエンジニアをしているSameです。

この記事はエアークローゼット Advent Calendar 2025 の15日目の記事です。

|> 要約: 深さ優先探索（DFS）を使用して複雑で相互接続されたデータを自動的にマッピングする方法 - 分散したAPIレスポンスを数秒で完全なネットワークマップに変換します。

🎯 問題：データが繋がっているのに見えづらい

お気に入りのTV、映画、アニメシリーズに関連する全作品を把握しようとしている場面を想像してください。APIを確認すると、2つの続編があることがわかります。しかし、その続編のスピンオフは？その続編の続編は？気づけば何十ものページをクリックし、手動で関係性を追跡し、必然的に見落としが発生します。

💡 これはメディアシリーズだけの問題ではありません。 ソフトウェアの依存関係をマッピングする場合でも、プロフェッショナルネットワークを探索する場合でも、相互接続されたシステムを分析する場合でも、同じ課題に直面します：ほとんどのデータソースは直接的な関係性しか表示しません。

全体像を把握するには、すべての接続を再帰的に探索する必要があります。手動で行うと、退屈でエラーが発生しやすいプロセスです。

良いニュースは？ エレガントなアルゴリズム的解決策があります：深さ優先探索（DFS: Depth-First Search）。

🔎 いつこの問題が発生するのか？

この課題は、データが以下の特徴を持つグラフ構造を形成している場合に発生します：

📊 3つの主要な指標：

  1. 🔗 エンティティが他のエンティティとの関係を持つ

    • 単純な階層ではなく、サイクル（A → B → C → A）を持つ相互接続されたネットワーク

  2. 🌐 データが分散している

    • 各ノードの情報は異なる場所に存在し、個別のAPI呼び出しやクエリが必要

  3. ❓ 深さが不明

    • 関係性の連鎖が2レベルの深さなのか20レベルの深さなのかわからない

📦 実例：npm依存関係

npm パッケージの依存関係を考えてみてください。Express.js をインストールすると、数十のパッケージに依存しています。それぞれがさらに他のパッケージに依存しています。完全な依存関係ツリーには数百のパッケージが含まれる可能性がありますが、npm info express は最初のレベルしか表示しません。

⚠️ API の問題：1レベルの深さしかない

典型的なAPIレスポンスは次のようになります：

{
  "id": 101,
  "name": "Item A",
  "related": [
    { "id": 102, "relationship": "sequel" },
    { "id": 103, "relationship": "spin-off" }
  ]
}

Item A が Item 102 と 103 に接続していることはわかります。しかし、それらは何に接続しているのでしょうか？

🔄 手動プロセス：

  1. ✅ Item 102 に対して別のAPI呼び出しを行う
  2. ✅ Item 103 に対しても同様に行う
  3. ✅ それらが接続しているものに対しても同様に行う
  4. ✅ すべてのブランチを探索するまで続ける
  5. ✅ 無限ループを避けるために、既に訪問したものを追跡する

⚡ これがまさにDFSが自動化するものです。

🎯 解決策：深さ優先探索

深さ優先探索は、バックトラックする前に各ブランチを可能な限り深く探索するグラフトラバーサルアルゴリズムです。この問題に最適な理由は次のとおりです：

┌─────────────────────────────────────────|
│  DFSがこの問題に最適な理由                  |
├─────────────────────────────────────────|
│ ✅ 未知の深さを処理                        |
│    → 接続がなくなるまで続ける               |
│                                         |  
│ ✅ 重複を回避                             | 
│    → 訪問済みノードを追跡して               |
│      無限ループを防ぐ                      |
│                                         |  
│ ✅ 非同期操作と連携                        |
│    → 各ステップでAPI呼び出しを              |
│      await できる                        |  
│                                         |   
│ ✅ 自然な再帰構造                          | 
│    → 問題の本質的な構造と一致               |
└─────────────────────────────────────────┘

🎬 仕組み：ビジュアルウォークスルー

ノードAから接続をマッピングしてみましょう：

ステップ1：ノードAを訪問

     [A]
    /   \
   ?     ?
  • 🔍 ノードA に対してAPI呼び出しを行う
  • 📌 接続を発見：[B, C]
  • ✓ A を訪問済みとしてマーク
  • 📝 マップに追加：A → [B, C]
┌──────────────────────────┐
│ 訪問済み: [A]            │
│ 探索予定: [B, C]         │
│ マップ: { A: [B, C] }    │
└──────────────────────────┘

ステップ2：ノードBを訪問（まず深く！）

     [A]
    /   \
  [B]    C
  / \
 ?   ?

💡 ここでDFSがその名前の由来となります。 次にCを探索する代わりに、すぐにBの接続に深く潜ります。

  • 🔍 ノードB に対してAPI呼び出しを行う
  • 📌 接続を発見：[D, E]
  • ✓ B を訪問済みとしてマーク
  • 📝 マップに追加：B → [D, E]
┌──────────────────────────┐
│ 訪問済み: [A, B]         │
│ 探索予定: [D, E, C]      │
│ マップ: {                │
│   A: [B, C],             │
│   B: [D, E]              │
│ }                        │
└──────────────────────────┘

ステップ3：ノードDを訪問（サイクルの処理）

     [A] ←─┐
    /   \   │
  [B]    C  │
  / \       │
[D] [E]     │
 └──────────┘
  • 🔍 ノードD に対してAPI呼び出しを行う
  • 📌 接続を発見：[A] — しかし、既にAは訪問済み！
  • ✓ D を訪問済みとしてマーク
  • 📝 マップに追加：D → [A]
  • 🚫 Aの再訪問をスキップ（無限ループを防ぐ）

🔄 サイクルが検出され処理されました！ これは相互接続されたデータでの無限ループを防ぐために重要です。

最終結果：完全なネットワークマップ

このプロセスを続けます—E、そして最後にCを訪問—到達可能なすべてのノードが探索されるまで。

┌─────────────────────────────────┐
│   完全な隣接リスト              │
├─────────────────────────────────┤
│   A: [B, C]                     │
│   B: [D, E]                     │
│   D: [A]  ← サイクル            │
│   E: [C]                        │
│   C: [B]  ← サイクル            │
└─────────────────────────────────┘

分散したAPIレスポンスを、ネットワーク全体を表す完全な隣接リストに変換しました！

🔄 変換：ビフォー＆アフター

📉 ビフォー：分散データ

❌ 手動でリクエストする必要がある個別のAPIレスポンス
❌ ネットワーク全体の概要がない
❌ いつ終わりに到達したかわからない
❌ 接続を見落としやすい

📈 アフター：完全なマップ

✅ ネットワーク全体を一目で確認可能
✅ 「AからEへのパスは？」といった質問に即座に回答できる
✅ クラスターとパターンを識別
✅ 完全なグラフを視覚化または分析

🛠️ 実世界での応用

Use Case #1: 📦 パッケージ依存関係

問題: プロジェクトの依存関係をセキュリティ脆弱性のために監査する場合、推移的依存関係を含む、インストールされるすべてのパッケージを知る必要があります。

async function mapAllDependencies(packageName) {
  const dependencyMap = new Map();

  async function explore(pkg) {
    if (dependencyMap.has(pkg)) return; // 訪問済み

    const deps = await fetchDependencies(pkg); // API呼び出し
    dependencyMap.set(pkg, deps);

    for (let dep of deps) {
      await explore(dep); // 再帰的DFS
    }
  }

  await explore(packageName);
  return dependencyMap;
}

結果: ✨ すべてのパッケージを示す完全な依存関係ツリーにより、セキュリティ監査、ライセンスコンプライアンスチェック、バンドルサイズ最適化が可能になります。

Use Case #2: 👥 プロフェッショナルネットワーク発見

問題: 会社Xの誰かに連絡を取りたいが、直接的なネットワークにいない場合。誰が紹介してくれるでしょうか？

LinkedIn スタイルの接続に対してDFSを使用することで、拡張ネットワークをマッピングし、次のようなパスを発見できます：

あなた → 友人A → 同僚B → ターゲット人物
         ↓
         友人C → ターゲット人物（より短いパス！）

結果: ✨ これにより、就職活動、営業、ネットワーキングのためのウォーム紹介が可能になります。

Use Case #3: 🎬 アニメフランチャイズのマッピング

問題: アニメシリーズには、前日譚、続編、サイドストーリー、スピンオフにまたがる複雑な関係性があることがよくあります。APIの例として、アニメデータベースサイトのMyAnimeListの場合は直接的な関係性のみを表示しますが、フランチャイズには10以上の相互接続されたタイトルが含まれる可能性があります。

const adjacencyRelatedList = new Map();

async function get_related(anime_id) {
  console.log('探索中:', anime_id);

  const related_set = await api_get_related(anime_id); // API呼び出し
  adjacencyRelatedList.set(anime_id, related_set);

  for (let related_id of related_set) {
    if (!adjacencyRelatedList.has(related_id)) {
      await get_related(related_id); // 再帰的DFS
    }
  }
}

await get_related(24405); // 1つのアニメから開始
// 完全なフランチャイズマップが adjacencyRelatedList に格納されました！

結果: ✨ 最適な視聴順序を示し、あまり知られていない関連作品を発見する完全なフランチャイズツリー。

🤔 いつこのアプローチを使うべきか？

✅ DFSを使用する場合：

  • 🔗 データが相互接続されたエンティティを持つグラフ構造を形成している
  • 🌐 関係性が異なるソース/API呼び出しに分散している
  • ❓ 深さが不明で、完了するまで探索する必要がある
  • 📊 分析または視覚化のために完全な全体像が必要

❌ DFSを使用しない場合：

  • 📄 データが既にフラット（単純なリスト）
  • 📦 すべてのデータが1つのレスポンスで利用可能
  • 1️⃣ 直接的な関係性（1レベル）のみが必要

⚙️ 重要な考慮事項：

🚦 APIレート制限

DFSは多くのAPI呼び出しを行う可能性があります。スロットリング、遅延、キャッシングを実装してください。

// API呼び出し間に遅延を追加
await new Promise(resolve => setTimeout(resolve, 100));

⚡ パフォーマンス

10,000以上のノードを持つグラフの場合、幅優先探索またはページネーションを検討してください。

🔄 サイクル

無限ループを防ぐために、Set または Map を使用して訪問済みノードを常に追跡してください。

const visited = new Set();
if (visited.has(nodeId)) return; // 重要なチェック！
visited.add(nodeId);

🎨 パターン：再利用可能なテンプレート

グラフ構造化されたデータに適応できる基本的なパターンは次のとおりです：

const map = new Map();

async function explore(nodeId) {
  if (map.has(nodeId)) return; // 訪問済みチェック

  const connections = await fetchData(nodeId); // API呼び出し
  map.set(nodeId, connections); // 保存

  for (let conn of connections) {
    await explore(conn); // 再帰
  }
}

await explore(startingNodeId);
// map に完全なネットワークが含まれています

💾 プロのヒント: このパターンはどのドメインでも機能します - fetchData 関数を入れ替えるだけです！

🎓 結論

データが分散し相互接続されている場合、深さ優先探索は不完全な断片を完全で実用的なマップに変換します。依存関係の監査、ネットワークの探索、メディアフランチャイズのマッピングなど、DFSは断片化されたデータの隠れた接続を明らかにするエレガントなソリューションを提供します。

🚀 次回、関連アイテムを手動でクリックしている自分に気づいたら、考えてみてください: DFSでこの探索を自動化し、数秒で完全な全体像を得られないだろうか？

📝 注記: この記事は、MyAnimeList API を使用したフランチャイズ関係性マッピングの実際の実装に基づいています。

English version

How Depth-First Search Reveals Hidden Connections in Fragmented Data

TL;DR: How to automatically map complex, interconnected data using Depth-First Search (DFS) - transforming scattered API responses into complete network maps.

🎯 The Problem: When Data is Connected But Hard to See

Imagine you're trying to understand all the anime series related to your favorite show. You check an API and find it has two sequels. But what about those sequels' spin-offs? And their prequels? Suddenly, you're clicking through dozens of pages, manually tracking relationships, and inevitably missing connections.

💡 This isn't just an anime problem. Whether you're mapping software dependencies, exploring professional networks, or analyzing any interconnected system, you face the same challenge: most data sources only show you direct relationships.

To see the complete picture, you need to recursively explore every connection—a tedious, error-prone process when done manually.

The good news? There's an elegant algorithmic solution: Depth-First Search (DFS).

🔎 When Does This Problem Appear?

This challenge emerges whenever your data forms a graph structure with these characteristics:

📊 Three Key Indicators:

  1. 🔗 Entities have relationships to other entities

    • Not simple hierarchies, but interconnected networks that can have cycles (A → B → C → A)

  2. 🌐 Data is distributed

    • Each node's information lives in a different location, requiring separate API calls or queries

  3. ❓ Depth is unknown

    • Relationship chains might be 2 levels deep or 20 levels deep

📦 Real Example: npm Dependencies

Think about npm package dependencies. When you install Express.js, it depends on dozens of packages. Each of those depends on others. The complete dependency tree can include hundreds of packages, but npm info express only shows you the first level.

⚠️ The API Problem: Only One Level Deep

Here's what a typical API response looks like:

{
  "id": 101,
  "name": "Item A",
  "related": [
    { "id": 102, "relationship": "sequel" },
    { "id": 103, "relationship": "spin-off" }
  ]
}

You know Item A connects to Items 102 and 103. But what do they connect to?

🔄 The Manual Process:

  1. ✅ Make another API call for Item 102
  2. ✅ Then for Item 103
  3. ✅ Then for whatever those connect to
  4. ✅ Continue until you've explored every branch
  5. ✅ Track what you've already visited to avoid infinite loops

⚡ This is exactly what DFS automates.

🎯 The Solution: Depth-First Search

Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Here's why it's perfect for this problem:

┌─────────────────────────────────────────┐
│  Why DFS is Perfect for This Problem   │
├─────────────────────────────────────────┤
│ ✅ Handles unknown depth                │
│    → Keeps going until no more          │
│      connections                        │
│                                         │
│ ✅ Avoids duplicates                    │
│    → Tracks visited nodes to prevent    │
│      infinite loops                     │
│                                         │
│ ✅ Works with async operations          │
│    → Can await API calls at each step   │
│                                         │
│ ✅ Natural recursive structure          │
│    → Matches the problem's inherent     │
│      structure                          │
└─────────────────────────────────────────┘

🎬 How It Works: A Visual Walkthrough

Let's map connections starting from Node A:

Step 1: Visit Node A

     [A]
    /   \
   ?     ?
  • 🔍 Make API call for Node A
  • 📌 Discover connections: [B, C]
  • ✓ Mark A as visited
  • 📝 Add to our map: A → [B, C]
┌──────────────────────────┐
│ Visited: [A]             │
│ To Explore: [B, C]       │
│ Map: { A: [B, C] }       │
└──────────────────────────┘

Step 2: Visit Node B (Go Deep First!)

     [A]
    /   \
  [B]    C
  / \
 ?   ?

💡 This is where DFS gets its name. Instead of exploring C next, we immediately dive deep into B's connections.

  • 🔍 Make API call for Node B
  • 📌 Discover connections: [D, E]
  • ✓ Mark B as visited
  • 📝 Add to map: B → [D, E]
┌──────────────────────────┐
│ Visited: [A, B]          │
│ To Explore: [D, E, C]    │
│ Map: {                   │
│   A: [B, C],             │
│   B: [D, E]              │
│ }                        │
└──────────────────────────┘

Step 3: Visit Node D (Handling Cycles)

     [A] ←─┐
    /   \   │
  [B]    C  │
  / \       │
[D] [E]     │
 └──────────┘
  • 🔍 Make API call for Node D
  • 📌 Discover connections: [A] — but we've already visited A!
  • ✓ Mark D as visited
  • 📝 Add to map: D → [A]
  • 🚫 Skip revisiting A (preventing infinite loops)

🔄 Cycle detected and handled! This is crucial for preventing infinite loops in interconnected data.

Final Result: Complete Network Map

We continue this process—visiting E, then finally C—until every reachable node has been explored.

┌─────────────────────────────────┐
│   Complete Adjacency List       │
├─────────────────────────────────┤
│   A: [B, C]                     │
│   B: [D, E]                     │
│   D: [A]  ← cycle               │
│   E: [C]                        │
│   C: [B]  ← cycle               │
└─────────────────────────────────┘

We've transformed scattered API responses into a complete adjacency list representing the entire network!

🔄 The Transformation: Before & After

📉 Before: Scattered Data

❌ Individual API responses you must manually request
❌ No overview of the complete network
❌ Don't know when you've reached the end
❌ Easy to miss connections

📈 After: Complete Map

✅ Entire network visible at a glance
✅ Can answer questions like "what's the path from A to E?" instantly
✅ Identify clusters and patterns
✅ Visualize or analyze the complete graph

🛠️ Real-World Applications

Use Case #1: 📦 Package Dependencies

Problem: When auditing a project's dependencies for security vulnerabilities, you need to know every package that will be installed—including transitive dependencies.

async function mapAllDependencies(packageName) {
  const dependencyMap = new Map();

  async function explore(pkg) {
    if (dependencyMap.has(pkg)) return; // Already visited

    const deps = await fetchDependencies(pkg); // API call
    dependencyMap.set(pkg, deps);

    for (let dep of deps) {
      await explore(dep); // Recursive DFS
    }
  }

  await explore(packageName);
  return dependencyMap;
}

Result: ✨ Complete dependency tree showing all packages, enabling security audits, license compliance checks, and bundle size optimization.

Use Case #2: 👥 Professional Network Discovery

Problem: You want to reach someone at Company X but they're not in your direct network. Who can introduce you?

Using DFS on LinkedIn-style connections, you can map your extended network and discover paths like:

You → Friend A → Colleague B → Target Person
      ↓
      Friend C → Target Person (shorter path!)

Result: ✨ This enables warm introductions for job hunting, sales, and networking.

Use Case #3: 🎬 Anime Franchise Mapping

Problem: Anime series often have complex relationships spanning prequels, sequels, side stories, and spin-offs. The MyAnimeList API only shows direct relationships, but a franchise can include 10+ interconnected titles.

const adjacencyRelatedList = new Map();

async function get_related(anime_id) {
  console.log('Exploring:', anime_id);

  const related_set = await api_get_related(anime_id); // API call
  adjacencyRelatedList.set(anime_id, related_set);

  for (let related_id of related_set) {
    if (!adjacencyRelatedList.has(related_id)) {
      await get_related(related_id); // Recursive DFS
    }
  }
}

await get_related(24405); // Start from one anime
// Complete franchise map is now in adjacencyRelatedList!

Result: ✨ Complete franchise tree showing optimal viewing order and discovering lesser-known related works.

🤔 When Should You Use This Approach?

✅ Use DFS When:

  • 🔗 Data forms a graph structure with interconnected entities
  • 🌐 Relationships are scattered across different sources/API calls
  • ❓ Depth is unknown and you need to explore until completion
  • 📊 You need the complete picture for analysis or visualization

❌ Don't Use DFS When:

  • 📄 Data is already flat (simple lists)
  • 📦 All data is available in one response
  • 1️⃣ You only need direct relationships (one level)

⚙️ Key Considerations:

🚦 API Rate Limits

DFS can make many API calls. Implement throttling, delays, and caching.

// Add delay between API calls
await new Promise(resolve => setTimeout(resolve, 100));

⚡ Performance

For graphs with 10,000+ nodes, consider breadth-first search or pagination.

🔄 Cycles

Always track visited nodes using a Set or Map to prevent infinite loops.

const visited = new Set();
if (visited.has(nodeId)) return; // Critical check!
visited.add(nodeId);

🎨 The Pattern: A Reusable Template

Here's the essential pattern you can adapt to any graph-structured data:

const map = new Map();

async function explore(nodeId) {
  if (map.has(nodeId)) return; // Visited check

  const connections = await fetchData(nodeId); // API call
  map.set(nodeId, connections); // Store

  for (let conn of connections) {
    await explore(conn); // Recurse
  }
}

await explore(startingNodeId);
// map now contains the complete network

💾 Pro tip: This pattern works for any domain - just swap out the fetchData function!

🎓 Conclusion

When data is scattered and interconnected, Depth-First Search transforms incomplete fragments into a complete, actionable map. Whether you're auditing dependencies, exploring networks, or mapping media franchises, DFS provides an elegant solution to reveal hidden connections in fragmented data.

🚀 The next time you find yourself manually clicking through related items, consider: Could DFS automate this exploration and give you the complete picture in seconds?

📚 Further Reading

  • 📖 Graph theory fundamentals
  • 🔍 DFS algorithms deep dive
  • 🌐 Network analysis techniques

📝 Note: This article is based on a real-world implementation of franchise relationship mapping using the MyAnimeList API.

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?