データ構造実験ノート

本記事は以前の8つのデータ構造実機実験レポートを統合し、重複した定型文とソースコード全体を削除して、各実験の核心となる考え方、重要なデータ構造、アルゴリズムの要点だけを残したものです。復習用の整理メモとして使うことを想定しています。コード片は C++ です。

一、再帰とスタック：フィボナッチ数列

問題

再帰を使って第 $n$ 個の Fibonacci 数を求めます。

再帰とスタックの関係

再帰が正しく戻れるかどうかは、引数をどのように渡すか、どこへ戻るかの2点にかかっています。Fib(5) を例にすると：

1. 再帰が1段深くなるたびに、その段の仮引数用の領域を新たに割り当てる必要があります。
2. さらに「今回の呼び出しが終わったらどの行に戻るか」という戻りアドレスも保存する必要があります。

この2つを合わせて作業記録（活動記録）となり、システムによって関数呼び出しスタックにプッシュされます。呼び出し時にプッシュし、戻る時にスタックの先頭からポップするので、正確に1つ前の段へ戻れます。

Fib(3) = Fib(2) + Fib(1) を例にすると、呼び出しの連鎖は次のとおりです：

Fib(3)
├── Fib(2)
│   ├── Fib(1) → 返回 1
│   └── Fib(0) → 返回 0
│   得 1
└── Fib(1) → 返回 1
得 2

アルゴリズム

int Fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return Fib(n - 1) + Fib(n - 2);
}

この再帰版は毎回大量の部分問題を重複して計算するため、時間計算量は指数関数的な $O(2^n)$ になります。効率よく求めるなら漸化式やメモ化に切り替えるべきで、$O(n)$ で済みます。再帰版の価値はスタックの動作過程を示すことにあります。

二、部分集合の分割問題

問題

集合をいくつかの互いに素な部分集合に分割し、同じ部分集合内の要素がどの2つも衝突せず、かつ部分集合の数ができるだけ少なくなるようにします。（典型的な応用：時間割の作成、スケジュール調整。）

アルゴリズム：循環ふるい分け法

1. まず二次元配列（衝突行列）で衝突関係を表します。$conflict[i][j] = 1$ は $i$ と $j$ が衝突することを、$0$ は衝突しないことを意味します。
2. 最初のまだグループに入っていない要素から始め、それを現在のグループに入れます。
3. 残りのまだグループに入っていない要素を順に確認します。それが現在のグループのどの要素とも衝突しなければ現在のグループに加え、そうでなければスキップして次の回に回します。
4. 1回の走査が終わった後、まだグループに入っていない要素があれば新しいグループを開き、手順2を繰り返します。すべての要素が分け終わるまで続けます。

データ構造

未処理の要素を格納するために循環キューを使います。走査が1回進むごとに要素はキューの中を1周するので、追加の記憶領域を確保する必要がありません。

要点

• 「現在のグループに加えられるか」を判定するときは、グループ内のすべての既存要素と比較しなければなりません。1つだけ見て判断すると誤ります。
• これは貪欲法であり、現在のグループに詰め込めれば詰め込むため、得られるのはより良い解であって厳密な最適解ではありません。

三、疎行列の乗算

問題

行列内の非ゼロ要素が非常に少ない場合、完全な二次元配列で格納すると大量の領域を浪費します。そこで3項組に切り替えて非ゼロ要素だけを格納し、2つの疎行列の乗算を実装します。

データ構造

struct Node {          // 1つの非ゼロ要素
    int i, j;          // 行番号、列番号
    int data;          // 要素の値
};

struct Matrix {
    int m, n;          // 総行数、総列数
    int L;             // 非ゼロ要素の個数
    Node* Ma[MAX];     // 非ゼロ要素の配列
};

アルゴリズム

定義どおり $C_{ij} = \sum_k A_{ik} \cdot B_{kj}$ に従いますが、両側とも非ゼロである項だけを累加します：

1. $A$ の各非ゼロ要素 $(i, k, a)$ を走査します。
2. $B$ の中から行番号が $k$ に等しい非ゼロ要素 $(k, j, b)$ を探します。
3. $a \times b$ を結果行列の $(i, j)$ の位置に累加します。

結果行列の非ゼロ要素は動的に生成され、累加した結果が 0 であれば格納しません。

要点

