คำจำกัดความของแผนภาพ
กราฟประกอบด้วยชุดจุดยอดที่ไม่ว่างเปล่าและชุดของขอบระหว่างจุดยอด มันมักจะแสดงเป็น: g (v, e) โดยที่ g หมายถึงกราฟ, v คือชุดของจุดยอดในกราฟ G และ E คือชุดของขอบในกราฟ G
กราฟกำกับ
ขอบกำกับ: หากขอบจากจุดสุดยอด VI ถึง VJ มีทิศทางขอบนี้เรียกว่าขอบกำกับซึ่งกลายเป็นส่วนโค้ง (อาร์ค) มันแสดงโดย <vi, vj> ที่สั่งซื้อ VI เรียกว่าหางอาร์คและ VJ เรียกว่าหัวอาร์ค
ไดอะแกรมที่ไม่เป็นระเบียบ
ขอบที่ไม่ได้ทิศทาง: หากขอบระหว่างจุดยอด VI ถึง VJ ไม่มีทิศทางขอบนี้เรียกว่าขอบที่ไม่ได้ทิศทาง (ขอบ) และแสดงโดยคู่ที่ไม่ได้เรียงลำดับ (VI, VJ)
ภาพเรียบง่าย
ไดอะแกรมอย่างง่าย: ในโครงสร้างกราฟหากไม่มีจุดสุดยอดไปที่ขอบของตัวเองและขอบเดียวกันไม่ปรากฏซ้ำ ๆ ซ้ำ ๆ รูปภาพนี้เรียกว่าไดอะแกรมง่าย ๆ
ชั้นเรียนภาพ
หมายถึงจุดสุดยอด
ขั้นตอนแรกในการสร้างคลาสกราฟคือการสร้างคลาสจุดสุดยอดเพื่อบันทึกจุดยอดและขอบ คลาสนี้ทำหน้าที่เหมือนกับคลาสโหนดของรายการที่เชื่อมโยงและต้นไม้ค้นหาไบนารี คลาส Vertex มีสมาชิกข้อมูลสองคน: หนึ่งในการระบุจุดสุดยอดและอื่น ๆ เพื่อระบุว่ามีการเข้าถึงหรือไม่ พวกเขามีชื่อว่าฉลากและเยี่ยมชมตามลำดับ
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น Vertex (ป้ายกำกับ) {
this.label = label;
-
เราบันทึกจุดยอดทั้งหมดในอาร์เรย์และในคลาสกราฟเราสามารถอ้างถึงตำแหน่งของพวกเขาในอาร์เรย์
ระบุขอบ
ข้อมูลจริงของกราฟถูกเก็บไว้ใน "ขอบ" เพราะพวกเขาอธิบายโครงสร้างของกราฟ โหนดหลักของต้นไม้ไบนารีสามารถมีลูกสองโหนดเท่านั้น แต่โครงสร้างของกราฟมีความยืดหยุ่นมากขึ้น จุดสุดยอดสามารถมีขอบหนึ่งขอบหรือหลายขอบเชื่อมต่อกับมัน
เราจะใช้วิธีการแสดงขอบของกราฟเพื่อเป็นตาราง adjacency หรืออาร์เรย์ตาราง adjacency มันจะเก็บอาร์เรย์ที่ประกอบด้วยรายการจุดยอดที่อยู่ติดกันของจุดยอด
สร้างกราฟ
กำหนดคลาสกราฟต่อไปนี้:
การคัดลอกรหัสมีดังนี้:
กราฟฟังก์ชัน (v) {
this.vertices = v; // จุดยอดถึงจุดสูง
this.edges = 0;
this.adj = [];
สำหรับ (var i = 0; i <this.vertices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
-
this.addedge = เพิ่ม;
this.toString = toString;
-
คลาสนี้บันทึกจำนวนกราฟที่แสดงและใช้ความยาวและจำนวนจุดยอดของกราฟเพื่อบันทึกจำนวนจุดยอด
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นเพิ่ม () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
-
ที่นี่เราใช้ A for loop เพื่อเพิ่ม subarray สำหรับแต่ละองค์ประกอบในอาร์เรย์เพื่อจัดเก็บจุดยอดที่อยู่ติดกันทั้งหมดและเริ่มต้นองค์ประกอบทั้งหมดลงในสตริงที่ว่างเปล่า
การสำรวจภาพ
ลำดับความสำคัญเชิงลึก
DEPTHFIRSTSEARCH หรือที่รู้จักกันในชื่อ DEPTHFIRSTSEARCH เรียกว่า DFS สั้น ๆ
ตัวอย่างเช่นมองหากุญแจในห้องไม่ว่าคุณจะเริ่มห้องใดคุณสามารถค้นหามุมห้อง, โต๊ะข้างเตียง, โต๊ะข้างเตียง, ใต้เตียง, ตู้เสื้อผ้า, ตู้ทีวี ฯลฯ ทีละคนเพื่อไม่ให้พลาดจุดบอด หลังจากค้นหาลิ้นชักและตู้เก็บของทั้งหมดแล้วค้นหาห้องถัดไป
การค้นหาลำดับความสำคัญเชิงลึก:
การค้นหาเชิงลึกครั้งแรกหมายถึงการเข้าถึงจุดสุดยอดที่ยังไม่ได้เข้าชมทำเครื่องหมายตามที่เข้าถึงได้จากนั้นเข้าถึงจุดยอดอื่น ๆ ที่ยังไม่ได้เข้าเยี่ยมชมในตาราง adjacency ของจุดยอดเริ่มต้น
เพิ่มอาร์เรย์ลงในคลาสกราฟ:
การคัดลอกรหัสมีดังนี้:
this.marked = []; // บันทึกจุดยอดที่เข้าชม
สำหรับ (var i = 0; i <this.vertices; ++ i) {
this.marked [i] = false; // เริ่มต้นเป็นเท็จ
-
ฟังก์ชั่นการค้นหาเชิงลึกครั้งแรก:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น dfs (v) {
สิ่งนี้ทำเครื่องหมาย [v] = true;
// ถ้าคำสั่งไม่จำเป็นที่นี่
if (this.adj [v]! = ไม่ได้กำหนด) {
พิมพ์ ("Visited Vertex:" + V);
สำหรับแต่ละ (var w ใน this.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
-
-
-
-
การค้นหาครั้งแรกที่กว้าง
Broadness First Search (BFS) เป็นวิธีการค้นหาคนตาบอดโดยมีวัตถุประสงค์เพื่อขยายอย่างเป็นระบบและตรวจสอบโหนดทั้งหมดในกราฟเพื่อค้นหาผลลัพธ์ กล่าวอีกนัยหนึ่งมันไม่ได้คำนึงถึงตำแหน่งที่เป็นไปได้ของผลลัพธ์และค้นหาภาพทั้งหมดอย่างละเอียดจนกว่าจะพบผลลัพธ์
การค้นหาแบบกว้างก่อนเริ่มต้นด้วยจุดสุดยอดครั้งแรกและพยายามเข้าถึงจุดสุดยอดใกล้เคียงที่สุดเท่าที่จะทำได้ดังแสดงในรูปต่อไปนี้:
หลักการทำงานของมันคือ:
1. ก่อนอื่นให้ค้นหาจุดยอดที่ไม่ได้รับการรับรองที่อยู่ติดกับจุดสุดยอดปัจจุบันและเพิ่มลงในรายการจุดยอดที่เข้าชมและคิว;
2. จากนั้นนำจุดสุดยอดถัดไปออกจากกราฟและเพิ่มลงในรายการ Vertice ที่เข้าชม
3. ในที่สุดก็เพิ่มจุดยอดที่ไม่ได้เข้าชมทั้งหมดที่อยู่ติดกับ V ไปยังคิว
ต่อไปนี้เป็นคำจำกัดความของฟังก์ชั่นการค้นหาที่กว้างก่อน:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น bfs (s) {
var queue = [];
this.marked = true;
queue.push (s); // เพิ่มไปยังส่วนท้ายของคิว
ในขณะที่ (queue.length> 0) {
var v = queue.shift (); // ลบออกจากหัวหน้าทีม
if (v == ไม่ได้กำหนด) {
พิมพ์ ("Visited Vertex:" + V);
-
สำหรับแต่ละ (var w ใน this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
สิ่งนี้ทำเครื่องหมาย [w] = true;
queue.push (w);
-
-
-
-
เส้นทางที่สั้นที่สุด
เมื่อทำการค้นหาแบบกว้างก่อนเส้นทางที่สั้นที่สุดจากจุดสุดยอดหนึ่งไปยังจุดสุดยอดที่เชื่อมต่ออื่นจะพบได้โดยอัตโนมัติ
กำหนดเส้นทาง
ในการค้นหาเส้นทางที่สั้นที่สุดเราจำเป็นต้องปรับเปลี่ยนอัลกอริทึมการค้นหาที่กว้างก่อนเพื่อบันทึกเส้นทางจากจุดสุดยอดหนึ่งไปยังอีกจุดหนึ่ง เราต้องการอาร์เรย์เพื่อบันทึกขอบทั้งหมดของจุดสุดยอดถัดไปจากจุดสุดยอดหนึ่ง เราตั้งชื่ออาร์เรย์นี้ edgeto
การคัดลอกรหัสมีดังนี้:
this.edgeto = []; // เพิ่มบรรทัดนี้ในคลาสกราฟ
// ฟังก์ชัน BFS
ฟังก์ชั่น bfs (s) {
var queue = [];
this.marked = true;
queue.push (s); // เพิ่มไปยังส่วนท้ายของคิว
ในขณะที่ (queue.length> 0) {
var v = queue.shift (); // ลบออกจากหัวหน้าทีม
if (v == ไม่ได้กำหนด) {
พิมพ์ ("Visited Vertex:" + V);
-
สำหรับแต่ละ (var w ใน this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
สิ่งนี้ทำเครื่องหมาย [w] = true;
queue.push (w);
-
-
-
-
อัลกอริทึมการเรียงลำดับทอพอโลยี
การเรียงลำดับทอพอโลยีเรียงลำดับจุดยอดทั้งหมดของกราฟที่กำกับเพื่อให้ขอบกำกับชี้จากจุดยอดด้านหน้าไปยังจุดสุดยอดด้านหลัง
อัลกอริทึมการเรียงลำดับทอพอโลยีนั้นคล้ายกับ BFS ความแตกต่างคืออัลกอริทึมการเรียงลำดับโทโพโลยีไม่ได้ส่งออกจุดยอดที่เข้าถึงได้ทันที แต่แทนที่จะเข้าถึงจุดยอดที่อยู่ติดกันทั้งหมดในตารางจุดสุดยอดปัจจุบันที่อยู่ติดกัน จนกว่ารายการนี้จะหมดจุดสุดยอดปัจจุบันจะไม่ถูกผลักเข้าไปในสแต็ก
อัลกอริทึมการเรียงลำดับทอพอโลยีแบ่งออกเป็นสองฟังก์ชั่น ฟังก์ชั่นแรกคือ TopSort () ซึ่งใช้ในการตั้งค่ากระบวนการเรียงลำดับและเรียกใช้ฟังก์ชั่น Helper Function TopSorthelper () จากนั้นแสดงรายการจุดสุดยอดที่เรียงลำดับ
งานหลักของอัลกอริทึมการเรียงลำดับโทโพโลยีนั้นทำในฟังก์ชั่นแบบเรียกซ้ำ topsorthelper () ซึ่งทำเครื่องหมายจุดสุดยอดปัจจุบันตามที่เข้าถึงได้จากนั้นจึงเข้าถึงแต่ละจุดสุดยอดในตาราง adjacency จุดยอดปัจจุบันทำเครื่องหมายจุดยอดเหล่านี้ ในที่สุดกดจุดยอดปัจจุบันลงในสแต็ก
การคัดลอกรหัสมีดังนี้:
// topsort () ฟังก์ชั่น
ฟังก์ชั่น topsort () {
var stack = [];
var visited = [];
สำหรับ (var i = 0; i <this.vertices; i ++) {
เยี่ยมชม [i] = false;
-
สำหรับ (var i = 0; i <this.vertices; i ++) {
ถ้า (เยี่ยมชม [i] == false) {
this.topsorthelper (i, เยี่ยมชม, สแต็ค);
-
-
สำหรับ (var i = 0; i <stack.length; i ++) {
ถ้า (stack [i]! = undefined && stack [i]! = false) {
พิมพ์ (this.vertexlist [stack [i]]);
-
-
-
// topsorthelper () ฟังก์ชั่น
ฟังก์ชั่น TopSorthelper (V, เยี่ยมชม, สแต็ค) {
เยี่ยมชม [v] = true;
สำหรับแต่ละ (var w ใน this.adj [v]) {
ถ้า (! เยี่ยมชม [w]) {
this.topsorthelper (เยี่ยมชม [w], เยี่ยมชม, สแต็ค);
-
-
stack.push (v);
-