使用向量和佇列實作BFS,依照CLRS演算法在C程式中的實現
在CLRS書中,BFS演算法使用向量和佇列來描述。我們必須使用C STL來實作該演算法。首先讓我們來看一下演算法。
演算法
BFS(G, s) −
begin for each vertex u in G.V - {s}, do u.color := white u.d := infinity u.p := NIL done s.color := green s.d := 0 s.p := NIL Q := NULL insert s into Q while Q is not null, do u = delete from Q for each v in adjacent to u, do if v.color = white v.color := green v.d := u.d + 1 v.p := u insert v into Q end if done u.color = dark_green done end
Example
的中文翻譯為:範例
#include<iostream> #include<vector> #include<queue> using namespace std; vector<string> colour; vector<int> dist; vector<int> par; void addEdge(vector <int> g[], int u, int v) { //add edge to form the graph g[u].push_back(v); g[v].push_back(u); } void BFS(vector <int> g[], int s) { queue<int> q; q.push(s); //insert source dist[s] = 0; colour[s] = "gray"; while (!q.empty()) { int u = q.front(); //top element from queue, then delete it q.pop(); cout << u << " "; for (auto i = g[u].begin(); i != g[u].end(); i++) { if (colour[*i] == "white") { //white is unvisited node colour[*i] = "gray"; //gray is visited but not completed dist[*i] = dist[u] + 1; par[*i] = u; q.push(*i); } } colour[u] = "black"; //black is completed node } } void BFSAlgo(vector <int> g[], int n) { colour.assign(n, "white"); //put as unvisited dist.assign(n, 0); par.assign(n, -1); for (int i = 0; i < n; i++) if (colour[i] == "white") BFS(g, i); } int main() { int n = 7; vector <int> g[n]; addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 1, 4); addEdge(g, 2, 5); addEdge(g, 2, 6); BFSAlgo(g, n); }
輸出
0 1 2 3 4 5 6
以上是使用向量和佇列實作BFS,依照CLRS演算法在C程式中的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

Laravel是一款非常受歡迎的PHP開發框架,它提供了豐富的功能和便利的開發方式,能夠幫助開發人員快速建立穩定可靠的Web應用程式。在Laravel開發過程中,合理使用快取與佇列是十分重要的,本文將介紹一些注意事項以幫助開發人員更好地利用快取與佇列。一、合理使用快取快取的定義與作用快取是一種將經常使用的資料暫時儲存在記憶體中的技術,能夠大幅提高系統的反應速度

佇列的死信佇列和延遲佇列在PHP與MySQL中的應用場景引言隨著網路應用變得越來越複雜,處理大量訊息和任務的需求日益增長。隊列作為一種解決方案,能夠有效實現任務的非同步處理,提高系統的可擴展性和穩定性。在隊列的應用中,常見的兩個概念是死信隊列和延遲隊列。本文將介紹這兩個概念在PHP與MySQL中的應用場景,並提供具體的程式碼範例。死信隊列的應用場景死信隊列是

在CLRS書中,BFS演算法使用向量和佇列來描述。我們必須使用C++STL來實作該演算法。首先讓我們來看一下演算法。演算法BFS(G,s)−begin foreachvertexuinG.V-{s},do u.color:=white u.d:=infinity u.p:=NI

佇列在PHP與MySQL中的訊息過濾和訊息路由的實作方法隨著網路的快速發展,訊息佇列(MessageQueue)作為一種重要的通訊機制,在Web開發中扮演著至關重要的角色。訊息佇列可以用於實現解耦、削峰填谷、非同步處理等功能。本文將介紹在PHP與MySQL中如何實作訊息過濾和訊息路由,並提供具體的程式碼範例。訊息隊列訊息隊列是一種典型的"生產者-消費者"模型

介紹C++中的堆疊和佇列棧和佇列是C++中常用的資料結構,它們在程式中有著廣泛的應用。本文將對堆疊和佇列的概念、使用方法和應用場景進行詳細介紹。一、棧的概念棧(Stack)是一種線性資料結構,它具有"先進後出"的特性。在棧中,越先進棧的數據,越靠近棧底;越後進棧的數據,就越靠近棧頂。棧的主要操作有入棧(push)和出棧(pop)。入棧就是往棧裡添加數據,而出棧

佇列的訊息持久化和訊息去重在PHP與MySQL中的應用場景佇列是一種常見的資料結構,在軟體開發中被廣泛應用於非同步訊息處理、任務調度、日誌收集等場景。其中,訊息持久化和訊息去重是佇列的兩個重要特性,能夠保證訊息的可靠性和資料的一致性。在PHP和MySQL中,佇列的應用可以透過Redis作為訊息中間件,用MySQL來儲存和管理佇列的元數據,具體範例如下所示。首先

一個棧(Stack)是Vector類別的子類,它代表了一個後進先出(LIFO)的物件堆疊。最後一個加入到堆疊頂部的元素(In)可以是從堆疊中首先移除的元素(Out)。佇列(Queue)類別擴展了Collection接口,並支援使用先進先出(FIFO)的插入和刪除操作。我們也可以在下面的程式中使用佇列來實作堆疊。範例importjava.util.*;publicclassStackFromQueueTest{ Queuequeue=newLinkedList();

隊列在PHP與MySQL中的消息堆積和擁塞控制的處理方法隨著互聯網的迅速發展,各種網站和應用程式的用戶數量不斷增加,對伺服器的負載能力提出了更高的要求。在這種背景下,訊息佇列成為了一種常用的解決方案,用來解決高並發存取下的訊息堆積和擁塞問題。本文將介紹隊列在PHP與MySQL中的訊息堆積和擁塞控制的處理方法,並給出具體的程式碼範例。在PHP中,我們可以使用Re
