我们将创建一个支持权重以及有向和无向类型的图类。这将使用邻接表来实现。随着我们转向更高级的概念,图形的权重和有向性质都将派上用场。
邻接列表是单独列表的数组A。数组Ai的每个元素都是一个列表,其中包含与顶点i相邻的所有顶点。我们使用2个成员,节点和边来定义它。
让我们通过定义我们的类和一些用于向图添加节点和边的方法来设置图类。
我们将首先定义以下方法-
addNode:将节点添加到图中
addEdge:将无方向的边添加到图形中
addDirectedEdge:添加有向边
class Graph { constructor() { this.edges = {}; this.nodes = []; } addNode(node) { this.nodes.push(node); this.edges[node] = []; } addEdge(node1, node2) { this.edges[node1].push(node2); this.edges[node2].push(node1); } addDirectedEdge(node1, node2) { this.edges[node1].push(node2); } display() { let graph = ""; this.nodes.forEach(node => { graph += node + "->" + this.edges[node].join(", ") + "\n"; }); console.log(graph); } }
您可以使用以下方法测试这些方法和我们的类:
let g = new Graph(); g.addNode("A"); g.addNode("B"); g.addNode("C"); g.addNode("D"); g.addNode("E"); g.addEdge("A", "C"); g.addEdge("A", "B"); g.addDirectedEdge("A", "D"); g.addEdge("D", "E"); g.display();
输出结果
这将给出输出-
A->C, B, D B->A C->A D->E E->D