การสำรวจเชิงลึก (Depth First Search) ในภาษา Delphi Object Pascal

 

การสำรวจเชิงลึก (Depth First Search หรือ DFS) เป็นเทคนิคการค้นหาที่ใช้ในการค้นหาจุดที่เราต้องการในโครงสร้างข้อมูลที่เป็นกราฟหรือต้นไม้ (Tree) ซึ่งเป็นหนึ่งในหาอัลกอริธึมพื้นฐานที่มีความสำคัญและได้รับการประยุกต์ใช้ในหลาย ๆ ด้าน เช่น การค้นหาข้อมูลในฐานข้อมูล การวิเคราะห์เครือข่าย หรือแม้กระทั่งการสร้างเกมที่มีการสำรวจโลก

 

DFS คืออะไร?

DFS คืออัลกอริธึมทางกราฟชนิดหนึ่งที่ทำการสำรวจจุดเชื่อมโยงในกราฟอย่างต่อเนื่อง โดยเริ่มจากจุดเริ่มต้นแล้วเข้าไปสำรวจจุดลูก (หรือเพื่อนบ้าน) ของจุดที่อยู่ปัจจุบัน โดยจะทำการสำรวจในเชิงลึก (Deep) จนกว่าจะไม่สามารถต่อไปได้ แต่ละจุดที่เราเข้ามาสำรวจจะถูกทำเครื่องหมายเพื่อป้องกันการสำรวจซ้ำอีกครั้ง

การประยุกต์ใช้อัลกอริธึม DFS

DFS เหมาะสำหรับการใช้ในปัญหาที่ต้องการสำรวจอาจเป็น:

1. การค้นหาทางออกในเขาวงกต: DFS สามารถใช้ในการค้นหาเส้นทางที่เชื่อมต่อระหว่างจุดเริ่มต้นไปยังจุดสิ้นสุดในเขาวงกต 2. การวิเคราะห์เครือข่าย: ในการวิเคราะห์โครงสร้างของเครือข่ายการสื่อสาร DFS ช่วยให้เข้าใจว่าสามารถติดต่อจุดใดจากจุดใด 3. การจัดระเบียบข้อมูลในฐานข้อมูล: DFS สามารถช่วยในการค้นหาข้อมูลเชิงโครงสร้างในฐานข้อมูลที่เป็นกราฟได้

 

ตัวอย่างโค้ด DFS ใน Delphi Object Pascal

ด้านล่างนี้คือโค้ดที่แสดงการใช้อัลกอริธึม DFS ในภาษา Delphi Object Pascal:

 program DFSExample;

uses
  SysUtils, Generics.Collections;

// สร้างคลาสสำหรับกราฟ
type
  TGraph = class
  private
    FAdjList: TDictionary<Integer, TList<Integer>>;
  public
    constructor Create;
    destructor Destroy; override;
    procedure AddEdge(v, w: Integer);
    procedure DFS(start: Integer);
  end;

// สร้างคลาสสำหรับการทำงานกับกราฟ
constructor TGraph.Create;
begin
  FAdjList := TDictionary<Integer, TList<Integer>>.Create;
end;

destructor TGraph.Destroy;
begin
  FAdjList.Free;
  inherited;
end;

// เพิ่มเส้นเชื่อมระหว่างจุดในกราฟ
procedure TGraph.AddEdge(v, w: Integer);
begin
  if not FAdjList.ContainsKey(v) then
    FAdjList.Add(v, TList<Integer>.Create);
  if not FAdjList.ContainsKey(w) then
    FAdjList.Add(w, TList<Integer>.Create);

  FAdjList[v].Add(w);
  FAdjList[w].Add(v); // สำหรับกราฟที่ไม่มีทิศทาง
end;

// ใช้อัลกอริธึม DFS ในการสำรวจกราฟ
procedure TGraph.DFS(start: Integer);
var
  Stack: TStack<Integer>;
  Visited: TDictionary<Integer, Boolean>;
  Node: Integer;
  Neighbour: Integer;
begin
  Stack := TStack<Integer>.Create;
  Visited := TDictionary<Integer, Boolean>.Create;

  try
    Stack.Push(start);
    Visited.Add(start, True);

    while Stack.Count > 0 do
    begin
      Node := Stack.Pop;
      WriteLn(Node); // แสดงผลที่ได้รับ

      for Neighbour in FAdjList[Node] do
      begin
        if not Visited.ContainsKey(Neighbour) then
        begin
          Visited.Add(Neighbour, True);
          Stack.Push(Neighbour);
        end;
      end;
    end;
  finally
    Stack.Free;
    Visited.Free;
  end;
