【TypeScriptで学ぶデータ構造】グラフ

グラフ

頂点と辺で構成されるデータ構造

グラフを再現したクラス

Graph.ts

//グラフの頂点を表すクラス
class GraphNode<T> {
  public value: T;
  public adjacent: Set<GraphNode<T>>;

  constructor(value: T) {
    this.value = value;
    this.adjacent = new Set();
  }
}

//グラフを表すクラス
class Graph<T> {
  private nodes: Map<T, GraphNode<T>>;

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

  //頂点を追加するメソッド
  public addVertex(value: T): GraphNode<T> {
    let node = this.nodes.get(value);
    if (!node) {
      node = new GraphNode(value);
      this.nodes.set(value, node);
    }
    return node;
  }

  //辺を追加するメソッド（無向グラフ→辺に方向がないグラフです）
  public addEdge(value1: T, value2: T): void {
    const node1 = this.addVertex(value1);
    const node2 = this.addVertex(value2);
    node1.adjacent.add(node2);
    node2.adjacent.add(node1); //無向グラフなので両方向に追加
  }

  //グラフを出力するメソッド
  public printGraph(): void {
    for (const [key, node] of this.nodes) {
      const adjacentValues = [...node.adjacent].map((n) => n.value).join(", ");
      console.log(`${key} --> ${adjacentValues}`);
    }
  }

  //頂点に隣接するノードを取得するメソッド
  public getAdjacentNodes(value: T): T[] | null {
    const node = this.nodes.get(value);
    if (node) {
      return [...node.adjacent].map((n) => n.value);
    }
    return null;
  }

  //深さ優先探索 
  public depthFirstSearch(start: T): void {
    const startNode = this.nodes.get(start);
    if (!startNode) return;

    const visited = new Set<GraphNode<T>>();

    const dfs = (node: GraphNode<T>) => {
      if (visited.has(node)) return;
      visited.add(node);
      console.log(node.value);

      node.adjacent.forEach((neighbor) => {
        dfs(neighbor);
      });
    };

    dfs(startNode);
  }

  //幅優先探索 
  public breadthFirstSearch(start: T): void {
    const startNode = this.nodes.get(start);
    if (!startNode) return;

    const visited = new Set<GraphNode<T>>();
    const queue: GraphNode<T>[] = [startNode];

    while (queue.length > 0) {
      const currentNode = queue.shift();
      if (!currentNode || visited.has(currentNode)) continue;

      visited.add(currentNode);
      console.log(currentNode.value);

      currentNode.adjacent.forEach((neighbor) => {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      });
    }
  }
}

//グラフの使用例
const graph = new Graph<number>();

//頂点と辺の追加
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(4, 5);

console.log("Graph structure:");
graph.printGraph(); //グラフの構造を表示

console.log("\nDepth-First Search (DFS):");
graph.depthFirstSearch(1); //深さ優先探索

console.log("\nBreadth-First Search (BFS):");
graph.breadthFirstSearch(1); //幅優先探索