การสร้างกราฟใน Javascript

เราจะสร้างคลาสกราฟที่รองรับน้ำหนักและทั้งแบบกำกับและแบบไม่บอกทิศทาง สิ่งนี้จะดำเนินการโดยใช้รายการที่อยู่ติดกัน เมื่อเราเปลี่ยนไปใช้แนวคิดขั้นสูง ทั้งการถ่วงน้ำหนักและลักษณะการกำกับของกราฟจะมีประโยชน์อย่างยิ่ง

รายการที่อยู่ติดกันคืออาร์เรย์ 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