C++グラフィックス-深さと広さの遍歴

(無方向)図の遍歴は,最もよく用いられる深さ優先遍歴であり,また探索アルゴリズムと類似した広さ優先遍歴もある.アクセスしたノードをマークすることを忘れないでください.
 
(一)深さ優先遍歴
sを起点として遍歴し,sに辺がある点を起点として遍歴する.スタック(再帰呼び出し)によって実現される.
 

#include 
using namespace std;

int n, m, s;
int a[2001][2001];
bool visited[2001]; //     

void build_graph() {
	int x, y;
	cin >> n >> m >> s;
	for(int i=1; i<=m; i++) {
		cin >> x >> y;
		a[x][y] = a[y][x] = 1;
	}
}

void dfs(int x) {					  // x     
	if(visited[x] == true) return;
	visited[x] = true;
	cout << x << " -> ";
	for(int i=1; i<=n; i++)
		if(!visited[i] && a[x][i] == 1) //x y      i     
			dfs(i); 
}

int main() {
	build_graph();
	dfs(s); // s      
}

(二)広さ優先遍歴(階層遍歴)
sを起点として,sをキューに入れ,再循環:キューを出てkを得,kのすべての関連点をキューに入れる.キューによって実現される.
C++STL解:

#include 
#include 
using namespace std;

int n, m, s;
int a[2001][2001];
int visited[2001];       //     
bool inq[2001];          //      

queue q;

void build_graph() {
	int x, y;
	cin >> n >> m >> s;
	for(int i=1; i<=m; i++) {
		cin >> x >> y;
		a[x][y] = a[y][x] = 1;
	}
}

void bfs(int x) {
	int k;
	q.push(x);
	inq[x] = true;
	while(!q.empty()) {
		k = q.front();
		q.pop();
		cout << k << " -> ";
		visited[k] = true;
		inq[k] = false;
		for(int i=1; i<=n; i++) {
			if(a[k][i] == 1 && !visited[i] && !inq[i]) {
				q.push(i);
				inq[i] = true;
			}
		}
	}
}

int main() {
	build_graph();
	bfs(s);
	return 0;
}

QWQ ...