[BOJ/C+]#1260 DFSとBFS
問題を解く
基本的なDFS、BFSナビゲーションの問題.
DFSは再帰呼び出しを用い,BFSはキューを用いて実現する.
グラフは、ベクトル配列を使用した隣接リストとして表示されます.
2つの頂点の間には複数の幹線がある可能性があるので、各配列は昇順に配列されます.
アクセスするアクセス配列変数をチェックすることを忘れないでください.
コード#コード#
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1001
int N, M, V;
vector<int> map[MAX];
bool visited[MAX];
void dfs(int v){
cout<<v<<" ";
for(int i : map[v]){
if(!visited[i]){
visited[i]=true;
dfs(i);
}
}
}
void bfs(int v){
queue<int> q;
q.push(v);
visited[v]=true;
while(!q.empty()){
int idx=q.front();
q.pop();
cout<<idx<<" ";
for(int i : map[idx]){
if(!visited[i]){
q.push(i);
visited[i]=true;
}
}
}
}
int main(){
cin>>N>>M>>V;
for(int i=0;i<M;i++){
int a, b;
cin>>a>>b; //양방향
map[a].push_back(b);
map[b].push_back(a);
}
for(int i=1;i<=N;i++){
sort(map[i].begin(),map[i].end());
}
visited[V]=true;
dfs(V);
cout<<"\n";
//visited 초기화
memset(visited, false, sizeof(visited));
bfs(V);
cout<<"\n";
return 0;
}
Reference
この問題について([BOJ/C+]#1260 DFSとBFS), 我々は、より多くの情報をここで見つけました https://velog.io/@inryu/BOJ-C-1260-DFS와-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol