Depth-First Search (DFS) là một thuật toán duyệt hoặc tìm kiếm trên cây hoặc đồ thị. Bắt đầu từ một đỉnh (node) ban đầu, DFS đi sâu vào các đỉnh con trước khi lùi lại và đi theo các nhánh khác. Trong C#, chúng ta có thể triển khai DFS sử dụng ngăn xếp (stack) để tránh đệ quy sâu gây tràn ngăn xếp. Dưới đây là cách triển khai DFS sử dụng cả phương pháp đệ quy và phương pháp ngăn xếp.
Triển khai DFS đệ quy
using System;
using System.Collections.Generic;
class Graph
{
private int vertices;
private List<int>[] adjacencyList;
// Khởi tạo đồ thị
public Graph(int v)
{
vertices = v;
adjacencyList = new List<int>[v];
for (int i = 0; i < v; ++i)
adjacencyList[i] = new List<int>();
}
// Thêm cạnh vào đồ thị
public void AddEdge(int v, int w)
{
adjacencyList[v].Add(w); // Thêm w vào danh sách kề của v
}
// DFS sử dụng đệ quy
private void DFSUtil(int v, bool[] visited)
{
// Đánh dấu đỉnh hiện tại là đã thăm
visited[v] = true;
Console.Write(v + " ");
// Duyệt qua tất cả các đỉnh kề với đỉnh này
foreach (int neighbor in adjacencyList[v])
{
if (!visited[neighbor])
DFSUtil(neighbor, visited);
}
}
// Hàm để khởi động DFS
public void DFS(int v)
{
// Đánh dấu tất cả các đỉnh là chưa thăm
bool[] visited = new bool[vertices];
// Gọi hàm DFSUtil cho đỉnh bắt đầu
DFSUtil(v, visited);
}
static void Main(string[] args)
{
Graph g = new Graph(4);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(2, 0);
g.AddEdge(2, 3);
g.AddEdge(3, 3);
Console.WriteLine("Duyệt đồ thị sử dụng DFS (đệ quy) bắt đầu từ đỉnh 2:");
g.DFS(2);
}
}
Triển khai DFS sử dụng ngăn xếp
using System;
using System.Collections.Generic;
class Graph
{
private int vertices;
private List<int>[] adjacencyList;
// Khởi tạo đồ thị
public Graph(int v)
{
vertices = v;
adjacencyList = new List<int>[v];
for (int i = 0; i < v; ++i)
adjacencyList[i] = new List<int>();
}
// Thêm cạnh vào đồ thị
public void AddEdge(int v, int w)
{
adjacencyList[v].Add(w); // Thêm w vào danh sách kề của v
}
// DFS sử dụng ngăn xếp
public void DFSIterative(int start)
{
// Đánh dấu tất cả các đỉnh là chưa thăm
bool[] visited = new bool[vertices];
Stack<int> stack = new Stack<int>();
// Thêm đỉnh bắt đầu vào ngăn xếp
stack.Push(start);
while (stack.Count != 0)
{
// Lấy đỉnh trên cùng của ngăn xếp
int v = stack.Pop();
if (!visited[v])
{
// Đánh dấu đỉnh này là đã thăm
visited[v] = true;
Console.Write(v + " ");
}
// Thêm tất cả các đỉnh kề với đỉnh này vào ngăn xếp
foreach (int neighbor in adjacencyList[v])
{
if (!visited[neighbor])
stack.Push(neighbor);
}
}
}
static void Main(string[] args)
{
Graph g = new Graph(4);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(2, 0);
g.AddEdge(2, 3);
g.AddEdge(3, 3);
Console.WriteLine("Duyệt đồ thị sử dụng DFS (ngăn xếp) bắt đầu từ đỉnh 2:");
g.DFSIterative(2);
}
}
Giải thích chi tiết:
-
Graph Class:
- vertices: Số lượng đỉnh trong đồ thị.
- adjacencyList: Mảng các danh sách kề, mỗi phần tử trong mảng là một danh sách các đỉnh kề với đỉnh tương ứng.
-
AddEdge Method:
- Thêm một cạnh vào đồ thị. Đối với đồ thị có hướng, chỉ cần thêm đỉnh đích vào danh sách kề của đỉnh nguồn.
-
DFSUtil Method (Đệ quy):
- Đây là hàm đệ quy thực hiện DFS. Nó đánh dấu đỉnh hiện tại là đã thăm và sau đó gọi đệ quy trên tất cả các đỉnh kề chưa được thăm.
-
DFS Method (Đệ quy):
- Khởi động DFS bằng cách tạo mảng đánh dấu tất cả các đỉnh là chưa thăm và gọi hàm đệ quy
DFSUtil.
- Khởi động DFS bằng cách tạo mảng đánh dấu tất cả các đỉnh là chưa thăm và gọi hàm đệ quy
-
DFSIterative Method (Ngăn xếp):
- Thực hiện DFS sử dụng ngăn xếp. Bắt đầu từ đỉnh ban đầu, thêm đỉnh vào ngăn xếp, sau đó lặp lại quá trình lấy đỉnh trên cùng của ngăn xếp, đánh dấu đỉnh đó là đã thăm, và thêm tất cả các đỉnh kề chưa thăm vào ngăn xếp.
-
Main Method:
- Tạo đồ thị, thêm các cạnh vào đồ thị, và gọi phương thức DFS để duyệt đồ thị bắt đầu từ một đỉnh cụ thể.
Cả hai phương pháp đều duyệt đồ thị theo chiều sâu, nhưng phương pháp sử dụng ngăn xếp tránh được vấn đề tràn ngăn xếp khi làm việc với đồ thị lớn hoặc có cấu trúc phức tạp.
Comments