[Thuật toán] Tìm kiếm theo chiều sâu DFS.

Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây.
Lý thuyết thuật toán tìm kiếm theo chiều rộng bạn có thể xem ở đây.
Tư tưởng cơ bản của thuật toán tìm kiếm theo chiều sâu là bắt đầu tại một đỉnh v0 nào đó, chọn một đỉnh u bất kỳ kề với v0 và lấy nó làm đỉnh duyệt tiếp theo. Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh v0 với đỉnh bắt đầu là u.
Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ i đã được duyệt, phần tử tương ứng trong mảng chuaxet[] có giá trị FALSE. Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong mảng có giá trị TRUE. Thuật toán có thể được mô tả bằng thủ tục đệ qui DFS () trong đó: chuaxet - là mảng các giá trị logic được thiết lập giá trị TRUE.

void DFS( int v){ 
 Thăm_Đỉnh(v);
 chuaxet[v]:= FALSE; 
 for ( u ∈ke(v) ) { 
  if (chuaxet[u] ) DFS(u); 
 } 
}

Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với mỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:

for (i=1; i≤n ; i++) 
 chuaxet[i]:= TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/
for (i=1; i≤n ; i++) 
 if (chuaxet[i] ) 
  DFS( i); 

Đồ thị - Tìm kiếm theo chiều sâu DFS

STT	Đỉnh bắt đầu duyệt	Các đỉnh đã duyệt	Các đỉnh chưa duyệt
1	DFS(1)	1	2,3,4,5,6,7,8,9,10,11,12,13
2	DFS(2)	1,2	3,4,5,6,7,8,9,10,11,12,13
3	DFS(4)	1,2,4	3,5,6,7,8,9,10,11,12,13
4	DFS(3)	1,2,4,3	5,6,7,8,9,10,11,12,13
5	DFS(6)	1,2,4,3,6	5,7,8,9,10,11,12,13
6	DFS(7)	1,2,4,3,6,7	5,8,9,10,11,12,13
7	DFS(8)	1,2,4,3,6,7,8	5,9,10,11,12,13
8	DFS(10)	1,2,4,3,6,7,8,10	5,9,11,12,13
9	DFS(10)	1,2,4,3,6,7,8,10,5	9,11,12,13
10	DFS(9)	1,2,4,3,6,7,8,10,5,9	11,12,13
11	DFS(13)	1,2,4,3,6,7,8,10,5,9,13	11,12
12	DFS(11)	1,2,4,3,6,7,8,10,5,9,13,11	12
13	DFS(12)	1,2,4,3,6,7,8,10,5,9,13,11,12	Ѳ

Kết quả duyệt: 1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12
Ma trận liền kề được tải về tại đây.
Chương trình cài đặt bằng C/C++.

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX  100 
#define TRUE 1 
#define FALSE 0 
int G[MAX][MAX], n, chuaxet[MAX]; 
void Init(){ 
 freopen("DFS.IN", "r", stdin); 
 cin>>n; 
 cout<<"So dinh cua ma tran n = "<<n<<endl;
 //nhap ma tran lien ke.
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>G[i][j]; 
  } 
 } 
} 
/* Depth First Search */
void DFS(int G[][MAX], int n, int v, int chuaxet[]){ 
 cout<<"Duyet dinh : "<<v<<endl;
 int u; 
 chuaxet[v]=FALSE; 
 for(u=1; u<=n; u++){ 
  if(G[v][u]==1 && chuaxet[u]) 
   DFS(G,n, u, chuaxet); 
 } 
} 
void main(void){ 
 Init(); 
 for(int i=1; i<=n; i++) 
  chuaxet[i]=TRUE; 
 for(int i=1; i<=n;i++) 
  if(chuaxet[i]) 
   DFS( G,n, i, chuaxet); 
 _getch(); 
}

Chương trình cài đặt bằng Java.

package simplecodecjava.blogspot.com;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class DFSAlgorithm {
 static final int MAX = 100;
 int G[][] = new int[MAX][MAX];// matran kề.
 int n = 0; // số dỉnh của đồ thị
 boolean chuaxet[] = new boolean[MAX];// mảng đánh dấu đỉnh đã được thăm.
 void Init() {
  File file = new File(getClass().getResource("DFS.IN").getPath());
  BufferedReader reader = null;
  try {
   reader = new BufferedReader(new FileReader(file));
   n = Integer.parseInt(reader.readLine());
   for (int i = 1; i <= n; i++) {
    String[] aLineOfMatrix = reader.readLine().split("\\s+");
    for (int j = 1; j <= n; j++) {
     G[i][j] = Integer.parseInt(aLineOfMatrix[j -1]);// index của J bắt đầu từ 0.
    }
   }
  }catch(FileNotFoundException e){
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  } 
  finally {
   if (reader != null)
    try {
     reader.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
  }
 }

 void DFS(int v) {
  int u;
  System.out.print(v + " ");
  chuaxet[v] = false;
  for (u = 1; u <= n; u++) {
   if (G[v][u] == 1 && chuaxet[u])
    DFS(u);
  }
 }

 public DFSAlgorithm() {
  Init();
  for (int i = 1; i <= n; i++){
   chuaxet[i] = true;
  }
  System.out.print("\n");
  for (int i = 1; i <= n; i++)
   if (chuaxet[i]){
    DFS(i);
   }
 }

 public static void main(String[] args) {
  System.out.println("DFS");
  new DFSAlgorithm();
 }
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.