Bfs trong python

+Breadth First Search là một thuật toán duyệt hoặc tìm kiếm một phần tử trên một cấu trúc dữ liệu dạng cây hoặc một đồ thị

+ Nó khác với DFS đó là nó sẽ được ưu tiên theo chiều ngang, nghĩa là duyệt từ trái qua phải hết rồi mới duyệt xuống dưới cho từng phần tử

Như vậy thứ tự đi trong hình minh họa ở trên như sau

• Bắt đầu từ 1 => 2 => 7 => 8 => hết nút ngang
• Continue 2 => 3 => 6 hết node ngang
• Start 7 => không có nút ngang
• Continue 8=>9 => 12 hết nút ngang
• Start 3 => 4 => 5 => hết node ngang
• Tiếp tục 6 => không có nút ngang
• Start 9 => 10=> 11 hết node ngang
• Tiếp tục 12 => không có nút ngang
• Start 4 => hết nút
• Tiếp tục 5 => hết nút
• Start 10 => hết nút
• Tiếp tục 11 => hết nút

– Queue data queue used to archive node

– Là cấu trúc dữ liệu dạng đồ thị, hoặc dạng cây

– Độ phức tạp thời gian là. Ô(. V. +. E. )  V là số duyệt qua và E là số duyệt qua

– Độ phức tạp không gian là O(. V. ). Số đỉnh là số phần tử cần lưu trữ vào bộ nhớ

Thực hiện được hai bước cho bài toán thực thi thuật toán Breath First Search

+ Xây dựng cấu trúc dữ liệu dạng cây cấu trúc, với phần tử cha là phần tử đầu tiên của cây

+ Viết hàm tìm kiếm, duyệt các phần tử bắt đầu từ phần tử cha ở trên

a. Áp dụng với bài toán đơn giản cho hình minh họa ở trên

Mục đích quan TA CẦN CÓ ĐỐI LẬP THỊ. 1 – 2 7 8 – 3 6 9 12 – 4 5 10 11

+ Nút là một đối tượng chung, và mỗi nút có thể trỏ đến nhiều nút khác là kiểu dữ liệu như nó

=> xây dựng nút là một lớp, và trong đó lưu lại một danh sách các đối tượng chính của nó

danh sách lưu trữ các nút chính là một cấu trúc dữ liệu kiểu Hàng đợi

build an class as after

Định nghĩa hàm AddChild để thêm nút và hàm tìm nút duyệt tìm kiếm, hàm trong dữ liệu

Build function tạo cây nhị phân lưu trữ dữ liệu

Được. Như vậy là chúng ta đã có thể demo thuật toán DFS bằng mã c++ với bài toán cơ bản nhất

b. Áp dụng vào bài toán hướng đối tượng. Giống như DFS

Vẫn là hình minh họa như DFS, nhưng các bạn sẽ thấy,

cách duyệt của BFS sẽ là duyệt tất cả các phòng ban, sau đó mới duyệt các bộ phận của từng phòng ban

Khác với DFS là duyệt từng phòng ban và duyệt hết các bộ phận phòng ban rồi mới sang phòng ban kết nối

Từ video thực hiện bài toán nâng cao của DFS mà tôi đã thực hiện trên video, các bạn thử áp dụng với BFS

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*/

for (u=1; u≤n; u++) 
 chuaxet[u] = TRUE; 
for (u∈V ) 
 if (chuaxet[u] ) 
  BFS(u);

STT

Các đỉnh đã duyệt

Các đỉnh trong hàng đợi

Các đỉnh còn lại

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

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

Chia sẻ cái này

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*/

for (u=1; u≤n; u++) 
 chuaxet[u] = TRUE; 
for (u∈V ) 
 if (chuaxet[u] ) 
  BFS(u);

STT

Các đỉnh đã duyệt

Các đỉnh trong hàng đợi

Các đỉnh còn lại

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

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