邻接矩阵图

介绍

实现

创建二维数组

:::details 点击查看代码

createTwoArray(n) {
    let array = [];
    for (let i = 0; i < n; i++) {
    array[i] = [];
    for (let j = 0; j < n; j++) {
        array[i][j] = 0;
    }
    }
    return array;
}

:::

添加顶点

:::details 点击查看代码

insertVertex(vertex) {
    this.vertexes.push(vertex);
}

:::

移除顶点

添加边

:::details 点击查看代码

insertEdge(vertex1, vertex2, weight) {
    const vertex1Index = this.getIndexOfVertex(vertex1);
    const vertex2Index = this.getIndexOfVertex(vertex2);
    this.edges[vertex1Index][vertex2Index] = weight;
    this.edges[vertex2Index][vertex1Index] = weight;
    this.count++;
}

:::

移除边

遍历图

获取相邻顶点

:::details 点击查看代码

getFirstNeighbor(index) {
          for (let i = 0; i < this.vertexes.length; i++) {
            if (this.edges[index][j] > 0) {
              return i;
            }
          }
          return -1;
        }

:::

判断是否相邻

根据相邻顶点的下一个顶点

:::details 点击查看代码

getNextNeighbor(vertex1, vertex2) {
          for (let i = vertex2 + 1; i < this.vertexes.length; i++) {
            if (this.edges[vertex1][i] > 0) {
              return i;
            }
          }
          return -1;
        }

:::

深度优先遍历访问 DFS

思想: 深度优先遍历基于栈结构。每次访问完当前节点后首先访问当前节点的第一个邻接节点

:::details 点击查看代码

:::

广度优先遍历访问 BFS

思想: 广度优先遍历基于队列结构。类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序访问这些节点的邻接节点

完整代码

:::details 点击查看代码

