資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C 語言編寫程式，列印圖從節點 1 開始的字典序最小的廣度優先搜尋（BFS）結果。
我們將得到一個具有 N 個頂點 M 條邊的連通圖。因此，我們必須列印從節點 1 開始的圖的字典序最小的 BFS 結果。
字典序是指從給定點開始到找到終點為止的順序。
頂點應從 1 到 N 編號
示例
Input: N = 5 M = 5 edges(1,4, arr) edges(3,4, arr) edges(5,4, arr) edges(3,2, arr) edges(1,5, arr) Output: 1 4 3 2 5
與其對圖使用簡單的佇列進行普通的 BFS 遍歷，我們可以使用優先佇列（最小堆）。每當訪問一個節點時，將它的鄰接節點新增到優先佇列中。每次我們訪問一個新節點時，它將是優先佇列中索引最小的那個。從 1 開始，每次訪問節點時列印節點。
演算法
Start Step 1 -> Declare Function void lexo(vector<int> array[], int n) Declare bool arr[n + 1] Call memset(arr, 0, sizeof arr) Use STL priority_queue<int, vector<int>, greater<int> > que Set arr[1] = true Call que.push(1) Loop While !que.empty() Declare int now = que.top() Call que.pop() Print now Loop For (auto p : array[now]) IF !arr[p] Call que.push(p) Call arr[p] = true End End End Step 2 -> declare Function void edge(int i, int j, vector<int> ar[]) Call ar[i].push_back(j) Call ar[j].push_back(i) Step 3- > In main() Declare int n = 5, m = 5 Use STL vector<int> arr[n + 1] Call edges(1,4, arr) Call edges(3,4, arr) Call lexo(arr, n) Stop
示例
#include <bits/stdc++.h>
using namespace std;
//for finding the graph
void lexo(vector<int> array[], int n){
bool arr[n + 1];
memset(arr, 0, sizeof arr);
priority_queue<int, vector<int>, greater<int> > que;
arr[1] = true;
que.push(1);
while (!que.empty()){
int now = que.top();
que.pop();
cout << now << " ";
for (auto p : array[now]){
if (!arr[p]){
que.push(p);
arr[p] = true;
}
}
}
}
//for generating edge
void edge(int i, int j, vector<int> ar[]){
ar[i].push_back(j);
ar[j].push_back(i);
}
int main(){
int n = 5, m = 5;
vector<int> arr[n + 1];
edges(1,4, arr); //for inserting the edge
edges(3,4, arr);
edges(5,4, arr);
edges(3,2 arr);
edges(1,5, arr);
lexo(arr, n);
return 0;
}輸出
如果我們執行上述程式，它將生成以下輸出
1 4 3 2 5
更新於: 2019年8月22日
473 次瀏覽
廣告