Data Structure & Algorithm(EP.12) — กราฟ(Graphs)

KongRuksiam Studio
3 min readFeb 28, 2024

--

Graphs เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น (Non-Linear) ที่กล่าวถึงความสัมพันธ์ระหว่างโหนดที่เชื่อมความสัมพันธ์ด้วยเส้นเชื่อมโยง (Edge)โครงสร้างข้อมูลกราฟถูกนำไปใช้ในระบบงานที่เป็นประเภทเครือข่าย การวิเคราะห์เส้นทางในการเดินทาง และการเชื่อมโยงหากันในระยะทางที่สั้นที่สุด

ประเภทของกราฟ (Graphs)

  1. กราฟแบบไม่มีทิศทาง (Undirected Graph)
  2. กราฟแบบมีทิศทาง (Directed Graph)
กราฟแบบไม่มีทิศทาง คือ กราฟที่ไม่มีการระบุทิศทาง (มีความสัมพันธ์แบบ 2 ทิศทาง)
กราฟแบบมีทิศทาง คือ กราฟที่มีการระบุทิศทางแต่ละเส้นจะมีลูกศรกำกับเพื่อบอกทิศทาง ซึ่งจะสามารถเดินทางไปตามที่หัวลูกศรอยู่เท่านั้น

การแทนกราฟ คือ การจัดการกราฟ เพื่อให้เห็นภาพรวมของกราฟและสามารถทำงานกับกราฟได้ง่ายมากยิ่งขึ้น ซึ่งมี 2 วิธี คือ

  • Adjacency Matrix
  • Adjacency List

Adjacency Matrix คือ การเก็บข้อมูลหรือแจกแจงความสัมพันธ์ภายในกราฟในลักษณะตาราง (Matrix)

ข้อกำหนด

  • ถ้ามีเส้นเชื่อมโยงระหว่าง Vertex ให้เก็บค่า 1
  • ถ้าไม่มีเส้นเชื่อมโยงระหว่าง Vertex จะเก็บค่า 0
แทนเลขน้ำหนักแต่ละเส้นลงไปในตาราง

Adjacency List

สร้างกราฟ (Graphs) โดยใช้การแทนกราฟแบบ Adjacency List

class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
return true;
}
return false;
}
}
let myGraph = new Graph();
myGraph.addVertex("A");
console.log(myGraph);
console.log(myGraph.addVertex("A"))

การเพิ่มเอดจ์ (Edge)

class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
return true;
}
return false;
}
addEdge(vertex1, vertex2) {
if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
return true;
}
return false;
}
}
let myGraph = new Graph();
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addEdge("A", "B");
console.log(myGraph);

การลบเอดจ์ (Edge)

class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
return true;
}
return false;
}
addEdge(vertex1, vertex2) {
if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
return true;
}
return false;
}
removeEdge(vertex1, vertex2) {
if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
(v) => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
(v) => v !== vertex1
);
return true;
}
return false;
}
}
let myGraph = new Graph();
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addVertex("C");
myGraph.addEdge("A", "B");
myGraph.addEdge("B", "C");
myGraph.addEdge("C", "A");
// myGraph.removeEdge("A","B")
console.log(myGraph);

เนื้อหาที่เกี่ยวข้อง

ช่องทางการสนับสนุน
🎓 คอร์สพัฒนาเว็บด้วย JavaScript 40 Workshop

🌎 ติดตามข่าวสารเพิ่มเติมได้ที่
Facebook | YouTube | TikTok

--

--

KongRuksiam Studio
KongRuksiam Studio

Written by KongRuksiam Studio

เรียนรู้การเขียนโปรแกรมนอกห้องเรียน

No responses yet