PTA | | 06 - 그림 1 연결 집합 목록

37415 단어 데이터 구조
NNN 의 정점 과 EEE 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 모든 연결 집합 을 각각 표시 하 십시오.정점 이 0 에서 N - 1N - 1N - 1 번 이 라 고 가정 하 세 요.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식:
첫 번 째 줄 을 입력 하면 정수 NNN (00 < N ≤ 10) 과 EEE 를 2 개 드 립 니 다. 각각 그림 의 정점 과 변 수 를 드 립 니 다.그 다음 에 EEE 줄 은 줄 마다 한 변 의 두 점 을 제시 합 니 다.줄 마다 숫자 사 이 를 1 칸 으로 구분한다.
출력 형식:
"{v1v 1v 1 v2v 2v 2... vkv kv 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 }

BFS (범위 우선 검색):
void BFS(MGraph Graph, Vertex V)
//BFS   ,          
{
	Vertex W;
	Queue Q;
	Q = CreateQ(Graph->Nv );//       MaxVertexNum     
	if (Visited[V])
		return;
	Visited[V] = true;
	printf("%d ", V);
	AddQ(Q, V);
	while(!IsEmpty(Q)){ 
		V = DeleteQ(Q);
		for (W = 0; W<Graph->Nv ; W++){
			if (!Visited[W] && Graph->G[V][W] ==1){
				Visited[W] = true;
				printf("%d ", W);
				AddQ(Q, W);
			}
		}
	}//    ,             

DFS (깊이 우선 검색):
void DFS(MGraph Graph, Vertex V)
//DFS  ,          
{
	Vertex W;
	if (Visited[V])
		return;
	Visited[V] = true;
	printf("%d ", V);
	for (W = 0; W < Graph->Nv ; W++){
		if (!Visited[W] && Graph->G[V][W] == 1)
			DFS(Graph, W);
	}
}

전체 8195: 전체 8195: 위의 두 표준 코드 세그먼트 는 모두 하나의 연결 분량 에 대해 검색 프로그램 이 그림 에 있 는 연결 분량 을 한 번 호출 합 니 다.그림 의 모든 연결 분량 을 옮 겨 다 니 려 면 그림 의 모든 정점 에 검색 프로그램 을 호출 할 수 있 습 니 다.
/*
	Name:  1      .cpp 
	Copyright: 
	Author: xuuyann
	Date: 04/11/18 21:06
	Description: 
*/

#include 
#include 
#define MaxVertexNum 10
#define Vertex int
#define WeightType int
#define DataType int
#define ElementType int
#include 


//        
//      
typedef struct GNode *PtrToGNode;
struct GNode {
	int Nv;//    
	int Ne;//  
	WeightType G[MaxVertexNum][MaxVertexNum];//    ,           
	//DataType Data[MaxVertexNum];//      
};
typedef PtrToGNode MGraph;
//    
typedef struct ENode *PtrToENode;
struct ENode {
	Vertex V1;
	Vertex V2;//      (  ) 
}; 
typedef PtrToENode Edge;
//    
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
	ElementType *Data;
	Position front, rear;
	int MaxSize;
}; 
typedef PtrToQNode Queue;
bool Visited[MaxVertexNum];//    。    false 

Queue CreateQ(int MaxSize)
//   
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType *)malloc(MaxSize*sizeof(ElementType));
	Q->front = Q->rear = 0;
	Q->MaxSize = MaxSize;
} 
void AddQ(Queue Q, ElementType V)
//   
{
	Q->rear = (Q->rear + 1)%Q->MaxSize ;
	Q->Data[Q->rear ] = V;
 } 
 
ElementType DeleteQ(Queue Q)
//   
{
	Q->front = (Q->front +1)%Q->MaxSize;
	return Q->Data[Q->front ];
 }
bool IsEmpty(Queue Q)
//        
{
	return (Q->rear ==Q->front );
 } 
 
MGraph CreateM(int V)
//    ,        V、  E 0   
{
	int i, j;
	MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = V;
	Graph->Ne = 0;
	for (i = 0; i<Graph->Nv ; i++){
		for (j = 0; j<Graph->Nv ; j++)
			Graph->G[i][j] = 0;//           
	}
	
	return Graph;
} 

