(c 언어 상세 설명) 06 - 그림 1 은 연결 집합 을 보 여 줍 니 다 (상세 설명)

본 박문 은 절강대학 의 에서 재 료 를 얻 었 다.제목 은 PTA 에서 유래 했다.N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식: 첫 번 째 줄 을 입력 하여 정수 N 2 개 (0)
출력 형식: "{v1, v 2... 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 }

분석 삼판 도끼
주제 에 대면 하 다.
이 문 제 는 무 방향 그림, 즉 가중치 가 기본 값 으로 1 이 될 수도 있 고 설정 하지 않 을 수도 있 습 니 다. 그림 (위) 의 첫 번 째 문제 이기 때문에 당황 하지 마 세 요. 우 리 는 첫 번 째 줄 이 그림 의 정점 과 그림 의 변 을 다시 분석 하고 정점 과 변 이 확정 되 었 습 니 다. 다음은 변 만 삽입 하면 됩 니 다. 변 을 삽입 하 는 것 은 두 가지 값 입 니 다. 예 를 들 어:

 0 6

0 점 과 6 점 의 관 계 를 설정 해 야 한 다 는 뜻 입 니 다. 제목 에는 DFS 와 BFS 가 명확 합 니 다. 그래서 이것 은 전형 적 인 그림 을 옮 겨 다 니 며 연결 집합 을 찾 는 문제 입 니 다.
입 출력
한 문 제 를 해결 하기 위해 연구 해 야 할 알고리즘 을 고려 하면 반드시 입력, 처리, 출력 이 어야 합 니 다. 입력 은 BuildGraph 라 는 함 수 를 실현 시 키 는 것 입 니 다. 주로 노드 를 저장 하면 됩 니 다. 데 이 터 는 필요 하지 않 습 니 다. 그리고 심층 검색 과 광 검색 실현 에서 문제 의 요 구 를 굳 게 잡 고 ListComponents 함수 에 있어 서 형식 을 조정 하 십시오. 모든 가장 핵심 적 인 코드 는 수업 시간 에 강의 합 니 다.지나 간 것 은 맞 추고 정리 하 는 것 을 배 웁 니 다. 깊 은 검색 과 넓 은 검색 은 사상 이 중요 합 니 다. 사상 을 파악 하면 많은 문 제 를 해결 할 수 있 기 때 문 입 니 다. 억지로 옮 기 면 많은 결 과 를 잃 게 됩 니 다.
전체 코드 는 다음 과 같 습 니 다:

#include
#include
#define MaxVertexNum 10
#define MaxSize 10

typedef int WeightType;
typedef int Vertex;
typedef int ElementType;
int Visited_DFS[MaxVertexNum];
int Visited_BFS[MaxVertexNum];

struct GNode {
	int Nv;
	int Ne;
	WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef struct GNode* PtrToGNode;
typedef PtrToGNode MGraph;

struct ENode {
	Vertex V1,V2;
	WeightType Weight;
	
};
typedef struct ENode* PtrToENode;
typedef PtrToENode Edge;

struct Node {
	ElementType Data;
	struct Node* Next;
};

struct QNode {
	struct Node* front;
	struct Node* rear;
};
typedef struct QNode* Queue;

MGraph CreateGraph(int VertexNum);
void InsertEdge(MGraph,Edge E);
MGraph BuildGraph();
void Visit(Vertex V);
void DFS(MGraph Graph,Vertex V,void (*Visit)(Vertex));
void BFS(MGraph Graph,Vertex S,void (*Visit)(Vertex));
void ListComponents_DFS(MGraph Graph);
void ListComponents_BFS(MGraph Graph);
Queue CreateQueue();
void AddQ(Queue Q,Vertex S);
ElementType DeleteQ(Queue Q);

int main()
{
	Vertex V;

	MGraph Graph = BuildGraph();
	ListComponents_DFS(Graph);
	ListComponents_BFS(Graph);
	return 0;
}

//MGraph   
MGraph CreateGraph(int VertexNum) {
	Vertex V,W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	
	for(V=0;V<Graph->Nv;V++)
		for(W=0;W<Graph->Nv;W++)
			Graph->G[V][W]=0;
		
	return Graph;
}
//MGraph   
void InsertEdge(MGraph Graph,Edge E) {
	Graph->G[E->V1][E->V2] = E->Weight;
	Graph->G[E->V2][E->V1] = E->Weight;
	
}
//    MGraph
MGraph BuildGraph() {
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv,i;
	scanf("%d",&Nv);
	Graph = CreateGraph(Nv);
	scanf("%d",&(Graph->Ne));
	if(Graph->Ne != 0) {
		E = (Edge)malloc(sizeof(struct ENode));
		for(i=0;i<Graph->Ne;i++) {
			scanf("%d %d",&E->V1,&E->V2);
			E->Weight = 1;
			InsertEdge(Graph,E);
			
		}
			
	}
	for(V=0;V<Graph->Nv;V++) {
		Visited_BFS[V] = 0;
		Visited_DFS[V] = 0;
	}
	return Graph;
}
//    
void Visit(Vertex V) {
	printf(" %d",V);
}
//   DFS
void ListComponents_DFS(MGraph Graph) {
	
	for(Vertex V=0;V<Graph->Nv;V++) {
		if(!Visited_DFS[V]) {
			printf("{");
			DFS(Graph,V,Visit);
			printf(" }");
			printf("
");
		}
	}
}
//   BFS
void ListComponents_BFS(MGraph Graph) {
	
	for(Vertex V=0;V<Graph->Nv;V++) {
		if(!Visited_BFS[V]) {
			printf("{");
			BFS(Graph,V,Visit);
			printf(" }");
			printf("
");
		}
	}
}
//DFS  
void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex )) {
	Vertex W;
	Visited_DFS[V] = 1;
	Visit(V);
	for(W=0;W<Graph->Nv;W++)
	if(Graph->G[V][W] == 1 && !Visited_DFS[W])
		{
			DFS(Graph, W, Visit);
			
		}


}

void BFS(MGraph Graph,Vertex S,void (*Visit)(Vertex)) {
	Queue Q;
	Vertex V,W;
	Q = CreateQueue();
	Visit(S);
	Visited_BFS[S] = 1;
	AddQ(Q,S);
	
	while(Q->front != NULL ) {
		V = DeleteQ(Q);
		for(W = 0;W<Graph->Nv;W++) {
			if(Graph->G[V][W] == 1 && !Visited_BFS[W])
			{
				Visit(W);
				Visited_BFS[W] = 1;
				AddQ(Q,W);
			
			}
		}
	}
	
}
//J    ，    
Queue CreateQueue(){
    Queue Q;
    Q=(Queue)malloc(sizeof(struct QNode));
    Q->front=Q->rear=NULL;
    return Q;
}
/*   */
void AddQ(Queue Q,Vertex S){
    struct Node *temp;
    temp=(struct Node*)malloc(sizeof(struct Node));
    temp->Data=S;
    temp->Next=NULL;
    if(Q->front==NULL){
        Q->front=temp;
        Q->rear=temp;
    }
    else{
        Q->rear->Next=temp;
        Q->rear=temp;
    }
    // return Q;
}
/*   */
ElementType DeleteQ(Queue Q){
    struct Node *FrontCell;
    ElementType FrontElem;
    if(Q->front==NULL){
        return -1;
    }
    FrontCell=Q->front;
    if(Q->front==Q->rear)
        Q->front=Q->rear=NULL;
    else Q->front=Q->front->Next;
    FrontElem=FrontCell->Data;
    free(FrontCell);
    return FrontElem;
}