PTA | | 06 - 그림 1 연결 집합 목록
37415 단어 데이터 구조
입력 형식:
첫 번 째 줄 을 입력 하면 정수 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;
}
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.