저장 성 빅 데이터 구조 연습 문제 노트: 06 - 그림 1 은 연결 집합 (그림 DFS 와 BFS 없 음) 을 보 여 줍 니 다.

14280 단어 데이터 구조알고리즘dfs도 론bfs
06 - 그림 1 은 연결 집합 을 보 여 줍 니 다 (그림 DFS 와 BFS 없 음)
원제
N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식: 첫 번 째 줄 을 입력 하여 정수 N 2 개 (0)
출력 형식: "{v 1 v2... v k}" 형식 으로 줄 마다 연결 집합 을 출력 합 니 다. DFS 결 과 를 먼저 출력 하고 BFS 결 과 를 출력 합 니 다.
입력 예시:
8 6
0 7
0 1
2 0
4 1
2 4
3 5

출력 예시:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

분석 하 다.
이 문 제 는 인접 행렬 법의 완전한 DFS 와 BFS 알고리즘 을 완성 한 것 이다.
전체 코드 구현
#include
#include
#include
#define MaxVertex 100
typedef int Vertex;
int G[MaxVertex][MaxVertex];
bool visit[MaxVertex];
int Ne,Nv;
using namespace std;


void Build(){
	cin>>Nv;
	for(int i=0;i<Nv;i++){
		visit[i] = false;
		for(int j=0;j<Nv;j++)
			G[i][j] = 0;		
	}
	cin>>Ne;
	for(int i=0;i<Ne;i++){
		int v1,v2;
		cin>>v1>>v2;
		G[v1][v2] = G[v2][v1] = 1;
	}
}

void DFS(Vertex v){
	visit[v] = true;
	cout<<" "<<v;
	for(int i=0;i<Nv;i++)
		if(visit[i] == 0 && G[v][i] != 0)
			DFS(i);
} 


void BFS(Vertex v){
	queue<Vertex> q;
	visit[v] = true;
	cout<<" "<<v;
	q.push(v);
	while(!q.empty()){
		Vertex tmp = q.front();
		q.pop();
		for(Vertex i=0;i<Nv;i++){
			if(visit[i] == 0 && G[i][tmp] != 0){
				visit[i] = true; 
				cout<<" "<<i;
				q.push(i);
			}
		}
	}
}

void ListComp(){
	for(Vertex i=0;i<Nv;i++)
		if(visit[i] == 0){
			cout<<"{";
			DFS(i);
			cout<<" }"<<endl;
		}

	for(Vertex i=0;i<Nv;i++)
		visit[i] = false;
	
	for(Vertex i=0;i<Nv;i++)
		if(visit[i] == 0){
			cout<<"{";
			BFS(i);
			cout<<" }"<<endl;
		}
}

int main(){
	Build();
	ListComp();
	return 0;
}
css3 내부 맵 360도 서라운드 각도
HTML5 & CSS3 노트: CSS3로 놀라운 아름다움 만들기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage