데이터 구조 - 재 귀 와 비 재 귀 실현 DFS 와 BFS

28834 단어 데이터 구조
선생님 의 데이터 구조 수업 숙제
c++ c + c++ c++ 의 vector 로 썼 습 니 다. 사실 자세 한 것 도 어렵 지 않 습 니 다. 코드 를 참조 하 십시오. DFS 와 BFS 의 참조 가 없 으 면: 자 료 는 BFS 로 귀속 합 니 다.
#include 

using namespace std;

const int maxn = 1e5 + 50 ;

vector<int>G[maxn] ;
int n ,m ,u ,v ,st ;

queue<int>que ;

void BFS(int st) {
	int len = G[st].size();
	for (int i = 0 ; i < len ; i ++ ) {
		que.push(G[st][i]);
	}
	if ( !que.empty() ) {
		int top = que.front() ; que.pop() ;
		printf("%d ",top) ;
		BFS(top) ;
	}
}

int main() {
	printf("            : ");
	scanf("%d %d",&n ,&m ) ;
	for (int i = 1 ; i <= m ; i ++ ) {
		printf("    %d       : ",i); 
		scanf("%d %d",&u ,&v ) ;
		G[u].push_back(v);
	}
	printf("       : ");
	scanf("%d",&st);
	printf("BFS       : ");
	printf("%d ",st);
	BFS(st);
	return 0;
} 

비 귀속 BFS
#include 

using namespace std;

const int maxn = 1e5 + 50 ;

vector<int>G[maxn] ;
int n ,m ,u ,v ,st ;

void BFS(int st) {
	queue<int>que;
	que.push(st) ;
	while ( !que.empty() ) {
		int top = que.front() ; que.pop() ;
		printf("%d ",top) ;
		int len = G[top].size();
		for (int i = 0 ; i < len ; i ++ ) {
			que.push(G[top][i]);
		}
	}
}

int main() {
	printf("            : ");
	scanf("%d %d",&n ,&m ) ;
	for (int i = 1 ; i <= m ; i ++ ) {
		printf("    %d       : ",i); 
		scanf("%d %d",&u ,&v ) ;
		G[u].push_back(v);
	}
	printf("       : ");
	scanf("%d",&st);
	printf("BFS        : ");
	BFS(st) ;
	return 0;
}

DFS 재 귀
#include 

using namespace std;

const int maxn = 1e5 + 50 ;

vector<int>G[maxn] ;
int n ,m ,u ,v ,st ;

void DFS(int st) {
	int len = G[st].size();
	for (int i = 0 ; i < len ; i ++ ) {
		printf("%d ",G[st][i]);
		DFS(G[st][i]);
	}
}

int main() {
	printf("            : ");
	scanf("%d %d",&n ,&m ) ;
	for (int i = 1 ; i <= m ; i ++ ) {
		printf("    %d       : ",i); 
		scanf("%d %d",&u ,&v ) ;
		G[u].push_back(v);
	}
	printf("       : ");
	scanf("%d",&st);
	printf("DFS       : ");
	printf("%d ",st);
	DFS(st);
	return 0;
} 

비 귀속 DFS
#include 

using namespace std;

const int maxn = 1e5 + 50 ;

vector<int>G[maxn];
stack<int>sta ;
int n ,m ,st ,u ,v ; 

void DFS(int st) {
	sta.push(st) ;
	while ( !sta.empty() ) {
		int top = sta.top(); sta.pop();
		int len = G[top].size();
		for (int i = 0 ; i < len ; i ++ ) {
			sta.push(G[top][i]);
		}
		printf("%d ",top);
	}
}

int main() {
	printf("            : ");
	scanf("%d %d",&n ,&m ) ;
	for (int i = 1 ; i <= m ; i ++ ) {
		printf("    %d       : ",i ); 
		scanf("%d %d",&u ,&v ) ;
		G[u].push_back(v);
	}
	printf("       : ");
	scanf("%d",&st);
	printf("DFS       : ");
	DFS(st);
	return 0;
}

좋은 웹페이지 즐겨찾기