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

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

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

ソートとは、データを特定の順序（通常は昇順または降順）に並べ替えること。

バブルソート（Bubble Sort）

Bubble Sort Comparison Based Sorts - LeetCode

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n)	O(n^2)	O(1)

選択ソート（Selection Sort）

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n^2)	O(n^2)	O(1)

挿入ソート（Insertion Sort）

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n^2)	O(n^2)	O(1)

マージソート（Merge Sort）

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n log(n))	O(n log(n))	O(n)

クイックソート（Quick Sort）

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n log(n))	O(n^2)	O(log(n))

ヒープソート（Heap Sort）

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n log(n))	O(n log(n))	O(1)

バケットソート（Bucket Sort）

平均時間計算量	最悪時間計算量	最悪領域計算量
O(n+k)	O(n^2)	O(n+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}に分類して管理するためのデータ構造。

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）
• 最短経路（Shortest Path）

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

参考

• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
• 問題解決力を鍛える!アルゴリズムとデータ構造
• 新・明解C言語で学ぶアルゴリズムとデータ構造第2版
• 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~
• 第五章 Data Structures & Algorithms (DSA) - InterviewCat
• Coding Interview University(JA) - GitHub
• Data Structures & Algorithms - Google Tech Dev Guide
• Big-O Cheat Sheet
• Learn - LeetCode