목차
algorithm
Example
Output
백엔드 개발 C++ 벡터와 큐를 이용하여 BFS를 구현하고, C 프로그램에서 CLRS 알고리즘을 구현한다.

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

Sep 06, 2023 pm 04:37 PM
대기줄 벡터 bfs (breadth-first search)

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

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으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

Laravel 개발 노트: 캐시와 큐의 적절한 사용 Laravel 개발 노트: 캐시와 큐의 적절한 사용 Nov 22, 2023 am 11:46 AM

Laravel 개발 노트: 캐시와 큐의 적절한 사용

PHP 및 MySQL의 데드 레터 큐 및 지연 큐의 애플리케이션 시나리오 PHP 및 MySQL의 데드 레터 큐 및 지연 큐의 애플리케이션 시나리오 Oct 15, 2023 am 11:46 AM

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

PHP 및 MySQL에서 대기열 메시지 필터링 및 메시지 라우팅을 구현하는 방법 PHP 및 MySQL에서 대기열 메시지 필터링 및 메시지 라우팅을 구현하는 방법 Oct 15, 2023 pm 04:55 PM

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

벡터와 큐를 이용하여 BFS를 구현하고, C 프로그램에서 CLRS 알고리즘을 구현한다. 벡터와 큐를 이용하여 BFS를 구현하고, C 프로그램에서 CLRS 알고리즘을 구현한다. Sep 06, 2023 pm 04:37 PM

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

PHP 및 MySQL의 큐 메시지 지속성 및 메시지 중복 제거에 대한 애플리케이션 시나리오 PHP 및 MySQL의 큐 메시지 지속성 및 메시지 중복 제거에 대한 애플리케이션 시나리오 Oct 15, 2023 pm 01:42 PM

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

C++의 스택과 큐 C++의 스택과 큐 Aug 22, 2023 am 11:00 AM

C++의 스택과 큐

Java에서 큐를 사용하여 스택을 어떻게 구현할 수 있나요? Java에서 큐를 사용하여 스택을 어떻게 구현할 수 있나요? Aug 25, 2023 pm 05:05 PM

Java에서 큐를 사용하여 스택을 어떻게 구현할 수 있나요?

PHP 및 MySQL에서 대기열 메시지 누적 및 정체 제어를 처리하는 방법 PHP 및 MySQL에서 대기열 메시지 누적 및 정체 제어를 처리하는 방법 Oct 15, 2023 am 09:24 AM

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

See all articles