資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究圖的廣度優先搜尋或 BFS
廣度優先搜尋 (BFS) 遍歷是一種演算法，用於訪問給定圖的所有節點。在這個遍歷演算法中，選擇一個節點，然後逐個訪問所有相鄰節點。完成所有鄰接頂點後，它會進一步檢查另一個頂點並再次檢查其鄰接頂點。
要實現此演算法，我們需要使用佇列資料結構。所有相鄰頂點都新增到佇列中，當完成所有相鄰頂點時，從佇列中刪除一個專案並再次開始遍歷該頂點。
在圖中，有時我們可能會得到一些迴圈，因此我們將使用一個數組來標記何時訪問了一個節點或尚未訪問。
輸入 - 圖的鄰接矩陣。
A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0
輸出 - BFS 遍歷：B A D E C F
演算法
bfs(vertices, start)
輸入 − 頂點列表和起始頂點。
輸出 − 如果圖是連通的，則遍歷所有節點。
Begin define an empty queue que at first mark all nodes status as unvisited add the start vertex into the que while que is not empty, do delete item from que and set to u display the vertex u for all vertices 1 adjacent with u, do if vertices[i] is unvisited, then mark vertices[i] as temporarily visited add v into the queue mark done mark u as completely visited done End
示例
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
typedef struct node{
int val;
int state; //status
}node;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void bfs(node *vert, node s){
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++){
vert[i].state = 0; //not visited
}
vert[s.val].state = 1;//visited
que.push(s); //insert starting node
while(!que.empty()){
u = que.front(); //delete from queue and print
que.pop();
cout << char(u.val+'A') << " ";
for(i = 0; i<NODE; i++){
if(graph[i][u.val]){
//when the node is non-visited
if(vert[i].state == 0){
vert[i].state = 1;
que.push(vert[i]);
}
}
}
u.state = 2;//completed for node u
}
}
int main(){
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++){
vertices[i].val = i;
}
s = 'B';//starting vertex B
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
}輸出
BFS Traversal: B A D E C F
更新時間: 05-Aug-2019
2 千次觀看
廣告