end;

// โปรแกรมหลัก
var
  Graph: TGraph;
begin
  Graph := TGraph.Create;
  try
    Graph.AddEdge(1, 2);
    Graph.AddEdge(1, 3);
    Graph.AddEdge(2, 4);
    Graph.AddEdge(2, 5);
    Graph.AddEdge(3, 6);
    Graph.AddEdge(4, 7);

    WriteLn('DFS starting from node 1:');
    Graph.DFS(1);
  finally
    Graph.Free;
  end;
end.

อธิบายโค้ด

- คลาส TGraph: ใช้สำหรับสร้างกราฟโดยใช้โครงสร้างข้อมูลเป็น Dictionary ที่เก็บเส้นเชื่อมของกราฟไว้ในรูปแบบของ List - AddEdge: ฟังก์ชันนี้ใช้สำหรับเพิ่มเส้นเชื่อมระหว่างจุดสองจุดในกราฟ - DFS: ฟังก์ชันนี้จะทำการสำรวจโดยใช้ Stack ในการเก็บจุดที่เราจะต้องไปสำรวจ และใช้ Dictionary เพื่อตรวจสอบว่าจุดไหนถูกสำรวจแล้วหรือยัง จากนั้นจะแสดงผลลัพธ์ของการสำรวจ

 

การวิเคราะห์ Complexity ของ DFS

- Time Complexity: O(V + E) โดยที่ V คือจำนวนจุด (Vertex) และ E คือจำนวนเส้นเชื่อม (Edge) ของกราฟ เนื่องจากเราต้องสำรวจแต่ละจุดและเส้นเชื่อมทั้งหมด - Space Complexity: O(V) สำหรับ Stack และ Dictionary ที่ใช้เก็บข้อมูลการเยี่ยมชม

 

ข้อดีและข้อเสียของ DFS

ข้อดี

1. การใช้หน่วยความจำน้อย: หากโหนดที่สำรวจมีความลึกมาก DFS จะใช้หน่วยความจำเพียงเท่าไหร่ที่ต้องสำรวจ เพื่อให้ถึงจุดปลาย 2. ค้นหาทุกจุดได้ทั้งกราฟ: DFS สามารถค้นหาและสำรวจทุกจุดได้เมื่อเริ่มต้นที่จุดใดก็ได้

ข้อเสีย

1. เสี่ยงที่จะไม่พบที่สุด: ในกรณีที่มีเส้นทางที่หนาแน่นหรือไม่เป็นระเบียบ DFS อาจจะไปถึงจุดที่ไม่ใช่เส้นทางที่สั้นที่สุดหรือดีที่สุด 2. ปัญหาจาก Recursion: หากทำการสำรวจกราฟที่มีลักษณะวงกลม (Cyclic Graph) อาจจะทำให้เกิด Stack Overflow ได้

 

สรุป

การสำรวจเชิงลึก (DFS) เป็นเครื่องมือที่ทรงพลังในการสำรวจโครงสร้างข้อมูลที่เป็นกราฟและต้นไม้ ไม่ว่าจะเป็นตรวจสอบเส้นทางในเขาวงกตหรือการสำรวจความสัมพันธ์ในข้อมูลต่าง ๆ คุณสามารถนำอัลกอริธึมนี้ไปใช้ในการพัฒนาแอปพลิเคชันหรือระบบที่ซับซ้อนได้

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและต้องการพัฒนาทักษะด้านนี้ ในการเรียนหรือค้นคว้าหลักสูตรที่ EPT (Expert-Programming-Tutor) คุณจะได้พบกับวิธีการเรียนการสอนที่ทันสมัย และเครื่องมือที่ช่วยในการเข้าใจการโปรแกรมได้อย่างมีประสิทธิภาพมากยิ่งขึ้น ไม่ว่าจะเป็นทฤษฎีหรือการปฏิบัติ คุณจะได้เรียนรู้ทุกสิ่งที่คุณต้องการเพื่อเป็นผู้เชี่ยวชาญด้านการเขียนโปรแกรมอย่างแท้จริง!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง