標準1260:DFSとBFS★

★★★★☆
DFSとBFSが何なのかわからないままスタートしたので、難易度が高いと感じました.

質問する

https://www.acmicpc.net/problem/1260

コンセプト

(熱血資料構造書を参考にして、私の理解するように整理)

DFS
1)深度優先ナビゲーション.一筋の道が深く入り込む.
2)任意の優先順位(この問題では、より小さい数の頂点)で1つの頂点に到達する.
※ある道を歩けないことを心配する必要はありません.
3)袋小路に着いたらコールの頂点に戻る
(関数の理由を定義します.呼び出しコードの次のコードが実行される場合があります.)
4)デッドパス:接続された頂点がすべてアクセスした頂点が

である場合

BFS
1)まず幅をブラウズします.自分に関連するすべての頂点を記録します.
2)最初に接続された頂点を巡り、次に進みます.
したがって,queueのような資料構造に頂点を置き,すべてをブラウズした後,1つずつ取り出して継続する.(DFSとの違い)
3)デッドパス:キューに頂点がない場合は

私の答え

#include <iostream>
#include <queue>
#define MAXSIZE 1001
using namespace std;

int n, m, v;
bool graph[MAXSIZE][MAXSIZE];
bool visit[MAXSIZE];
queue<int> dfsqueue;

void resetvisit() {
	for (int i = 0; i < MAXSIZE; i++) {
		visit[i] = false;
	}
}

void dfs(int p) {//DFS, 깊이우선탐색
	visit[p] = true;
	cout << p << " ";

	for (int i = 1; i <=n; i++) {
		if (graph[p][i]&&!visit[i]) { //연결되어 있고, 방문하지 않았다면 다음으로
			visit[i] = true; //방문 기록
			dfs(i); 
		}
	}
	return; //방문할 노드가 없다면 리턴
}

void bfs(int p) {//BFS, 너비우선탐색
	dfsqueue.push(p); //현재 정점을 실행하기 위해 push해줌
	visit[p] = true;
	cout << p << " ";

	while (!dfsqueue.empty()) {
		int tem = dfsqueue.front();
		dfsqueue.pop();
		for (int i = 1; i <= n; i++) {
			if (graph[tem][i] && !visit[i]) { //연결되어 있고, 방문하지 않았다면 다음으로
				visit[i] = true; //방문 기록
				dfsqueue.push(i); //큐에 정점 기록하기
				cout << i << " ";
			}
		}
	}
	return;
}

int main() {
	
	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		graph[x][y] = true;
		graph[y][x] = true;
	}

	resetvisit();
	dfs(v);
	cout << "\n";

	resetvisit();
	bfs(v);
	cout << "\n";
	return 0;
}

グローバル変数を用いて解くが,関数のパラメータが図形や配列を伝達する方法もある.
classを使ってグラフィックも実現しましたが、コードが重くなってあまりメリットがないので2次元配列に変更しました.