TypeScript上級

上級 TypeScriptで学ぶデータ構造｜練習問題編

 

導入

データ構造はプログラミングの根幹を成す要素であり、特に業務システムにおいては効率的なデータ処理が求められます。ここでは、TypeScriptを用いて、特定のデータ構造の実装に焦点を当て、その実務での活用方法を探ります。具体的には、グラフデータ構造を取り上げ、業務で直面しがちな問題点とその解決策について考察します。

教科書レベルの解説（データ構造）

重要な概念の整理

グラフは、ノード（頂点）とそれらをつなぐエッジ（辺）から構成されるデータ構造です。ネットワークのモデル化や、経路探索アルゴリズムに利用されます。特に、実務においては、リレーショナルデータベースの設計や、ソーシャルネットワークの分析など、さまざまなシナリオで使用されます。グラフの実装には、隣接リストや隣接行列といった手法があり、選択するデータ構造によって性能に大きな影響を与えることがあります。

コード例（TypeScript）


class Graph {
    private adjacencyList: Map;

    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(vertex: string) {
        this.adjacencyList.set(vertex, []);
    }

    addEdge(vertex1: string, vertex2: string) {
        this.adjacencyList.get(vertex1)?.push(vertex2);
        this.adjacencyList.get(vertex2)?.push(vertex1);
    }

    getVertices() {
        return Array.from(this.adjacencyList.keys());
    }

    getEdges() {
        const edges: string[] = [];
        this.adjacencyList.forEach((neighbors, vertex) => {
            neighbors.forEach(neighbor => {
                edges.push(`${vertex} - ${neighbor}`);
            });
        });
        return edges;
    }
}

コードの行ごとの解説

  1. class Graph { – グラフを表現するクラスの定義です。
  2. private adjacencyList: Map; – 隣接リストを格納するためのマップを定義します。
  3. constructor() { this.adjacencyList = new Map(); } – コンストラクタで隣接リストの初期化を行います。
  4. addVertex(vertex: string) { this.adjacencyList.set(vertex, []); } – 新しい頂点を追加するメソッドです。
  5. addEdge(vertex1: string, vertex2: string) { … } – 二つの頂点を結ぶエッジを追加します。
  6. getVertices() { … } – グラフ内の全ての頂点を取得するメソッドです。
  7. getEdges() { … } – グラフ内の全てのエッジを取得するメソッドです。

練習問題編

以下の練習問題に取り組んで、グラフデータ構造の理解を深めてください。

  1. 問題1: グラフに新しい頂点を追加するメソッドを拡張して、重複する頂点が追加されないようにしてください。
  2. 問題2: グラフのエッジを削除するメソッドを実装してください。
  3. 問題3: グラフの深さ優先探索（DFS）を実装し、特定の頂点から他の頂点への経路を探索できるようにしてください。
  4. 問題4: グラフの隣接行列を生成するメソッドを実装してください。
  5. 問題5: グラフの全ての頂点とエッジを出力するメソッドを追加してください。

まとめ

  • グラフデータ構造は、業務システムにおいて重要な役割を果たします。
  • 隣接リストの実装は、効率的なメモリ使用を実現し、特定の操作に対して優れた性能を発揮します。
  • 練習問題を通じて、実務での応用力を高めることが期待されます。
RELATED POST