《 데이터 구 조 》 06 - 그림 1 은 연결 집합 을 보 여 준다.

14623 단어 데이터 구조데이터 구조 (저장 성)
제목.
N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식: 첫 번 째 줄 을 입력 하면 2 개의 정수 N (0 < N ≤ 10) 과 E E 를 보 여 줍 니 다. 각각 그림 의 정점 과 변 수 를 보 여 줍 니 다.그 다음 에 E 줄 은 줄 마다 한 변 의 두 점 을 제시 합 니 다.줄 마다 숫자 사 이 를 1 칸 으로 구분한다.
출력 형식: "{v 1 v 2... v k v 1 v 2... v k v1 v2.. vk}" 형식 으로 줄 마다 연결 집합 을 출력 합 니 다.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 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] = 1;
		G[v2][v1] = 1;
	}
}

void DFS(Vertex v){
	//       
	visit[v] = true;
	cout<<" "<<v;
	for(int i=0;i<Nv;i++)
		if(!visit[i] && G[v][i])
			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] && G[i][tmp]){
				visit[i] = true; 
				cout<<" "<<i;
				q.push(i);
			}
		}
	}
}

//       
void ListComp(){
	for(Vertex i=0;i<Nv;i++)
		if(!visit[i]){
			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]){
			cout<<"{";
			BFS(i);
			cout<<" }"<<endl;
		}
}

int main(){
	Build();
	ListComp();
	return 0;
}
코드 탐색
데이터 구조 (2) - 스 택, 대기 열

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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