Thuật toán về tìm kiếm theo chiều sâu DFS bằng ngôn ngữ C/C++

Thuật toán về tìm kiếm theo chiều sâu DFS bằng ngôn ngữ C/C++

Để 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 đồ thị - Đường đi - Chu trình - Đồ thị liên thông

Lý thuyết thuật toán tìm kiếm theo chiều rộng bạn có thể xem ở đây.

>> Lý thuyết thuật toán tìm kiếm theo chiều rộng BFS bằng C/C++ và Java

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

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

Kết quả duyệt: 1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12

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 Ѳ

DFS.IN

13
0    1    1    0    0    0    0    0    0    0    1    0    0
1    0    0    1    0    1    0    0    0    0    0    0    0
1    0    0    1    0    0    0    0    0    0    0    0    0
0    1    1    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    1    1    0    0    0
0    1    0    1    0    0    1    1    0    0    0    0    0
0    0    0    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    1    0    0    0    1    0    0    0
0    0    0    0    1    0    0    0    0    0    0    0    1
0    0    0    0    1    0    0    1    0    0    0    0    0
1    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    1    0    1
0    0    0    0    0    0    0    0    1    0    1    1    0

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();

 }

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Drupal Development: Hướng dẫn tạo CTools Panels Plugin trong Drupal 7

Drupal Development: Hướng dẫn tạo CTools Panels Plugin trong Drupal 7

The Drupal Panels module is a powerful module for designing complex pages on your web site. In combination with CTools, Views, Page Manager, and Panelizer,

CMS WordPress

Thủ thuật tối ưu hóa WordPress – nâng cao

Liệu blog của bạn đã đạt tốc độ cao nhất chưa? Tốc độ load trang có nhanh hay không? Tốc độ khi truy cập là một trong những nhân tố chính tạo sự thiện cảm cho khách viếng thăm. Do vậy Misao nghĩ bạn nên dành thời gian để tu bổ/ tối ưu hóa trang web của mình. Trong bài viết này, tôi sẽ liệt kê một vài thủ thuật khác nhau giúp bạn tăng tốc cho blog WordPress của mình.

Ứng dụng nhắn tin miễn phí WhatsApp lập kỉ lục 27 tỉ tin nhắn trong 24 giờ

Ứng dụng nhắn tin miễn phí WhatsApp lập kỉ lục 27 tỉ tin nhắn trong 24 giờ

Ứng dụng nhắn tin miễn phí WhatsApp vừa xác lập kỉ lục mới khi xử lí 10 tỉ tin nhắn trong nội bộ người dùng và 17 tỉ tin nhắn đến từ bên ngoài, trong vong 24 giờ. Thông tin này được hãng thông báo trên Twitter của mình.

Tomdesgin.vn

 

Drupal Services