图¶

概念¶

图 (Graph) :G = (V, E)。V 代表 Vertex，E 代表 Edge，即一个顶点对 (u, v)。
权值：一个顶点到另一个顶点的 "代价"。若不联通，则认为无限大。
图的数据结构可用 邻接表(Adjacency List) 或 邻接矩阵(Adjacency Matrix) 表示。
邻接表，可表示为以顶点为key值的二维数组。
邻接矩阵，可表示为|V|*|V|的矩阵 Matrix。若(u, v)联通，则 Matrix[u][v] = 1；若边有加权，则 Matrix[u][v] = 权值。

图的遍历¶

深度优先遍历 (Depth-First Search)
广度优先遍历 (Breadth-First Search)

图的最短路径¶

广度优先遍历，获取无权最短路径
为什么说 广度优先搜索 可以用来求 无权最短路径 呢？
因为广度优先搜索每次都会先发现距离s为k的所有顶点，然后才会发现距离s为k+1的所有顶点。 s为起始点。
Dijkstra算法
Dijkstra算法是典型的单源最短路径算法，用于计算**带权有向图**一个节点到其他所有节点的最短路径。
算法步骤：
- 1) G = (V,E) 是一个带权有向图，图中顶点两组，S 和 U。
- 2) 初始，S 只包含源点，即S＝{ v }，v 的距离为0；U 包含除v外其他顶点。若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
- 3) 从 U 中选取一个距离 v 最小的顶点 k，把 k 加入 S （该距离就是 v 到 k 的最短路径长度）。
- 4) 以 k 为中间点，修改 U 中各顶点的距离。若从源点v到顶点u的距离（经过k）比原来距离（不经过k）短，则修改顶点 u 的距离值。
- 5) 重复步骤 3 和 4 ，直到所有顶点都包含在S中。

拓扑排序¶

“The algorithm for topological sorting is similar to the algorithm for depth-first search.”

GraphVertex¶

graph/GraphVertex.js

import LinkedList from '../linked-list/LinkedList.js'

export default class GraphVertex {
  /**
   * @param {*} value
   */
  constructor(value) {
    if (value === undefined) {
      throw new Error('Graph vertex must have a value');
    }

    const edgeComparator = (edgeA, edgeB) => {
      if (edgeA.getKey() === edgeB.getKey()) {
        return 0;
      }

      return edgeA.getKey() < edgeB.getKey() ? -1 : 1;
    };

    this.value = value;
    this.edges = new LinkedList(edgeComparator);
  }

  /**
   * @returns {string}
   */
  getKey() {
    return this.value;
  }

  /**
   * @param {GraphEdge} edge
   * @returns {GraphVertex}
   */
  addEdge(edge) {
    this.edges.append(edge);

    return this;
  }

  deleteEdge(edge) {
    this.edges.delete(edge);
  }

  findEdge(vertex) {
    const edge = this.edges.find({
      callback: edge => edge.startVertex === vertex || edge.endVertex === vertex
    });

    return edge ? edge.value : null;
  }

  /**
   * @returns {GraphVertex[]}
   */
  getNeighbors() {
    const edges = this.edges.toArray();

    return edges.map(linkedListNode => linkedListNode.value.startVertex === this
      ? linkedListNode.value.endVertex
      : linkedListNode.value.startVertex
    );
  }

  /**
   * @return {GraphEdge[]}
   */
  getEdges() {
    const edges = this.edges.toArray();

    return edges.map(linkedListNode => linkedListNode.value);
  }

  getDegree() {
    return this.edges.toArray().length;
  }
}

GraphEdge¶

graph/GraphEdge.js

export default class GraphEdge {
  constructor(startVertex, endVertex, weight = 0) {
    this.startVertex = startVertex;
    this.endVertex = endVertex;
    this.weight = weight;
  }

  getKey() {
    return `${this.startVertex.getKey()}_${this.endVertex.getKey()}`;
  }
}

Graph¶

graph/Graph.js

export default class Graph {
  constructor(isDirected = false) {
    this.vertices = {};
    this.edges = {};
    this.isDirected = isDirected;
  }

  /**
   * @param {GraphVertex} newVertex
   * @returns {Graph}
   */
  addVertex(newVertex) {
    this.vertices[newVertex.getKey()] = newVertex;

    return this;
  }

  getVertexByKey(vertexKey) {
    return this.vertices[vertexKey];
  }

  /**
   * @return {GraphVertex[]}
   */
  getAllVertices() {
    return Object.values(this.vertices);
  }

  /**
   * @return {GraphEdge[]}
   */
  getAllEdges() {
    return Object.values(this.edges);
  }