class Graph {
    vertexes = [];
    edges;
    count = 0;
    visited = [];
    constructor(n) {
      this.edges = this.createTwoArray(n);
    }
    createTwoArray(n) {
      let array = [];
      for (let i = 0; i < n; i++) {
        array[i] = [];
        for (let j = 0; j < n; j++) {
          array[i][j] = 0;
        }
      }
      return array;
    }
    insertVertex(vertex) {
      this.vertexes.push(vertex);
    }
    getIndexOfVertex(vertex) {
      return this.vertexes.indexOf(vertex);
    }
    insertEdge(vertex1, vertex2, weight) {
      const vertex1Index = this.getIndexOfVertex(vertex1);
      const vertex2Index = this.getIndexOfVertex(vertex2);
      this.edges[vertex1Index][vertex2Index] = weight;
      this.edges[vertex2Index][vertex1Index] = weight;
      this.count++;
    }
    getValueOfVertex(i) {
      return this.vertexes[i];
    }
    getFirstNeighbor(index) {
      for (let i = 0; i < this.vertexes.length; i++) {
        if (this.edges[index][i] > 0) {
          return i;
        }
      }
      return -1;
    }
    getNextNeighbor(vertex1, vertex2) {
      for (let i = vertex2 + 1; i < this.vertexes.length; i++) {
        if (this.edges[vertex1][i] > 0) {
          return i;
        }
      }
      return -1;
    }
    show() {
      return this.edges;
    }
    DFSTraverseByRecursion(vertexIndex) {
      let visited = [];
      let result = "";
      for (let i = 0; i < this.vertexes.length; i++) {
        visited[i] = false;
      }
      const DFS = (vertexIndex) => {
        result += this.getValueOfVertex(vertexIndex) + "->";
        visited[vertexIndex] = true;
        let vertexNeighborIndex = this.getFirstNeighbor(vertexIndex);
        while (vertexNeighborIndex != -1) {
          if (!visited[vertexNeighborIndex]) {
            DFS(vertexNeighborIndex);
          }
          vertexNeighborIndex = this.getNextNeighbor(
            vertexIndex,
            vertexNeighborIndex
          );
        }
      };
      for (let i = 0; i < this.vertexes.length; i++) {
        if (!visited[i]) {
          DFS(i);
        }
      }
      return result;
    }
    DFSTraverseByIteration(vertexIndex) {
      let visited = [];
      let result = "";
      for (let i = 0; i < this.vertexes.length; i++) {
        visited[i] = false;
      }
      const DFS = (vertexIndex) => {
        result += this.getValueOfVertex(vertexIndex) + "->";
        visited[vertexIndex] = true;
        let vertexNeighborIndex = this.getFirstNeighbor(vertexIndex);
        while (vertexNeighborIndex != -1) {
          if (!visited[vertexNeighborIndex]) {
            DFS(vertexNeighborIndex);
          }
          vertexNeighborIndex = this.getNextNeighbor(
            vertexIndex,
            vertexNeighborIndex
          );
        }
      };
      for (let i = 0; i < this.vertexes.length; i++) {
        if (!visited[i]) {
          DFS(i);
        }
      }
      return result;
    }
    BFSTraverseByRecursion() {
      let visited = [];
      let result = "";
      for (let i = 0; i < this.vertexes.length; i++) {
        visited[i] = false;
      }
      const BFS = (vertexIndex) => {
        result += this.getValueOfVertex(vertexIndex) + "->";
        visited[vertexIndex] = true;
        let queue = [];
        queue.push(vertexIndex);
        while (queue.length) {
          let queueHead = queue.shift();
          let vertexNeighborIndex = this.getFirstNeighbor(queueHead);
          while (vertexNeighborIndex != -1) {
            if (!visited[vertexNeighborIndex]) {
              result += this.getValueOfVertex(vertexNeighborIndex) + "->";
              visited[vertexNeighborIndex] = true;
              queue.push(vertexNeighborIndex);
            }
            vertexNeighborIndex = this.getNextNeighbor(
              vertexIndex,
              vertexNeighborIndex
            );
          }
        }
      };
      for (let i = 0; i < this.vertexes.length; i++) {
        if (!visited[i]) {
          BFS(i);
        }
      }
      return result;
    }
    BFSTraverseByIteration() {
      let visited = [];
      let result = "";
      for (let i = 0; i < this.vertexes.length; i++) {
        visited[i] = false;
      }
      const BFS = (vertexIndex) => {
        result += this.getValueOfVertex(vertexIndex) + "->";
        visited[vertexIndex] = true;
        let queue = [];
        queue.push(vertexIndex);
        while (queue.length) {
          let queueHead = queue.shift();
          let vertexNeighborIndex = this.getFirstNeighbor(queueHead);
          while (vertexNeighborIndex != -1) {
            if (!visited[vertexNeighborIndex]) {
              result += this.getValueOfVertex(vertexNeighborIndex) + "->";
              visited[vertexNeighborIndex] = true;
              queue.push(vertexNeighborIndex);
            }
            vertexNeighborIndex = this.getNextNeighbor(
              vertexIndex,
              vertexNeighborIndex
            );
          }
        }
      };
      for (let i = 0; i < this.vertexes.length; i++) {
        if (!visited[i]) {
          BFS(i);
        }
      }
      return result;
    }
  }

  const vertex = 5;
  const vertexValue = ["A", "B", "C", "D", "E"];
  const graph = new Graph(vertex);
  for (let i of vertexValue) {
    graph.insertVertex(i);
  }
  graph.insertEdge("A", "B", 1);
  graph.insertEdge("A", "C", 1);
  graph.insertEdge("B", "C", 1);
  graph.insertEdge("B", "D", 1);
  graph.insertEdge("B", "E", 1);
  console.log("遍历图的边");
  console.log(graph.show());
  console.log("深度优先遍历");
  console.log(graph.DFSTraverseByRecursion());
  console.log("广度优先遍历");
  console.log(graph.BFSTraverseByIteration());

:::