การสร้าง Graph ใน JavaScript

เราจะสร้าง graph class ที่รองรับ weights และทั้ง directed และ undirected types จะ implement ด้วย adjacency list เมื่อไปสู่ concepts ขั้นสูง weights และ directed nature จะมีประโยชน์

Adjacency list คือ array A ของ lists แยกกัน แต่ละ element Ai เป็น list ที่มี vertices ที่ adjacent กับ vertex i เรากำหนดด้วย 2 members คือ nodes และ edges

มาตั้งค่า graph class โดยกำหนด class และ methods ที่ใช้เพิ่ม nodes และ edges:

เราจะกำหนด methods เริ่มต้นดังนี้:

• addNode: เพิ่ม node ใน graph
• addEdge: เพิ่ม undirected edge ใน graph
• addDirectedEdge: เพิ่ม directed edge

ตัวอย่างโค้ด

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);
  }
}

ทดสอบ methods และ class ได้ดังนี้:

ตัวอย่างการใช้งาน

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