データ構造とアルゴリズム入門2（ソート・グラフ）

Last updated at 2024-06-16Posted at 2024-05-04

データ構造とアルゴリズム

10. [アルゴリズム] ソート（Sort）

ソートとは、データをそれらが持つキーを基準に昇順（小さい順）または降順（大きい順）に並べ替える処理。
安定なソート（Stable Sort）
- キーの値が同じ要素を2つ以上含むデータをソートした場合、処理の前後でそれらの要素の順番が変わらないようなアルゴリズムのこと。

バブルソート（Bubble Sort）

配列の隣接する要素を比較、交換し、最も大きい（小さい）要素を徐々に配列の端に移動させる。
1. 配列の最初の要素と次の要素を比較し、順序が逆であれば交換する。
2. 1.を配列の最後まで繰り返す。
3. 配列全体がソートされるまで、1 ~ 2を繰り返す。
例: 配列 [5, 2, 9, 1, 5, 6]
1. [2, 5, 1, 5, 6, 9]
2. [2, 1, 5, 5, 6, 9]
3. [1, 2, 5, 5, 6, 9]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n^2)	O(n^2)	O(1)	◯

Bubble Sort Comparison Based Sorts - LeetCode

挿入ソート（Insertion Sort）

配列の先頭の要素をソート済みとみなすことから開始する。
1. 未ソート部分から、最初の要素を1つ取り出す。
2. ソート済み部分において、未ソート部から取り出した要素より大きい要素を、後方へ1つずつ移動する。
3. 空いた位置に取り出した要素を挿入する。
例: 配列 [4, 3, 2, 10, 12, 1, 5, 6]
1. [3, 4, 2, 10, 12, 1, 5, 6]
2. [2, 3, 4, 10, 12, 1, 5, 6]
3. [2, 3, 4, 10, 12, 1, 5, 6] （変わらず）
4. [2, 3, 4, 10, 12, 1, 5, 6] （変わらず）
5. [1, 2, 3, 4, 10, 12, 5, 6]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n^2)	O(n^2)	O(1)	◯

選択ソート（Selection Sort）

未ソート部分から最小の要素を見つけ出し、それを未ソート部分の先頭要素と交換することを繰り返す。
1. 未ソート部分の最小の要素を見つける。
2. その要素を未ソート部分の先頭の要素と交換する。
3. 配列全体がソートされるまで、1 ~ 2を繰り返す。
例: 配列 [64, 25, 12, 22, 11]
1. [11, 25, 12, 22, 64]
2. [11, 12, 25, 22, 64]
3. [11, 12, 22, 25, 64]
4. [11, 12, 22, 25, 64]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n^2)	O(n^2)	O(1)	×

マージソート（Merge Sort）

分割統治法に基づくアルゴリズム。
配列を半分に分割し、それぞれを再帰的にソートしてから統合する。
1. 配列を半分に分割する。（Divide）
2. 分割された配列が要素数1になるまで、分割を繰り返す。
3. 要素数1の配列を結合してソートされた配列にしていく。
4. 2つのソート済みの配列を統合する。（Conquer）
例: 配列 [38, 27, 43, 3, 9, 82, 10]
1. 分割 [38, 27, 43, 3] と [9, 82, 10]
2. 分割 [38, 27] と [43, 3]、[9] と [82, 10]
3. 分割 [38] と [27]、 [43] と [3]、[9]、[82] と [10]
4. 統合 [27, 38]、[3, 43]、[9]、[10, 82]
5. 統合 [3, 27, 38, 43]、[9, 10, 82]
6. 統合 [3, 9, 10, 27, 38, 43, 82]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n log(n))	O(n log(n))	O(n)	◯

クイックソート（Quick Sort）