void InsertEdge(MGraph Graph, Edge E)
//    
{
	Graph->G[E->V1 ][E->V2 ] = 1;
	Graph->G[E->V2 ][E->V1 ] = 1;//    
} 

MGraph BuildGraph()
//   
{
	MGraph Graph;
	Edge E;
	int VertexNum, EdgeNum, i;
	scanf("%d %d", &VertexNum, &EdgeNum);
	Graph = CreateM(VertexNum);
	Graph->Ne = EdgeNum;
	if (Graph->Ne != 0){
		E =(Edge)malloc(sizeof(struct ENode)); 
		for (i = 0; i < Graph->Ne; i++){
			scanf("%d %d", &E->V1 ,&E->V2 );
			InsertEdge(Graph, E);
		}
	}
	
	return Graph;
}

void DFS(MGraph Graph, Vertex V)
//DFS  ,          
{
	Vertex W;
	if (Visited[V])
		return;
	Visited[V] = true;
	printf("%d ", V);
	for (W = 0; W < Graph->Nv ; W++){
		if (!Visited[W] && Graph->G[V][W] == 1)
			DFS(Graph, W);
	}
}

void BFS(MGraph Graph, Vertex V)
//BFS   ,          
{
	Vertex W;
	Queue Q;
	Q = CreateQ(Graph->Nv );//       MaxVertexNum     
	if (Visited[V])
		return;
	Visited[V] = true;
	printf("%d ", V);
	AddQ(Q, V);
	while(!IsEmpty(Q)){ 
		V = DeleteQ(Q);
		for (W = 0; W<Graph->Nv ; W++){
			if (!Visited[W] && Graph->G[V][W] ==1){
				Visited[W] = true;
				printf("%d ", W);
				AddQ(Q, W);
			}
		}
	}//    ,             
}

void ListDFS(MGraph Graph)
{
	int i;
	for (i = 0; i<Graph->Nv ; i++){
		if (!Visited[i]){
			printf("{ "); 
			DFS(Graph, i);
			printf("}
"
); } } } void ListBFS(MGraph Graph) { int i; for (i = 0; i<Graph->Nv ; i++){ if (!Visited[i]){ printf("{ "); BFS(Graph, i); printf("}
"
); } } } // int main() { int i; MGraph G; G = BuildGraph();// for (i = 0; i < G->Nv ; i++) Visited[i] = false; ListDFS(G);//DFS(MGraph Graph, Vertex V)//DFS for (i = 0; i < G->Nv ; i++) Visited[i] = false; ListBFS(G);//void BFS(MGraph Graph, Vertex V)//BFS return 0; } /* // #include #include #include using namespace std; #define MaxSive 10 int graph[MaxSive][MaxSive]; int Nv, Ne; int check[MaxSive]; void buildGraph() { int V1, V2; scanf("%d %d",&Nv, &Ne); //CreateGraph for (int i = 0; i < Nv;i++) { check[i] = 0; for (int j = 0; j < Ne;j++) { graph[i][j] = 0; } } for (int i = 0; i < Ne; i++) { scanf("%d %d",&V1,&V2); // //InsertEdge graph[V1][V2] = 1; graph[V2][V1] = 1; } } int checkVisited() { int i; for (i = 0; i < Nv;i++) { if (!check[i]) { break; } } if (i==Nv) { return -1; } return i; } void BFS() { queue Q; int i, j; i = checkVisited(); if (i==-1) { return; } Q.push(i); check[i] = true; printf("{ %d ", i); // 0 // while (!Q.empty()) { int temp = Q.front(); Q.pop(); for (j = 0; j < Nv;j++) { if (graph[temp][j]==1&&!check[j]) { check[j] = 1; printf("%d ", j); Q.push(j); } } } printf("}
"); return BFS(); // } void DFS(int V) { check[V] = 1; printf("%d ",V); for (int i = 0; i < Nv; i++) { if (graph[V][i]==1&&!check[i]) { DFS(i); } } } void DFSList() { for (int i = 0; i < Nv;i++) { if (check[i]==0) { printf("{ "); DFS(i); printf("}
"); } } } int main() { buildGraph(); DFSList(); //memset(check, 0, sizeof(int)*MaxSive); for (int i = 0; i < Nv; i++) { check[i] = 0; } BFS(); return 0; } */

좋은 웹페이지 즐겨찾기