TypeScript의 데이터 구조 - 그래프

그래프는 에지로 다른 정점과 연결할 수 있는 정점(또는 노드)으로 구성된 데이터 구조입니다.



차수는 정점에 연결된 모서리의 수입니다. 예를 들어 정점 A의 차수는 1이고 정점 C의 차수는 2입니다.

그래프는 방향성 또는 무방향성일 수 있으며 방향성 그래프는 일방통행과 같고 무방향성 그래프는 양방향과 같습니다.



그래프에도 주기가 있을 수 있습니다.



그래프는 연결되지 않은 것일 수 있습니다. 즉, 분리된 하위 그래프로 구성되거나 모든 노드 쌍이 모두 에지로 연결된 연결된 것으로 구성됩니다.



그래프는 네트워크, 웹 사이트 구조를 나타내는 데 사용할 수 있으며 경로 최적화 알고리즘에도 사용되며 언어학, 물리학, 화학, 생물학, 수학 등과 같은 다른 분야의 응용 프로그램이 있습니다.

대표

그래프는 다음과 같이 나타낼 수 있습니다.

인접 목록 - 모든 노드는 인접한 정점의 목록을 저장합니다. 예를 들어 배열 또는 모든 정점을 포함하고 각 정점에는 인접한 정점이 있는 다른 배열이 포함되어 있습니다. 배열 대신 해시 테이블 및 링크된 데이터 구조와 같은 다른 데이터 구조를 사용할 수 있습니다. 목록.

인접 행렬 - NxN 부울 행렬(여기서 N은 꼭지점의 수), 행렬[i][j]가 true 값을 저장하는 경우 꼭지점 i와 j 사이에 연결이 있습니다. 무향 그래프에서 matrix[j][i]도 true 값을 저장합니다. 부울 대신 다른 유형을 사용할 수 있습니다(예: 가중치를 나타내는 숫자).

그래프 검색

깊이 우선 검색

깊이 우선 검색은 그래프를 탐색하는 방법으로, 주어진 정점에서 시작하여 다른 분기로 이동하기 전에 각 분기를 완전히 방문합니다. DFS는 그래프의 모든 노드를 방문해야 할 때 자주 사용됩니다.



위의 그래프에서 DPS를 사용하면 A, B, D, C, E, F 순서로 노드를 방문하게 됩니다.

너비 우선 검색

이것은 그래프를 탐색하는 또 다른 방법으로, 주어진 정점에서 시작하여 자식으로 이동하기 전에 인접한 모든 정점을 방문합니다. BFS는 두 노드 사이의 경로를 찾는 데 유용합니다.



위의 그래프에서 DPS를 사용하면 A, B, E, F, D, C 순서로 노드를 방문하게 됩니다.

양방향 검색

두 개의 너비 우선 검색을 동시에 실행하는 것으로 구성되며, 각각 다른 정점에서 시작하여 충돌할 때까지 실행됩니다. 이것은 두 정점 사이의 최단 경로를 찾는 데 유용합니다.



다음은 인접 목록을 사용하여 방향성 그래프를 구현한 것입니다. 거의 모든 작업에서 더 잘 수행되기 때문입니다.

export class Node<T> {
  data: T;
  adjacent: Node<T>[];
  comparator: (a: T, b: T) => number;

  constructor(data: T, comparator: (a: T, b: T) => number) {
    this.data = data;
    this.adjacent = [];
    this.comparator = comparator;
  }

  addAdjacent(node: Node<T>): void {
    this.adjacent.push(node);
  }

  removeAdjacent(data: T): Node<T> | null {
    const index = this.adjacent.findIndex(
      (node) => this.comparator(node.data, data) === 0
    );

    if (index > -1) {
      return this.adjacent.splice(index, 1)[0];
    }

    return null;
  }
}

class Graph<T> {
  nodes: Map<T, Node<T>> = new Map();
  comparator: (a: T, b: T) => number;

  constructor(comparator: (a: T, b: T) => number) {
    this.comparator = comparator;
  }

  /**
   * Add a new node if it was not added before
   *
   * @param {T} data
   * @returns {Node<T>}
   */
  addNode(data: T): Node<T> {
    let node = this.nodes.get(data);

    if (node) return node;

    node = new Node(data, this.comparator);
    this.nodes.set(data, node);

    return node;
  }

  /**
   * Remove a node, also remove it from other nodes adjacency list
   *
   * @param {T} data
   * @returns {Node<T> | null}
   */
  removeNode(data: T): Node<T> | null {
    const nodeToRemove = this.nodes.get(data);

    if (!nodeToRemove) return null;

    this.nodes.forEach((node) => {
      node.removeAdjacent(nodeToRemove.data);
    });

    this.nodes.delete(data);

    return nodeToRemove;
  }

  /**
   * Create an edge between two nodes
   *
   * @param {T} source
   * @param {T} destination
   */
  addEdge(source: T, destination: T): void {
    const sourceNode = this.addNode(source);
    const destinationNode = this.addNode(destination);

    sourceNode.addAdjacent(destinationNode);
  }

  /**
   * Remove an edge between two nodes
   *
   * @param {T} source
   * @param {T} destination
   */
  removeEdge(source: T, destination: T): void {
    const sourceNode = this.nodes.get(source);
    const destinationNode = this.nodes.get(destination);

    if (sourceNode && destinationNode) {
      sourceNode.removeAdjacent(destination);
    }
  }

  /**
   * Depth-first search
   *
   * @param {T} data
   * @param {Map<T, boolean>} visited
   * @returns
   */
  private depthFirstSearchAux(node: Node<T>, visited: Map<T, boolean>): void {
    if (!node) return;

    visited.set(node.data, true);

    console.log(node.data);

    node.adjacent.forEach((item) => {
      if (!visited.has(item.data)) {
        this.depthFirstSearchAux(item, visited);
      }
    });
  }

  depthFirstSearch() {
    const visited: Map<T, boolean> = new Map();
    this.nodes.forEach((node) => {
      if (!visited.has(node.data)) {
        this.depthFirstSearchAux(node, visited);
      }
    });
  }

  /**
   * Breadth-first search
   *
   * @param {T} data
   * @returns
   */
  private breadthFirstSearchAux(node: Node<T>, visited: Map<T, boolean>): void {
    const queue: Queue<Node<T>> = new Queue();

    if (!node) return;

    queue.add(node);
    visited.set(node.data, true);

    while (!queue.isEmpty()) {
      node = queue.remove();

      if (!node) continue;

      console.log(node.data);

      node.adjacent.forEach((item) => {
        if (!visited.has(item.data)) {
          visited.set(item.data, true);
          queue.add(item);
        }
      });
    }
  }

  breadthFirstSearch() {
    const visited: Map<T, boolean> = new Map();
    this.nodes.forEach((node) => {
      if (!visited.has(node.data)) {
        this.breadthFirstSearchAux(node, visited);
      }
    });
  }
}

function comparator(a: number, b: number) {
  if (a < b) return -1;

  if (a > b) return 1;

  return 0;
}

const graph = new Graph(comparator);