分割統治法に基づくアルゴリズム。 ※ 統合は行わない。
基準となる要素（ピボット / pivot）を選び、配列を基準となる要素より小さい要素と大きい要素に分割し、それぞれを再帰的にソートする。
1. 配列からピボットを選ぶ。
2. ピボットより小さい要素の配列と大きい要素の配列に分ける。（Divide）
3. 分割された配列に対して、1 ~ 2の手順を繰り返す。
4. 2つのソート済みの配列の間にピボットを入れて統合する。（Conquer）
例: 配列 [10, 7, 8, 9, 1, 5]、ピボットは9
1. 分割 [1, 5, 7, 8], 9, [10]
2. [1, 5, 7, 8]
3. [10]
4. [1, 5, 7, 8, 9, 10]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n log(n))	O(n^2)	O(log(n))	×

ヒープソート（Heap Sort）

ヒープ（データ構造）（完全二分木）を用いてソートする。
1. 配列を最大ヒープor最小ヒープに変換する。（ヒープ化）
2. ヒープの根（root。最大または最小の要素）を取り出し、末尾の要素と交換する。
3. ヒープのサイズを1減らす。
4. ヒープが空になるまで、1 ~ 3を繰り返す。
例: 配列 [4, 10, 3, 5, 1]
1. ヒープ化 [10, 5, 3, 4, 1]
2. 10を末尾と交換 [1, 5, 3, 4, 10]
3. ヒープ化 [5, 4, 3, 1, 10]
4. 5を末尾と交換 [1, 4, 3, 5, 10]
5. ヒープ化 [4, 1, 3, 5, 10]
6. 4を末尾と交換 [1, 3, 4, 5, 10]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n log(n))	O(n log(n))	O(1)	×

バケットソート（計数ソート / Bucket Sort / Counting Sort）

データをいくつかのバケット（小さな区間）に分け、それぞれのバケット内でソートを行い、最後にバケットを結合する。
1. データを複数のバケットに分割する。
2. 各バケット内でソートを行う。
3. ソートされたバケットを順に結合する。
例: 配列 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
- 分割: バケット1: [0.12, 0.17, 0.21, 0.23, 0.26], バケット2: [0.39, 0.68, 0.72, 0.78, 0.94]
- 各バケット内ソート: バケット1: [0.12, 0.17, 0.21, 0.23, 0.26], バケット2: [0.39, 0.68, 0.72, 0.78, 0.94]
- 結合: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

平均時間計算量	最悪時間計算量	最悪領域計算量	安定なソート
O(n+k)	O(n^2)	O(n+k)	◯

※ k はバケットの数またはデータの最大値を表す。

11. [データ構造] グラフ（Graph）

データ構造の説明

グラフの種類	説明	例
無向グラフ（Undirected Graph）	各辺に向き（方向）がないグラフ	・Facebookなどのソーシャルグラフで、誰と誰が友人か
有向グラフ（Directed Graph）	各辺に向き（方向）があるグラフ	・Twitterなどのソーシャルグラフで、誰が誰のことをフォローしているか・Google Mapsで、道路が一方通行かどうか
重み付き無向グラフ（Weighted Undirected　Graph）	各辺に重みがあり、向き（方向）がないグラフ	・Google Mapsで、頂点（地図上の特定の地点）までの辺（道路）に、どれくらいの重み（距離、所要時間）があるか
重み付き有向グラフ（Weighted Directed Graph）	各辺に重みがあり、向き（方向）があるグラフ	・Google Mapsで、電車を利用した時、ある頂点（駅A）から別の頂点（駅B）までの辺（経路）に、どれくらいの重み（料金）があるか