  /**
   * @return {GraphEdge|null}
   */
  findEdge(startVertex, endVertex) {
    const vertex = this.getVertexByKey(startVertex.getKey());

    if (!vertex) {
      return null;
    }

    return vertex.findEdge(endVertex);
  }

  /**
   * @param {GraphEdge} edge
   * @returns {Graph}
   */
  addEdge(edge) {
    let startVertex = this.getVertexByKey(edge.startVertex.getKey());
    let endVertex = this.getVertexByKey(edge.endVertex.getKey());

    // 若无节点，先插入
    if (!startVertex) {
      this.addVertex(edge.startVertex);
      startVertex = this.getVertexByKey(edge.startVertex.getKey());
    }

    // 若无节点，先插入
    if (!endVertex) {
      this.addVertex(edge.endVertex);
      endVertex = this.getVertexByKey(edge.endVertex.getKey());
    } 

    // Check 边是否已添加过
    if (this.edges[edge.getKey()]) {
      throw new Error('边已存在！');
    } else {
      this.edges[edge.getKey()] = edge;
    }

    if (this.isDirected) {
      startVertex.addEdge(edge);
    } else {
      startVertex.addEdge(edge);
      endVertex.addEdge(edge);
    }

    return this;
  }

  /**
   * @param {GraphEdge} edge
   */
  deleteEdge(edge) {
    if (this.edges[edge.getKey()]) {
      delete this.edges[edge.getKey()];
    } else {
      throw new Error('Edge not found');
    }

    const startVertex = this.getVertexByKey(edge.startVertex.getKey());
    const endVertex = this.getVertexByKey(edge.endVertex.getKey());

    startVertex.deleteEdge(edge);
    endVertex.deleteEdge(edge);
  }

  /**
   * @return {*[][]}
   */
  getAdjacencyMatrix() {
    const vertices = this.getAllVertices();
    const verticesIndices = vertices.reduce((acc, vertex, index) => ({
      ...acc,
      [vertex.getKey()]: index
    }), {});


    // 初始化邻接矩阵
    // Infinity 表示顶点之间不通
    const adjacencyMatrix = Array(vertices.length).fill(null).map(() => {
      return Array(vertices.length).fill(Infinity);
    });

    vertices.forEach((vertex, vertexIndex) => {
      vertex.getNeighbors().forEach(neighbor => {
        const neighborIndex = verticesIndices[neighbor.getKey()];
        adjacencyMatrix[vertexIndex][neighborIndex] = this.findEdge(vertex, neighbor).weight;
      });
    });

    return adjacencyMatrix;
  }

  /**
   * 深度优先遍历算法
   * 1. 从开始顶点搜索一条路径，直到无路可走；
   * 2. 回退到上一顶点，往下继续遍历未访问过的顶点；
   * 3. 依次类推，直到所有的顶点都已经访问过。
   * */
  depthFirstSearch(vertex, callback) {}

  /**
   * 广度优先遍历算法
   * 1. 取当前节点的一个未被访问的邻节点，标记为已访问，加入队列；
   * 2. 取下一个节点 v，标记为已访问；
   * 3. 将 v 邻节点中所有未访问的节点加入队列。
   * */
  breadthFirstSearch(vertex, callback) {}

  /**
   * 无权最短路径(伪代码)
   * */  
  pathTo(target) {
    const edgeTo = []; //记录从一个到另一个顶点的边
    const marked = []; // 记录已访问过的顶点
    this.bfs(0, vertex => {
      edgeTo[vertex] = 前一个邻节点; 
      marked[vertex] = true;
    });

    // 若v未被访问过，则说明从0到v无路可走
    if(!marked[v]) {
      return null;
    }

    // 假设起点为0，target 为目标顶点
    const path = [];
    const source = 0;
    for(let i = target; i != source; i = edgeTo[i]) {
      path.unshift(i);
    }
    path.unshift(source);

    return path;
  }

  /**
   * 拓扑排序(伪代码)
   * 定义：将 **有向无环图** 的顶点以线性方式排序；
   * 对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。
   * “The algorithm for *topological sorting* is similar to the algorithm for 
   * depth-first search*.”
   * */
  topSort() {
    const stack = [];

    const visited = [];
    for (var i = 0; i < this.vertices; i++) {
      visited[i] = false;
    }

    for (var i = 0; i < this.vertices; i++) {
      if (visited[i] === false) {
        this.topSortRecursive(i, visited, stack);
      }
    }

    return stack;
  }

  /**
   * 拓扑排序递归(伪代码)
   * */
  topSortRecursive(v, visited, stack) {
    visited[v] = true;
    this.adj[v].forEach(w => {
      if (!visited[w]) {
        this.topSortRecursive(w, visited, stack);
      }
   });
   stack.unshift(v);
  }
}