• 素朴な三重ループよりはるかに高速です。大量のゼロ要素同士の乗算を飛ばせるからです。
• さらに高速化したい場合は、3項組の表に行インデックス（行論理リンク順序表）を加えることで、手順2で毎回 $B$ を先頭から走査する必要がなくなります。
• 必ず検証すること：$A$ の列数が $B$ の行数に等しいか、また入力された行・列の添字が範囲外でないか。

四、KMP 文字列マッチング

問題

テキスト文字列の中からパターン文字列が最初に現れる位置を探します。素朴なマッチングは不一致時にパターン文字列を1つ右へずらし、テキストのポインタを後退させるため、最悪の場合 $O(nm)$ になります。KMP はこれを $O(n+m)$ に改善します。

核心：LPS 配列

LPS（Longest Prefix Suffix）は、パターン文字列の各位置より前の部分文字列における「最長で等しい接頭辞と接尾辞」の長さを記録します。これは不一致時にパターン文字列を安全にどれだけ右へ滑らせられるかを教えてくれるので、テキストのポインタを後退させずに済みます。

パターン文字列 ABABCABAB を例にすると、その LPS 配列は次のとおりです：

アルゴリズム

// LPS 配列の構築
void computeLPS(const string& pat, vector<int>& lps) {
    int len = 0;          // 現在の最長接頭辞接尾辞の一致長
    lps[0] = 0;
    int i = 1;
    while (i < (int)pat.size()) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];   // 次に長い接頭辞接尾辞に後退して比較を続ける
        } else {
            lps[i++] = 0;
        }
    }
}

// text の中から pat を探す
void KMPSearch(const string& text, const string& pat) {
    int m = pat.size(), n = text.size();
    vector<int> lps(m);
    computeLPS(pat, lps);

    int i = 0, j = 0;          // i はテキスト、j はパターン文字列を進む
    while (i < n) {
        if (pat[j] == text[i]) { i++; j++; }
        if (j == m) {
            cout << "在索引 " << i - j << " 处找到匹配串" << endl;
            j = lps[j - 1];    // 次の一致を探し続ける
        } else if (i < n && pat[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else        i++;   // j はすでに 0 なので、テキスト側のポインタを進める
        }
    }
}

要点

• テキストのポインタ i は決して後退しません。これが KMP の効率の源です。
• 不一致時は lps[j-1] を使ってパターンのポインタを後退させ、j をゼロに戻したりはしません。
• lps を計算する部分のコード自体も「パターン文字列が自分自身とマッチングする」処理であり、考え方はメインループと同じです。
• 例：テキスト ABABDABACDABABCABAB、パターン ABABCABAB の場合、一致位置は添字 10 です。

五、二分木の格納と走査

問題

**レベル順（BFS 順）**で入力された文字列が与えられます。’@’ は空ノードを表します。これを基に二分木を構築し、さらに順序記憶方式とリンク方式それぞれでの走査を実装します。

2つの格納方式

順序記憶：配列に添字で格納し、親子関係は添字から計算します：

• 親ノードの添字が $i$ → 左の子は $2i+1$、右の子は $2i+2$。
• 逆に、ノード $i$ の親ノードは $\lfloor (i-1)/2 \rfloor$。

完全二分木に向いています。ノードが疎な場合は配列の領域を大量に浪費します。

リンク方式：構造体とポインタを使い、キューを補助にして構築します。

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
};

構築の流れ：根ノードをエンキューする → キューの先頭からノードを1つ取り出すたびに、順に左、右の子を付けます（入力が ‘@’ ならその側は空）。そして新しい子をエンキューします。先行順入力での構築に変えたい場合は、キューをスタックに置き換えるだけです。

3つの深さ優先走査

void preOrder(TreeNode* p) {          // 先行順：根 → 左 → 右
    if (!p) return;
    visit(p);
    preOrder(p->left);
    preOrder(p->right);
}

void inOrder(TreeNode* p) {           // 中間順：左 → 根 → 右
    if (!p) return;
    inOrder(p->left);
    visit(p);
    inOrder(p->right);
}

void postOrder(TreeNode* p) {         // 後行順：左 → 右 → 根
    if (!p) return;
    postOrder(p->left);
    postOrder(p->right);
    visit(p);
}

幅優先走査

キューを使って根から1レベルずつ処理します。ノードを訪問するときにその左右の子を順にエンキューします。

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        visit(p);
        if (p->left)  q.push(p->left);
        if (p->right) q.push(p->right);
    }
}

完全な例