グラフ（Graph）
- 対象物の関係性を表すデータ構造。
- 例えば、友達関係を表すソーシャルグラフは、友達同士の関係性を表すことができる。
頂点(ノード / Vertex / Node)
- グラフにおいて、対象物を表す丸のこと。
辺（Edge）
- グラフにおいて、頂点間の関係性を表す、頂点と頂点を結ぶ線のこと。
向き（方向 / Direction）
- グラフにおいて、頂点間の一方的な関係性を表す、頂点から頂点への矢印で示される辺の特性のこと。
重み（Weight）
- 各辺に関連付けられた値のこと。
- 例えば、時間、距離、コスト、サイズ、関連の強さなどの数値のこと。
（頂点が）隣接している(Vertex is Adjancent)
- 頂点 u と頂点 v が辺 e によって結ばれているとき、頂点 u , v は隣接している、と言う。
（辺が）接続している(Edge is Incident)
- 辺 e が頂点 u と頂点 v によって結ばれているとき、辺 e は頂点 u , v 接続している、と言う。
歩道 (ウォーク / walk)
- 頂点 u から頂点 v まで、隣接する頂点を辿って到達できる経路のこと。
パス（道 / Path）
- 同じ頂点を2度以上通らない歩道のこと。
閉路（サイクル / Cycle）
- 始点と終点が同じである歩道のこと。
（頂点の）次数（Degree of Vertex）
- 頂点につながっている辺の数のこと。
- 入次数（In-Degree）
  - 有向グラフにおいて、頂点 u に入る辺の数のこと。
- 出次数（Out-Degree）
  - 有向グラフにおいて、頂点 u から出ていく辺の数のこと。
（グラフが）連結である（Graph is Connected）
- グラフ G のどの頂点 u , v においてもパスが存在するとき、グラフ G は連結である、と言う。

重み付き無向グラフのイメージ:

パス、閉路、連結、次数のイメージ:

有向グラフ、入次数、出次数のイメージ:

グラフデータ処理アルゴリズムと機械学習/人工知能タスクへの応用

グラフの表現方法には、隣接行列による表現と、隣接リストによる表現の2種類がある。
隣接行列（Adjancency matrix）
- 行列という名の通り、グラフを 二次元配列 で表現する方法。
- 配列のインデックスが各頂点の番号に対応する。
- 例えば、二限配列を M とすると、 M[i][j] の値を1（true）とし、辺がない場合は0（false）とする。
- 無向グラフの隣接行列では、右上と左下が対称になる。
隣接リスト（Adjancency list）
- グラフを二次元配列、または 連結リストの配列 で表現する方法。
- 一次配列のインデックスが各頂点の番号に対応する。
  - 一次配列の各要素には、頂点に隣接する頂点の配列、または頂点に隣接する頂点の連結リストを保持する。
- 例えば、配列を M とすると、 M[i] の値を [1, 4] とし、辺がない場合は [] とする。

重みなし有向グラフの隣接行列:

隣接行列 - ALGORITHM NOTE

重み付き有向グラフの隣接リスト:

隣接リスト - ALGORITHM NOTE

12. [データ構造] Union Find（Disjoint Set / 素集合データ構造）

データ構造の説明

Union Find は、データを 互いに素な動的集合（1つの要素が複数の集合に属することがない集合） S = {S1, S2,...,Sk}に分類して管理するためのデータ構造。
- 以下の2つの基本操作を効率的に実行することを目的としている。
  - Find（探索）
    - 要素がどの集合に属しているかを調べる操作。
    - 通常、要素の「親」を追跡することで実現される。
  - Union（統合）
    - 2つの異なる集合を1つに結合する操作。
    - この操作では、1つの集合の「根」をもう一方の集合の「根」に結びつける。
- 操作を効率的に行うために、Union Findデータ構造では、「ランク付け」と「経路圧縮」という2つの最適化手法が用いられる。
  - ランク付け（Union by Rank） - 各集合の「根」にランクを割り当て、ランクの低い集合をランクの高い集合に結びつけることで、木の高さを抑える手法。
  - 経路圧縮（Path Compression） - Find操作の際に経路上の全ての要素を直接根に結びつけることで、後続のFind操作を高速化する手法。

C++での実装

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent, rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int main() {
    UnionFind uf(10);

    uf.unite(1, 2);
    uf.unite(2, 3);
    uf.unite(4, 5);
    uf.unite(6, 7);
    uf.unite(5, 6);

    cout << "1と3が同じ集合に属しているか: " << (uf.find(1) == uf.find(3)) << endl;
    cout << "4と7が同じ集合に属しているか: " << (uf.find(4) == uf.find(7)) << endl;
    cout << "1と7が同じ集合に属しているか: " << (uf.find(1) == uf.find(7)) << endl;

    return 0;
}

