Data Structure & Algorithm(EP.12) — กราฟ(Graphs)
3 min readFeb 28, 2024
Graphs เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น (Non-Linear) ที่กล่าวถึงความสัมพันธ์ระหว่างโหนดที่เชื่อมความสัมพันธ์ด้วยเส้นเชื่อมโยง (Edge)โครงสร้างข้อมูลกราฟถูกนำไปใช้ในระบบงานที่เป็นประเภทเครือข่าย การวิเคราะห์เส้นทางในการเดินทาง และการเชื่อมโยงหากันในระยะทางที่สั้นที่สุด
ประเภทของกราฟ (Graphs)
- กราฟแบบไม่มีทิศทาง (Undirected Graph)
- กราฟแบบมีทิศทาง (Directed Graph)
การแทนกราฟ คือ การจัดการกราฟ เพื่อให้เห็นภาพรวมของกราฟและสามารถทำงานกับกราฟได้ง่ายมากยิ่งขึ้น ซึ่งมี 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);
บทความที่เกี่ยวข้อง
- EP.1 — รู้จักกับโครงสร้างข้อมูลและอัลกอริทึม
- EP.2 — การวัดประสิทธิภาพอัลกอริทึม
- EP.3 — อัตราการเติบโตของฟังก์ชั่น
- EP.4 — การวิเคราะห์อัลกอริทึม
- EP.5 — Big-O Notation
- EP.6 — การคำนวณ Big-O
- EP.7 — ลิงค์ลิสต์ (Linked-List)
- EP.8 — สแต็ก (Stack)
- EP.9 — คิว(Queue)
- EP.10 — ทรี (Tree)
- EP.11 — Binary Search Tree (BST)
- EP.12 — กราฟ(Graphs)
เนื้อหาที่เกี่ยวข้อง
ช่องทางการสนับสนุน
🎓 คอร์สพัฒนาเว็บด้วย JavaScript 40 Workshop