벡터와 큐를 이용하여 BFS를 구현하고, C 프로그램에서 CLRS 알고리즘을 구현한다.
Sep 06, 2023 pm 04:37 PM
대기줄
벡터
bfs (breadth-first search)
CLRS 책에서는 BFS 알고리즘이 벡터와 큐를 사용하여 설명됩니다. 이 알고리즘을 구현하려면 C++ STL을 사용해야 합니다. 먼저 알고리즘을 살펴보겠습니다.
algorithm
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
의 중국어 번역은 다음과 같습니다: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); }
로그인 후 복사
Output
0 1 2 3 4 5 6
로그인 후 복사
위 내용은 벡터와 큐를 이용하여 BFS를 구현하고, C 프로그램에서 CLRS 알고리즘을 구현한다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

인기 기사
Repo : 팀원을 부활시키는 방법
3 몇 주 전
By 尊渡假赌尊渡假赌尊渡假赌
스플릿 소설을이기는 데 얼마나 걸립니까?
3 몇 주 전
By DDD
R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
1 몇 주 전
By 尊渡假赌尊渡假赌尊渡假赌
헬로 키티 아일랜드 어드벤처 : 거대한 씨앗을 얻는 방법
3 몇 주 전
By 尊渡假赌尊渡假赌尊渡假赌

인기 기사
Repo : 팀원을 부활시키는 방법
3 몇 주 전
By 尊渡假赌尊渡假赌尊渡假赌
스플릿 소설을이기는 데 얼마나 걸립니까?
3 몇 주 전
By DDD
R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
1 몇 주 전
By 尊渡假赌尊渡假赌尊渡假赌
헬로 키티 아일랜드 어드벤처 : 거대한 씨앗을 얻는 방법
3 몇 주 전
By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 기사 태그

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제
Gmail 이메일의 로그인 입구는 어디에 있나요?
7291
9


자바 튜토리얼
1622
14


Cakephp 튜토리얼
1342
46


라라벨 튜토리얼
1259
25


PHP 튜토리얼
1206
29



PHP 및 MySQL의 데드 레터 큐 및 지연 큐의 애플리케이션 시나리오

PHP 및 MySQL에서 대기열 메시지 필터링 및 메시지 라우팅을 구현하는 방법

벡터와 큐를 이용하여 BFS를 구현하고, C 프로그램에서 CLRS 알고리즘을 구현한다.

PHP 및 MySQL의 큐 메시지 지속성 및 메시지 중복 제거에 대한 애플리케이션 시나리오

PHP 및 MySQL에서 대기열 메시지 누적 및 정체 제어를 처리하는 방법