出力

1と3が同じ集合に属しているか: 1
4と7が同じ集合に属しているか: 1
1と7が同じ集合に属しているか: 0

13. [アルゴリズム] 深さ優先探索(Depth First Search / DFS） / 幅優先探索（Breadth First Search / BFS）

データ構造の説明

	使用するデータ構造・アルゴリズム	手順	説明	時間計算量	ユースケース
深さ優先探索(Depth First Search / DFS）	スタック（LIFO）再帰	1. スタート地点の頂点をスタックに入れて訪問する。 2. スタックのトップの頂点から未訪問の隣接頂点に進み、訪問してスタックに追加する。 3. 隣接する未訪問の頂点がなくなるまで繰り返し、スタックから頂点を取り出して戻る。	1人の捜査員が道の領域をできるだけ奥深くへと捜索し、行き止まりに出会った時にだけ戻ってくるのと似ている。	O(\|V\| + \|E\|) ※Vは頂点、Eは辺を表す	数独などのパズル、コンピュータ将棋ソフト、迷路探索、サイクル検出、トポロジカルソート
幅優先探索（Breadth First Search / BFS）	キュー（FIFO）	1. スタート地点の頂点をキューに入れて訪問する。 2. キューが空になるまで、キューから頂点を取り出し、その未訪問の隣接頂点を全てキューに追加して訪問する。	捜査チームが（各自の道の領域を）全方向に捜査するのと似ている。	O(\|V\| + \|E\|)　 ※Vは頂点、Eは辺を表す	最短経路、ソーシャルネットワーク、リアルタイムゲーム（移動範囲の決定）

https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

グラフの探索とは、グラフの全ての頂点を訪問すること。
深さ優先探索（Depth First Search）
- 可能な限り隣接する頂点を訪問する、という戦略に基づくグラフの探索アルゴリズム。
- 深さ優先探索は、再帰的なアルゴリズムでより簡単に実装することができるが、大きなグラフに対する再帰を用いた深さ優先探索は、スタックオーバーフローを起こす可能性があるので、スタックを用いて実装したり、（キューを用いた）幅優先探索を用いて実装する。

再帰による深さ優先探索（C++での実装）

基本形:

https://github.com/drken1215/book_algorithm_solution/blob/master/codes/chap13/code_13_2.cpp

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    // G[v] のベクターの各要素に対して繰り返し処理する
    for (auto next_v: G[v]) {  // G[v] の次の要素を、型推論しつつ、 next_v に代入する
        if (seen[next_v]) continue; // next_v が探索済ならば探索しない
        dfs(G, next_v); // 再帰的に探索
    }
}

int main() {
    // 頂点数と辺数
    int N, M;
    cin >> N >> M;

    // グラフ入力受取 (ここでは有向グラフを想定)
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
    }

    // 探索
    seen.assign(N, false); // 初期状態では全頂点が未訪問
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue; // すでに訪問済みなら探索しない
        dfs(G, v);
    }
}

200. Number of Islands - leetcode

https://leetcode.com/problems/number-of-islands/

#include <iostream>
#include <vector>
using namespace std;

class Solution {
private:
    // 深さ優先探索関数
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();

        // 現在のセルを訪問済みとしてマーク
        grid[r][c] = '0';

        // 上下左右の隣接セルを調べる
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c); // 上
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c); // 下
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1); // 左
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1); // 右
    }

public:
    // 島の数を数える関数
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        // 各セルを順番に調べる
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                // 島が見つかったら深さ優先探索を行う
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};


int main() {
    Solution solution;
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    // 島の数を出力
    std::cout << "Number of islands: " << solution.numIslands(grid) << std::endl;
    return 0;
}

スタックによる深さ優先探索（C++での実装）