abc@def@@@@ を入力すると（レベル順、’@’ は空）、対応する二分木は次のとおりです：

        a
      /   \
     b     c
    / \   / \
   @   d e   f
      / \ / \ / \
     @  @ @ @ @  @

順序記憶での中間順走査は開始点を慎重に扱う必要があります。先行順は添字 0 から始められますが、中間順は木全体で最も左下のノードから始めなければなりません。そうでなければ左部分木の左半分を取りこぼします。

走査列から二分木を逆に求める

• 先行順 + 中間順、後行順 + 中間順、レベル順 + 中間順のいずれも、二分木を一意に確定できます。
• しかし先行順 + 後行順では不可能で、子が1つだけのときにそれが左に付くのか右に付くのかを区別できません。

六、ハフマン木と符号化

問題

文字を出現頻度に応じて符号化し、符号化後の総長を最短にし、かつどの符号も別の符号の接頭辞にならないようにします（接頭符号。一意に復号できることを保証します）。

アルゴリズム

1. 各文字の出現頻度を数えます。
2. 各文字についてリーフノードを1つ作り、すべて最小ヒープに入れます。
3. ループ：頻度が最小の2つのノードを取り出し、新しいノード（頻度は両者の和）に統合し、新しいノードをヒープに戻します。
4. ヒープにノードが1つだけ残ったとき、それがハフマン木の根です。

while (minHeap.size() > 1) {
    auto left  = minHeap.top(); minHeap.pop();
    auto right = minHeap.top(); minHeap.pop();
    auto parent = new HuffmanNode('$', left->frequency + right->frequency);
    parent->left = left;
    parent->right = right;
    minHeap.push(parent);
}

符号の生成と復号

• 符号の生成：根から再帰的に走査し、左へ進むと 0、右へ進むと 1 を記録し、リーフノードに到達したときの現在の経路の文字列をその文字の符号として記録します。
• 符号化：原文の各文字をその符号列に置き換えます。
• 復号：根から始め、0 なら左、1 なら右へ進み、リーフに到達したらその文字を出力して根に戻り、最初からやり直します。

要点

• 頻度が高い文字ほど根に近く、符号が短くなります。これが圧縮の原理です。
• 符号はすべてリーフノードにあるため、「ある符号が別の符号の接頭辞になる」ことはなく、復号に曖昧さは生じません。
• 繰り返しソートする代わりに最小ヒープを使うことで、構築の計算量を $O(n \log n)$ まで下げられます。
• 出現頻度が同じ文字は、どちらが先でも符号の長さには影響せず、割り当てられる 0/1 の列だけが変わります。

七、ソート二分木とノードの削除

問題

ソート二分木（BST）を構築し、挿入、中間順走査、ノードの削除に対応します。

挿入

再帰的に比較します。挿入する値が現在のノードより小さければ左へ、大きければ右へ進み、空の位置に来たら新しいノードを作って付けます。

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val)      root->left  = insert(root->left,  val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;   // 等しい場合は挿入せず、重複を避ける
}

中間順走査

BST を中間順に走査すると昇順の列が得られます。これは BST が正しく構築されているかを確かめる最も直接的な方法です。

ノードの削除

削除は最も間違えやすい部分で、3つの場合に分かれます：

TreeNode* remove(TreeNode* root, int val) {
    if (!root) return nullptr;
    if (val < root->val)      root->left  = remove(root->left,  val);
    else if (val > root->val) root->right = remove(root->right, val);
    else {
        if (!root->left)  { auto t = root->right; delete root; return t; }
        if (!root->right) { auto t = root->left;  delete root; return t; }
        // 子が2つ：右部分木の最小ノードを探す
        TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val  = succ->val;
        root->right = remove(root->right, succ->val);
    }
    return root;
}

左部分木の最大ノード（中間順の先行）で置き換えても効果は同等です。

木全体の削除

後行順で各ノードを順に解放します。親ノードを先に解放してから子を探してはいけません。

八、二分木の手がかり化

問題

$n$ 個のノードを持つ二分木には $2n$ 個のポインタ領域がありますが、実際に使われるのは $n-1$ 本の辺だけで、残りの $n+1$ 個は空ポインタであり、明らかに無駄です。手がかり化とは、この空ポインタに走査順での先行/後続を格納し、走査がスタックや再帰に依存しなくて済むようにすることです。

データ構造

struct Node {
    int data;
    Node *left, *right;
    int ltag, rtag;   // 0 は子を指す、1 は手がかり（先行/後続を指す）
};

アルゴリズム（中間順の手がかり化を例に）

