前言

有向和无向图实现方式

图的实现
  1. type NodeType = string | number;
  2. interface GNode {
  3.   key: NodeType;
  4.   value: NodeType;
  5. }
  6. interface Edge {
  7.   a: NodeType;
  8.   b: NodeType;
  9.   weight: number;
  10. }
  11. class Graph {
  12.   nodes: GNode[] = [];
  13.   edges: Map<string, Edge> = new Map();
  14.   directed: boolean = true;
  15.   constructor(directed: boolean = true) {
  16.     this.directed = directed;
  17.   }
  18.   addNode(key: NodeType, value: NodeType = key) {
  19.     this.nodes.push({ key, value });
  20.   }
  21.   removeNode(key: NodeType) {
  22.     this.nodes = this.nodes.filter((node: GNode) => node.key !== key);
  23.     [...this.edges.values()].forEach(({ a, b }) => {
  24.       if (a === key || b === key) this.edges.delete(JSON.stringify([a, b]));
  25.     });
  26.   }
  27.   addEdge(a: NodeType, b: NodeType, weight: number) {
  28.     this.edges.set(JSON.stringify([a, b]), { a, b, weight });
  29.     if (!this.directed)
  30.       this.edges.set(JSON.stringify([b, a]), { a: b, b: a, weight });
  31.   }
  32.   removeEdge(a: NodeType, b: NodeType) {
  33.     this.edges.delete(JSON.stringify([a, b]));
  34.     if (!this.directed) this.edges.delete(JSON.stringify([b, a]));
  35.   }
  36.   findNode(key: NodeType) {
  37.     return this.nodes.find((node: GNode) => node.key === key);
  38.   }
  39.   hasEdge(a: NodeType, b: NodeType) {
  40.     return this.edges.has(JSON.stringify([a, b]));
  41.   }
  42.   getEdgeWeight(a: NodeType, b: NodeType) {
  43.     return this.edges.get(JSON.stringify([a, b]))?.weight;
  44.   }
  45.   setEdgeWeight(a: NodeType, b: NodeType, weight: number) {
  46.     return this.addEdge(a, b, weight);
  47.   }
  48.   // 获取 key 节点指向的所有节点
  49.   adjacent(key: NodeType): NodeType[] {
  50.     return [...this.edges.values()].reduce((acc, { a, b }) => {
  51.       if (key === a) acc.push(b);
  52.       return acc;
  53.     }, []);
  54.   }
  55.   indegree(key: NodeType): number {
  56.     return [...this.edges.values()].reduce((count, { a, b }) => {
  57.       if (key === b) count++;
  58.       return count;
  59.     }, 0);
  60.   }
  61.   outdegree(key: NodeType): number {
  62.     return [...this.edges.values()].reduce((count, { a, b }) => {
  63.       if (key === a) count++;
  64.       return count;
  65.     }, 0);
  66.   }
  67. }