基本形:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
using Graph = vector<vector<int>>;

// スタックを用いた非再帰的な深さ優先探索
void dfs(const Graph &G, int s) {
    int N = (int)G.size(); // 頂点数
    vector<bool> seen(N, false); // 各頂点の訪問状態
    stack<int> st;

    // 初期状態としてスタート頂点をスタックにpush
    st.push(s);
    seen[s] = true; // スタート頂点を訪問済みに

    while (!st.empty()) {
        int v = st.top(); // スタックから頂点を取得
        st.pop(); // スタックから頂点を削除

        // 頂点vから行ける頂点を全て調べる
        for (auto next_v : G[v]) {
            if (!seen[next_v]) { // 未訪問ならば
                seen[next_v] = true; // 訪問済みとする
                st.push(next_v); // スタックにpush
            }
        }
    }
}

int main() {
    int N, M; // 頂点数と辺数
    cin >> N >> M;
    Graph G(N); // グラフの隣接リスト表現
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b; // 頂点aからbへの辺を入力
        G[a].push_back(b); // 有向グラフとする
    }

    int s; // 探索の開始頂点
    cin >> s;
    dfs(G, s); // スタックを用いたDFS

    return 0;
}

200.Number of Islands - leetcode

https://leetcode.com/problems/number-of-islands/

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        // 各セルを順番に調べる
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                // 島が見つかったら深さ優先探索を行う
                if (grid[r][c] == '1') {
                    ++num_islands;
                    stack<pair<int, int>> s;
                    s.push({r, c});
                    while (!s.empty()) {
                        auto [i, j] = s.top();
                        s.pop();
                        grid[i][j] = '0'; // 訪問済みとしてマーク

                        // 上下左右の隣接セルを調べる
                        if (i - 1 >= 0 && grid[i-1][j] == '1') s.push({i - 1, j}); // 上
                        if (i + 1 < nr && grid[i+1][j] == '1') s.push({i + 1, j}); // 下
                        if (j - 1 >= 0 && grid[i][j-1] == '1') s.push({i, j - 1}); // 左
                        if (j + 1 < nc && grid[i][j+1] == '1') s.push({i, j + 1}); // 右
                    }
                }
            }
        }

        return num_islands;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    // 島の数を出力
    std::cout << "Number of islands: " << solution.numIslands(grid) << std::endl;
    return 0;
}

幅優先探索（Breadth First Search）
- 始点 s から k + 1 の距離にある頂点を発見する前に、距離 k の頂点をすべて発見する、という戦略に基づくグラフの探索アルゴリズム。
- 始点から各頂点までの 最短経路 を順番に求めることができる。

キューによる幅優先探索（C++での実装）

基本形:

https://github.com/drken1215/book_algorithm_solution/blob/master/codes/chap13/code_13_3.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;

// 入力: グラフ G と、探索の始点 s
// 出力: s から各頂点への最短路長を表す配列
vector<int> BFS(const Graph &G, int s) {
    int N = (int)G.size(); // 頂点数
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 s を初期頂点として設定)
    dist[s] = 0; // 頂点 s の距離を0に設定
    que.push(s); // s をキューに追加して探索を開始

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int x : G[v]) {
            if (dist[x] != -1) continue; // すでに訪問済みの頂点は探索しない

            // 新たに発見した頂点 x について距離情報を更新してキューに挿入
            dist[x] = dist[v] + 1;
            que.push(x);
        }
    }
    return dist;
}

int main() {
    // 頂点数と辺数
    int N, M;
    cin >> N >> M;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a); // 無向グラフなので両方向に辺を追加
    }

    // 頂点 0 を始点とした BFS
    vector<int> dist = BFS(G, 0);

    // 結果出力 (各頂点の頂点 0 からの距離を出力)
    for (int v = 0; v < N; ++v) {
        cout << v << ": " << dist[v] << endl;
    }
}

200.Number of Islands - leetcode