再帰的な中間順走査を使い、同時にグローバルな pre ポインタで直前に訪問したノードを記録します：

Node* pre = nullptr;

void thread(Node* p) {
    if (!p) return;
    thread(p->left);              // まず左部分木を処理する

    if (!p->left) {               // 左の子が空なら、左ポインタを先行に向け替える
        p->left = pre;
        p->ltag = 1;
    }
    if (pre && !pre->right) {     // 先行の右の子が空なら、右ポインタを後続に向け替える
        pre->right = p;
        pre->rtag = 1;
    }

    pre = p;                      // 先行を更新する
    thread(p->right);             // 次に右部分木を処理する
}

要点

• left / right ポインタの意味は二重であり、ltag / rtag で区別しなければなりません。そうしないと手がかりを子ポインタとして使ってしまい、無限ループになります。
• 中間順の手がかり化では、先に左部分木を再帰し、次に現在のノードを処理し、最後に右部分木を再帰します。pre = p の位置が手がかりの向き先を決めます。
• 先行順、後行順の手がかり化も考え方は同じで、違いは現在のノードを処理するタイミングと pre を更新する順序にあります。
• 手がかり化した木は空間 $O(1)$ で走査でき、スタックも再帰も必要ありません。

九、グラフの格納：隣接行列と隣接リスト

隣接行列

二次元配列 adj[V][V] で辺を格納します。adj[i][j] = 1（または辺の重み）は $i \to j$ に辺があることを意味します。

• 長所：2点間に辺があるかの判定が $O(1)$。実装も単純。
• 短所：空間が常に $O(V^2)$ で、疎グラフでは浪費が深刻。ある点のすべての隣接点を走査するには1行全体を走査する必要があり $O(V)$。
• 無向グラフの行列は主対角線に対して対称です。

隣接リスト

「配列 + 連結リスト」を使います。adj[i] にはノード $i$ に隣接するすべてのノードを格納します。

vector<int> adj[MAX];          // 各要素が1つの連結リスト/動的配列
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);       // 無向グラフでは逆向きの辺も追加する
}

• 長所：空間は $O(V + E)$ で、疎グラフに優しい。ある点の隣接点を走査するときは実在する辺だけを訪問します。
• 短所：2点間に辺があるかを判定するには連結リストを走査する必要があり、最悪 $O(V)$。
• 有向グラフでは、adj[u] に格納されるのは $u$ の出辺です。入次数を求めるには追加の走査か、別途逆隣接リストを作る必要があります。

どちらを選ぶか

グラフ構築時のチェック

辺 $(u, v)$ を読み込んだ後は $0 \le u, v < V$ を検証し、範囲外を避けます。重みなしグラフでは2点間に辺を重複して追加すべきではありません。そうしないと走査や次数の集計に影響します。

十、Kruskal と最小全域木

問題

重み付き連結無向グラフの中で、総重みが最小の全域木を探します。

アルゴリズム（貪欲法）

1. すべての辺を重みの昇順でソートします。
2. 各辺を順に検討します。その両端点がまだ同じ集合にないなら全域木に加え、この2つの集合を統合します。そうでなければ閉路ができるので、そのまま捨てます。
3. $V-1$ 本の辺を選び終えたら終了します。

sort(edges.begin(), edges.end(),
     [](const Edge& a, const Edge& b) { return a.weight < b.weight; });

UnionFind uf(numNodes);
vector<Edge> result;
for (const Edge& e : edges) {
    if (uf.find(e.start) != uf.find(e.end)) {   // 非連結 → 加えても閉路にならない
        result.push_back(e);
        uf.unite(e.start, e.end);
    }
}

Union-Find（素集合データ構造）

Kruskal の効率の鍵は「2点がすでに連結かどうかを判定する」ことにあり、これがまさに Union-Find の得意分野です。2つの操作をサポートします：

• Find(x)：$x$ が属する集合の根ノードを求め、ついでに2点が同じ集合かを判定します。
• Union(a, b)：2つの集合を統合します。

2つの最適化を併用すると、ならし計算量をほぼ定数にできます：

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);   // 経路圧縮
    return parent[x];
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) swap(a, b);   // ランクによる統合
    parent[b] = a;
    if (rank[a] == rank[b]) rank[a]++;
}

要点

