【Day20】[资料结构]-图Graph-实作

图(Graph)建立的方法

• addVertex: 新增顶点
• addEdge: 新增边
• removeVertex: 删除顶点
• removeEdge: 删除边

图的介绍可以参考此篇。

JavaScript

• 无向图
• 相邻串列 (Adjacency List)

class Graph {
  constructor() {
    this.adjacencyList = {}
  }

  //新增顶点
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = []
    } else {
      return '顶点已存在';
    }
  }
  
  //新增边
  addEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1]) {
      if (this.adjacencyList[vertex2]){
        this.adjacencyList[vertex1].push(vertex2)
        this.adjacencyList[vertex2].push(vertex1)
      }else {
        return '第二项顶点不存在';
      }
    } else {
      return '第一项顶点不存在';
    }
  }
  
  //删除顶点
  removeVertex(vertex) {
    if (this.adjacencyList[vertex]) {
      this.adjacencyList[vertex].forEach(function(item) {
        this.removeEdge(vertex, item)
        delete this.adjacencyList[vertex]
      });
    } else {
      return '此顶点已不存在';
    }
  }
  
  //删除边
  removeEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1]) {
      if (this.adjacencyList[vertex2]){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
          (vertex) => vertex !== vertex2
        )
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
          (vertex) => vertex !== vertex1
        )
      }else {
        return '第二项顶点已不存在';
      }
    } else {
      return '第一项顶点已不存在';
    }
  }

  printGraph(){
    console.log(this.adjacencyList)
  }

}

let graph = new Graph();

graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

graph.addEdge('A', 'B');
graph.addEdge('A', 'D');
graph.addEdge('A', 'E');
graph.addEdge('B', 'C');
graph.addEdge('D', 'E');
graph.addEdge('E', 'F');
graph.addEdge('E', 'C');
graph.printGraph();
//{
//  A: ["B", "D", "E"],
//  B: ["A", "C"],
//  C: ["B", "E"],
//  D: ["A", "E"],
//  E: ["A", "D", "F", "C"],
//  F: ["E"]
//}

Python

• 无向图
• 使用Numpy实作相邻矩阵(Adjacency Matrix)

import numpy as np
 
vertices = {0, 1, 2, 3, 4}
edges = {(0, 1), (1, 2), (0, 3), (1, 3), (3, 4)}
adjacencyMatrix = np.zeros((5, 5)).astype(int)
for edge in edges:
    v1 = edge[0]
    v2 = edge[1]
    adjacencyMatrix[v1][v2] = 1
    adjacencyMatrix[v2][v1] = 1
print("Vertices:",vertices)
print("Edges:",edges)
print(adjacencyMatrix)
#Vertices: {0, 1, 2, 3, 4}
#Edges: {(0, 1), (1, 2), (1, 3), (0, 3), (3, 4)}
#[[0 1 0 1 0]
# [1 0 1 1 0]
# [0 1 0 0 0]
# [1 1 0 0 1]
# [0 0 0 1 0]]