https://leetcode.com/problems/number-of-islands/

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        // 各セルを順番に調べる
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                // 島が見つかったら幅優先探索を行う
                if (grid[r][c] == '1') {
                    ++num_islands;
                    queue<pair<int, int>> q;
                    q.push({r, c});
                    while (!q.empty()) {
                        auto [i, j] = q.front();
                        q.pop();
                        grid[i][j] = '0'; // 訪問済みとしてマーク

                        // 上下左右の隣接セルを調べる
                        if (i - 1 >= 0 && grid[i-1][j] == '1') {
                            q.push({i - 1, j}); // 上
                            grid[i-1][j] = '0'; // 訪問済みとしてマーク
                        }
                        if (i + 1 < nr && grid[i+1][j] == '1') {
                            q.push({i + 1, j}); // 下
                            grid[i+1][j] = '0'; // 訪問済みとしてマーク
                        }
                        if (j - 1 >= 0 && grid[i][j-1] == '1') {
                            q.push({i, j - 1}); // 左
                            grid[i][j-1] = '0'; // 訪問済みとしてマーク
                        }
                        if (j + 1 < nc && grid[i][j+1] == '1') {
                            q.push({i, j + 1}); // 右
                            grid[i][j+1] = '0'; // 訪問済みとしてマーク
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    // 島の数を出力
    std::cout << "Number of islands: " << solution.numIslands(grid) << std::endl;
    return 0;
}

トポロジカルソート（Topological Sort）
- 有向非巡回グラフにおいて、すべての辺 (u, v) について、頂点 u が頂点 v に先行するように、頂点を線形に並べること。
  - 具体的には、グラフの頂点を順番に訪問し、その訪問順序を保存していく。最終的に訪問した順序の逆順がトポロジカルソートの結果となる。
- 有向非巡回グラフ（DAG / Directed Acyclic Graph）
  - 閉路が存在しない有向グラフのこと。
  - 例
    - タスクの依存関係
      - タスクAがタスクBに依存している場合、タスクAを完了する前にタスクBを完了する必要がある。DAGを用いると依存関係を視覚的に整理できる。

C++での実装

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// グラフを表す構造体
struct Graph {
    int V; // 頂点数
    vector<vector<int>> adj; // 隣接リスト

    Graph(int V) : V(V), adj(V) {}

    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& Stack) {
        visited[v] = true; // 現在の頂点を訪問済みとする

        for (int i : adj[v]) // すべての隣接頂点を再帰的に訪問
            if (!visited[i])
                topologicalSortUtil(i, visited, Stack);

        Stack.push(v); // 完了した頂点をスタックに追加
    }

    void topologicalSort() {
        stack<int> Stack; 
        vector<bool> visited(V, false); 

        for (int i = 0; i < V; i++) // すべての頂点を訪問
            if (visited[i] == false)
                topologicalSortUtil(i, visited, Stack);

        while (!Stack.empty()) { // スタックから取り出し順序を表示
            cout << Stack.top() << " ";
            Stack.pop();
        }
    }
};

int main() {
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    cout << "トポロジカルソートの順序:\n";
    g.topologicalSort();
    return 0;
}

出力

トポロジカルソートの順序:
5 4 2 3 1 0

最短経路（Shortest Path）
- グラフの2つの頂点間の経路の中で、辺の重みの合計が最小の経路を見つけること。
- 代表的なアルゴリズムには以下のものがある：
  - ダイクストラのアルゴリズム（Dijkstra's Algorithm） - 辺の重みが非負の場合に最短経路を求めるアルゴリズム。
  - ベルマン-フォードのアルゴリズム（Bellman-Ford Algorithm） - 負の重みを持つ辺が存在する場合でも最短経路を求めることができるアルゴリズム。
  - フロイド-ワーシャルのアルゴリズム（Floyd-Warshall Algorithm） - 全ての頂点間の最短経路を求めるアルゴリズム。

C++での実装

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

typedef pair<int, int> iPair;

void dijkstra(vector<vector<iPair>>& graph, int src) {
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    vector<int> dist(graph.size(), INT_MAX);
    pq.push(make_pair(0, src));
    dist[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    cout << "頂点 " << src << " からの最短距離:\n";
    for (int i = 0; i < dist.size(); ++i)
        cout << "頂点 " << i << " : " << dist[i] << "\n";
}

int main() {
    int V = 5;
    vector<vector<iPair>> graph(V);
    graph[0].emplace_back(1, 10);
    graph[0].emplace_back(4, 5);
    graph[1].emplace_back(2, 1);
    graph[1].emplace_back(4, 2);
    graph[2].emplace_back(3, 4);
    graph[3].emplace_back(2, 6);
    graph[3].emplace_back(0, 7);
    graph[4].emplace_back(1, 3);
    graph[4].emplace_back(2, 9);
    graph[4].emplace_back(3, 2);

    dijkstra(graph, 0);

    return 0;
}

出力

頂点 0 からの最短距離:
頂点 0 : 0
頂点 1 : 8
頂点 2 : 9
頂点 3 : 7
頂点 4 : 5

14. [アルゴリズム] 動的計画法（Dynamic Programming / DP）

動的計画法（Dynamic Programming / DP） は、複雑な問題を小さな部分問題に分割し、それらの部分問題を解決することによって全体の問題を解決するアルゴリズム手法。
- メモ化（Memoization）
  - 部分問題の解を保存して再利用すること。
  - 計算の繰り返しを避け、効率的に問題を解くことができる。
- 代表的な動的計画法の例
  - フィボナッチ数列(Fibonacci sequence)
    - 再帰的に計算する場合、同じ計算を何度も行うのを避けるため、計算済みの値をメモ化する。
  - ナップサック問題(Knapsack Problem)
    - 与えられた容量のナップサック（リュックサック）に、重さと価値が決まった物品を入れていき、ナップサックの容量を超えない範囲で、価値の総和が最大となるように物品を選ぶ問題。
      - 重さ10、価値60の物品Aと重さ20、価値100の物品Bがある。ナップサックの容量が50の場合、どの組み合わせで物品を入れれば価値が最大になるか。
  - 最長共通部分列（Longest Common Subsequence, LCS）
    - 2つの文字列の中から共通の部分列を見つけ、その中で最も長いものを求める問題。
      - 文字列 "AGGTAB" と "GXTXAYB" がある。この2つの文字列の中で最も長い共通の部分列は "GTAB" であり、その長さは4。

ナップサック問題のC++での実装

#include <iostream>
#include <vector>
using namespace std;

// ナップサック問題を解くための関数
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    // dpテーブルの初期化、n + 1行、W + 1列の2次元ベクトル
    vector<vector<int>> dp(n + 1, vector<int>(W + 1));

    // dpテーブルを埋めるためのループ
    for (int i = 0; i <= n; i++) { // iはアイテムのインデックス
        for (int w = 0; w <= W; w++) { // wはナップサックの容量
            if (i == 0 || w == 0) // ベースケース: アイテムが0個または容量が0の場合
                dp[i][w] = 0;
            else if (wt[i - 1] <= w) // 現在のアイテムの重さがナップサックの容量に収まる場合
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                // アイテムを入れる場合の価値と、入れない場合の価値の大きい方を選ぶ
            else
                dp[i][w] = dp[i - 1][w]; // 現在のアイテムの重さがナップサックの容量を超える場合、アイテムを入れない
        }
    }
    return dp[n][W]; // dpテーブルの最後のセルが最大価値を示す
}

int main() {
    int W = 50; // ナップサックの容量
    vector<int> wt = {10, 20, 30}; // アイテムの重さ
    vector<int> val = {60, 100, 120}; // アイテムの価値
    int n = wt.size(); // アイテムの数
    cout << "ナップサックの最大価値: " << knapsack(W, wt, val, n) << endl; // 結果を出力
    return 0;
}

出力

ナップサックの最大価値: 220

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up