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

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

Để 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 về thuật toán tìm kiếm theo chiều sâu bạn có thể xem ở đây.

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

Khác với thuật toán tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều rộng thay thế việc sử dụng stack bằng hàng đợi queue. Trong thủ tục này, đỉnh được nạp vào hàng đợi đầu tiên là v, các đỉnh kề với v ( v1, v2,..., vk) được nạp vào queue kế tiếp. Quá trình duyệt tiếp theo được bắt đầu từ các đỉnh còn có mặt trong hàng đợi.

Để ghi nhận trạng thái duyệt các đỉnh của đồ thị, ta cũng vẫn sử dụng mảng chuaxet[] gồm n phần tử thiết lập giá trị ban đầu là TRUE. Nếu đỉnh i của đồ thị đã được duyệt, giá trị chuaxet[i] sẽ nhận giá trị FALSE. Thuật toán dừng khi hàng đợi rỗng.

Thủ tục BFS dưới đây thể hiện quá trình thực hiện của thuật toán:

void BFS(int u){

 queue = φ;

 u <= queue; /*nạp u vào hàng đợi*/

 chuaxet[u] = false;/* đổi trạng thái của u*/

 while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/

  queue<=p; /*lấy p ra từ khỏi hàng đợi*/

  Thăm_Đỉnh(p); /* duyệt xong đỉnh p*/

  for (v ∈ke(p) ) {/* đưa các đỉnh v kề với p nhưng chưa được xét vào hàng đợi*/

   if (chuaxet[v] ) {

    v<= queue; /*đưa v vào hàng đợi*/

    chuaxet[v] = false;/* đổi trạng thái của v*/

   }

  }

 } /* end while*/

}/* end BFS*/

Thủ tục BFS sẽ thăm tất cả các đỉnh cùng thành phần liên thông với u. Để thăm tất cả các đỉnh của đồ thị, chúng ta chỉ cần thực hiện đoạn chương trình dưới đây:

for (u=1; u≤n; u++)

 chuaxet[u] = TRUE;

for (u∈V )

 if (chuaxet[u] )

  BFS(u);

Đồ thị - Tìm kiếm theo chiều rộng BFS

Đồ thị - Tìm kiếm theo chiều rộng BFS

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

BFS.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ạy tay

STT
Các đỉnh đã duyệt
Các đỉnh trong hàng đợi
Các đỉnh còn lại
1 Ѳ Ѳ 1,2,3,4,5,6,7,8,9,10,11,12,13
2 1 2,3,11 4,5,6,7,8,9,10,12,13
3 1,2 3,11,4,6 5,7,8,9,10,12,13
4 1,2,3 11,4,6 5,7,8,9,10,12,13
5 1,2,3,11 4,6,12,13 5,7,8,9,10
6 1,2,3,11,4 6,12,13 5,7,8,9,10
7 1,2,3,11,4,6 12,13,7,8 5,9,10
8 1,2,3,11,4,6,12 13,7,8 5,9,10
9 1,2,3,11,4,6,12,13 7,8,9 5,10
10 1,2,3,11,4,6,12,13,7 8,9 5,10
11 1,2,3,11,4,6,12,13,7,8 9,10 5
12 1,2,3,11,4,6,12,13,7,8,9 10,5 Ѳ
13 1,2,3,11,4,6,12,13,7,8,9,10 5 Ѳ
14 1,2,3,11,4,6,12,13,7,8,9,10,5 Ѳ Ѳ

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], QUEUE[MAX]; 

void Init(){ 

 freopen("BFS.IN","r",stdin);

 cin>>n;

 cout<<"So dinh cua do thi 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]; 

  } 

 } 

 for(int i=1; i<=n;i++){

  chuaxet[i]=TRUE; 

 }

} 

/* Breadth First Search */

void BFS(int i){ 

 int u,dauQ, cuoiQ;

 dauQ=1; cuoiQ=1;QUEUE[cuoiQ]=i;chuaxet[i]=FALSE; 

 /* thiết lập hàng đợi với đỉnh đầu là i*/

 while(dauQ<=cuoiQ){ 

  u=QUEUE[dauQ];// lấy đỉnh u ra khỏi queue.

  cout<<"duyet dinh: "<<u<<endl;

  dauQ=dauQ+1; /* duyệt đỉnh đầu hàng đợi*/

  for(int j=1; j<=n;j++){ 

   if(G[u][j]==1 && chuaxet[j] ){ 

    cuoiQ=cuoiQ+1; 

    QUEUE[cuoiQ]=j; 

    chuaxet[j]=FALSE; 

   } 

  } 

 } 

} 

void main(void){ 

 Init(); 

 for(int i=1; i<=n; i++) 

  if (chuaxet[i])

   BFS(i); 

 _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 BFSAlgorithm {

 static final int MAX = 100;

 int G[][] = new int[MAX][MAX];/* ma trận kề*/

 boolean chuaxet[] = new boolean[MAX];/*mảng đánh dấu đỉnh đã được thăm.*/

 int QUEUE[] = new int[MAX]; /*hàng đợi*/

 int n;


 void init() {

  File file = new File(getClass().getResource("BFS.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 BFS(int v) {

  int u, dauQ, cuoiQ, j;

  dauQ = 1;

  cuoiQ = 1;

  QUEUE[cuoiQ] = v;

  chuaxet[v] = false;

  /* thiết lập hàng đợi với đỉnh đầu là i */

  while (dauQ <= cuoiQ) {

   u = QUEUE[dauQ];

   System.out.print(u + " ");

   dauQ = dauQ + 1; /* duyệt đỉnh đầu hàng đợi */

   for (j = 1; j <= n; j++) {

    if (G[u][j] == 1 && chuaxet[j]) {

     cuoiQ = cuoiQ + 1;

     QUEUE[cuoiQ] = j;

     chuaxet[j] = false;

    }

   }

  }

 }


 public BFSAlgorithm() {

  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]) {

    BFS(i);

   }

 }


 public static void main(String[] args) {

  new BFSAlgorithm();

 }

}
Bạn thấy bài viết này như thế nào?: 
Average: 9.5 (19 votes)
Ả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

 
Kì vọng nào dành cho nền tảng iOS 6 sắp tới của Apple

Kì vọng nào dành cho nền tảng iOS 6 sắp tới của Apple

Dự kiến tại sự kiện WWDC diễn ra vào tuần tới, Apple sẽ chính thức giới thiệu đến người dùng phiên bản hệ điều hành iOS 6 mới nhất...

Showing a Twitter Feed in a Drupal Block

Hiển thị Twitter Feed với một Drupal Block

In this tutorial we'll show you how to place a Twitter feed inside a block. You can then display that Twitter feed anywhere around your theme. There are many different Twitter options out there but most have a couple of limitations:

Rel tag

Thêm thuộc tính rel cho thẻ liên kết

Thuộc tính rel cho thẻ liên kết không hiểu sao không được coi trọng trong Blogger - một sản phẩm của Google. Trong khi với Wordpress thì thuộc tính này luôn được khai báo cẩn thận và có phải nhờ một phần như vậy mà Wordpress có khả năng SEO tốt hơn Blogger rất nhiều?

Công ty diệt chuột T&C

 

Diet con trung