資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學在 C++ 中使用 STL 的 BFS 進行競賽編碼？
廣度優先搜尋 (BFS) 遍歷是一種演算法，用於訪問圖的所有節點。在這個遍歷演算法中，先選擇一個節點，然後依次訪問所有相鄰節點。完成所有相鄰頂點後，它會進一步檢查另一個頂點及其相鄰頂點。
在競技編碼中，我們必須非常快速地解決問題。我們將使用 STL (C++ 標準庫) 來實現這個演算法，我們需要使用佇列資料結構。所有相鄰頂點都新增到佇列中，當所有相鄰頂點完成後，從佇列中刪除一個專案並再次遍歷該頂點。
在圖中，有時我們可能會遇到一些迴圈，因此我們將使用一個數組來標記一個節點是否已被訪問。
Input : The Adjacency matrix of the graph. 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 Output : BFS Traversal: 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;
class node {
public:
int val;
int state; //status
};
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
更新於: 30-Jul-2019
566 次瀏覽
廣告