• 時間計算量は $O(E \log E)$ で、主にソートに費やされます。
• 疎グラフに適しています。稠密グラフでは通常 Prim アルゴリズム（$O(V^2)$、またはヒープを使った $O(E \log V)$）の方が高速です。
• 辺のソートと、Union-Find による閉路判定が、Kruskal の2つの中核動作です。

十一、Dijkstra と単一始点最短経路

問題

重み付きグラフと始点 $s$ が与えられたとき、$s$ から他のすべての頂点への最短距離を求めます。

アルゴリズム（貪欲法 + 優先度付きキュー）

1. 始点の距離を 0 に、それ以外をすべて無限大に設定します。
2. (距離, 頂点) を優先度付きキューに入れ、毎回距離が最小の頂点 $u$ を取り出します。この時点でその最短距離はすでに確定しています。
3. 緩和：$u$ の各隣接点 $v$ について、$dist[u] + w(u,v) < dist[v]$ なら $dist[v]$ を更新し、新しい (dist[v], v) をキューに入れます。
4. 2–3 をキューが空になるまで繰り返します。

vector<int> dijkstra(const vector<vector<int>>& g, int src) {
    int n = g.size();
    vector<int> dist(n, INF);
    // 最小ヒープ：キューの先頭が距離最小の要素
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;        // 期限切れの項目はスキップ
        for (int v = 0; v < n; v++) {
            if (g[u][v] == 0) continue;   // 0 は直接の接続がないことを表す
            if (dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

要点

• 負の重みの辺は扱えません。Dijkstra の正しさは「一度取り出した点の距離はもう小さくならない」ことに依存しており、負の重みの辺はこの前提を崩します。負の重みを含む場合は Bellman-Ford や SPFA に切り替えます。
• 隣接行列でグラフを表す場合、内側の走査は $O(V)$ で、全体の計算量は $O(V^2)$ です。隣接リストと優先度付きキューに変えると $O(E \log V)$ まで下げられます。
• 同じ点が複数回エンキューされることがあるため、デキュー時に d > dist[u] を判定して期限切れの項目をスキップします。
• 0 で「辺なし」を表すのは1つの約束事です。グラフで重み 0 の辺を許す場合は、別の目印を設けるか隣接リストに切り替える必要があります。

十二、クリティカルパス

問題

AON（アクティビティ・オン・ノード）ネットワークでは、各ノードが1つのアクティビティを表し、所要時間と先行関係を持ちます。プロジェクトの総工期を決めるクリティカルなアクティビティの列を探します。

• 最早開始時刻 ES：そのアクティビティを最も早くいつ開始できるか。
• 最遅開始時刻 LS：総工期を遅らせない前提で、最も遅くいつまでに開始しなければならないか。
• 時間余裕：$LS - ES$。余裕が 0 のアクティビティがクリティカルアクティビティで、それらをつなぐとクリティカルパスになります。

ES の前向き計算

トポロジカル順で始点イベントから後ろへ進めます：

先行アクティビティのない始点イベントは $ES = 0$ です。プロジェクトの総工期は $T = \max_v (ES[v] + duration[v])$ です。

void calcEarliest() {
    // 必ずトポロジカル順で処理する。そうしないと先行の ES がまだ計算されていない
    for (int u : topoOrder) {
        for (int v : activities[u].next) {
            earliest[v] = max(earliest[v], earliest[u] + activities[u].duration);
        }
    }
}

LS の後ろ向き計算

逆トポロジカル順で終点イベントから前へ進めます：

後続のない終点イベントは $LS = ES = T - duration$ です。（等価に、$LF[\cdot] = T$ とすると $LS = LF - duration$、$LF[u] = \min_{v \in succ(u)} LS[v]$。）

void calcLatest() {
    for (int u : reverseTopoOrder) {
        for (int v : activities[u].next) {
            latest[u] = min(latest[u], latest[v] - activities[u].duration);
        }
    }
}

要点

• どちらの方向も必ず厳密にトポロジカル順で進めなければなりません。そうでないと使う先行/後続がまだ計算されていません。
• 始点イベントの判定に「隣接リストが空かどうか」を使ってはいけません。隣接リストが空なのは終点イベント（出次数が 0）です。始点イベントの判定根拠は入次数が 0 であることで、この向きを逆にすると計算全体が破綻します。
• クリティカルパスは複数あることがあります。$\text{余裕} = 0$ のアクティビティはすべて印を付ける必要があります。
• 総工期を短縮したい場合は、クリティカルアクティビティを圧縮するしかありません。クリティカルでないアクティビティを圧縮しても意味はありません。

まとめ