그림 의 조작 --- 건설 도, DFS, BFS 스 트 리밍 도

그림 의 기본 동작 인 건 도, DFS, BFS 스 트 리밍 그림 은 N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.입력 형식: 첫 번 째 줄 을 입력 하면 정수 N (0 출력 형식: "{v 1 v 2... v k}" 형식 에 따라 줄 마다 연결 집합 을 출력 합 니 다. DFS 결 과 를 먼저 출력 하고 BFS 결 과 를 출력 합 니 다.사고: 1. 어떤 저장 도 를 사용 합 니까? 인접 행렬 or 인접 표 는 이 문제 에서 '항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 점점 증가 하 는 순서에 따라 인접 점 을 방문 합 니 다' 라 는 요구 가 있 습 니 다.인접 표 는 변 의 입력 순서에 따라 삽 입 된 것 이다. 즉, 번호 가 무질서 하고 행렬 저장 소 는 0 에서 시작 하여 순서대로 증가 하기 때문에 여 기 는 인접 행렬 2. 다음 에 코드 (1) 헤더 파일 을 쓰 는 것 을 선택한다.

#include

(2) 저장 구조

typedef struct ENode{
 vertex V1,V2;
}*Edge;

typedef struct GNode{
 int Nv;
 int Ne;
 int G[MaxSize][MaxSize];
}*MGraph;

(3) 주 함수

int main(){
 int N,E;
 MGraph Graph;
 scanf("%d%d",&N,&E); //        
 Graph=InitGraph(N);  //    
 Graph=CreateGraph(Graph,E);//   
 total_DFS(Graph); //DFS  
 total_BFS(Graph);//BFS  
 return 0;
}

(4) 그림 초기 화

MGraph InitGraph(int N){   
MGraph Graph;
 Graph=(MGraph)malloc(sizeof(struct GNode));
 Graph->Nv=N;  //   
 Graph->Ne=0;  //       0
 int V,W;
 for(V=0;V<Graph->Nv;V++)
 for(W=0;W<Graph->Nv;W++)
   Graph->G[V][W]=0;
 for(V=0;V<Graph->Nv;V++){
   Visited_DFS[V]=0;  //     
   Visited_BFS[V]=0;  //     
  }
  return Graph;
}

삽입 변

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

구조 도

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

DFS 옮 겨 다 니 기

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



void total_DFS(MGraph Graph){
 vertex V;
 for(V=0;V<Graph->Nv;V++){
  if(Visited_DFS[V]==0)
  { printf("{");
   DFS(Graph,V);
   printf(" }");
   printf("
");}
 }
}

BFS 옮 겨 다 니 기

void BFS(MGraph Graph,vertex V){  
 Queue Q;
 Q=InitQ();
 AddQ(Q,V);
 Visited_BFS[V]=1;
 printf(" %d",V);
 vertex W;
 while(!IsEmpty(Q)) {
  V=DeleteQ(Q);
 for(W=0;W<Graph->Nv;W++){
  if(!Visited_BFS[W]&&Graph->G[V][W]==1){
   printf(" %d",W);
   AddQ(Q,W);
   Visited_BFS[W]=1;
    }
 }
 }
}     

우 리 는 여기에 대열 을 짓 고, 대열 을 나 가 고, 대열 에 들 어 가 는 조작 대열 의 유형 정 의 를 진행 해 야 한다.

typedef struct QNode{
 int Data[10];
 int front;
 int rear;
}*Queue; 

초기 화

Queue InitQ(){
 Queue Q;
 Q=(Queue)malloc(sizeof(struct QNode));
 Q->front=Q->rear=0;
 return Q;
}

//        
int IsEmpty(Queue Q){
 return Q->front==Q->rear;
}

대열 에 들어가다

void AddQ(Queue Q,vertex V){
 if((Q->rear+1)%MaxSize!=Q->front)
 {   Q->rear=(Q->rear+1)%MaxSize;
  Q->Data[Q->rear]=V;
 }
}

대열 에 나가다

int DeleteQ(Queue Q){
 if(Q->front==Q->rear) return -1;
 else {
  Q->front=(Q->front+1)%MaxSize;
  return Q->Data[Q->front];
 }
}

전체 코드

#include
#include
typedef int vertex;
#define MaxSize 10
int Visited_DFS[MaxSize];
int Visited_BFS[MaxSize];
typedef struct ENode{
 vertex V1,V2;
}*Edge;          
typedef struct GNode{
 int Nv;
 int Ne;
 int G[MaxSize][MaxSize];
}*MGraph;
typedef struct QNode{
 int Data[10];
 int front;
 int rear;
}*Queue; 
 //  
Queue InitQ(){
 Queue Q;
 Q=(Queue)malloc(sizeof(struct QNode));
 Q->front=Q->rear=0;
 return Q;
}

int IsEmpty(Queue Q){
 return Q->front==Q->rear;
}
void AddQ(Queue Q,vertex V){
 if((Q->rear+1)%MaxSize!=Q->front)
 {   Q->rear=(Q->rear+1)%MaxSize;
  Q->Data[Q->rear]=V;
 }
}

int DeleteQ(Queue Q){
 if(Q->front==Q->rear) return -1;
 else {
  Q->front=(Q->front+1)%MaxSize;
  return Q->Data[Q->front];
 }
}

MGraph InitGraph(int N){    
 MGraph Graph;
 Graph=(MGraph)malloc(sizeof(struct GNode));
 Graph->Nv=N;
 Graph->Ne=0;
 int V,W;
 for(V=0;V<Graph->Nv;V++)
  for(W=0;W<Graph->Nv;W++)
   Graph->G[V][W]=0;
 for(V=0;V<Graph->Nv;V++){
   Visited_DFS[V]=0;
   Visited_BFS[V]=0;
  }
 return Graph;
}

void InsertEdge(MGraph Graph,Edge E){
 Graph->G[E->V1][E->V2]=1;
 Graph->G[E->V2][E->V1]=1;
}
MGraph CreateGraph(MGraph Graph,int Ne){   
 Graph->Ne=Ne;
 Edge E;
 if(Graph->Ne!=0){
  E=(Edge)malloc(sizeof(struct ENode));
  for(int i=0;i<Graph->Ne;i++){
   scanf("%d %d",&E->V1,&E->V2);
   InsertEdge(Graph,E);
    }
 }
 return Graph;
}

void DFS(MGraph Graph,vertex V){
  printf(" %d",V);
  Visited_DFS[V]=1;
  vertex W;
  for(W=0;W<Graph->Nv;W++)
   if(!Visited_DFS[W]&&Graph->G[V][W]==1)
   DFS(Graph,W);
}
void total_DFS(MGraph Graph){
 vertex V;
 for(V=0;V<Graph->Nv;V++){
  if(Visited_DFS[V]==0)
  { printf("{");
   DFS(Graph,V);
   printf(" }");
   printf("
");}
    }
}

void BFS(MGraph Graph,vertex V){  
 Queue Q;
 Q=InitQ();
 AddQ(Q,V);
 Visited_BFS[V]=1;
 printf(" %d",V);
 vertex W;
 while(!IsEmpty(Q)) {
  V=DeleteQ(Q);
 for(W=0;W<Graph->Nv;W++){
  if(!Visited_BFS[W]&&Graph->G[V][W]==1){
   printf(" %d",W);
   AddQ(Q,W);
   Visited_BFS[W]=1;
    }
 }
 }
}     
void total_BFS(MGraph Graph){
 vertex V;
 for(V=0;V<Graph->Nv;V++){
  if(Visited_BFS[V]==0)
  { printf("{");
   BFS(Graph,V);
   printf(" }");
   printf("
");}
   }
}
int main(){
 int N,E;
 MGraph Graph;
 scanf("%d%d",&N,&E);
 Graph=InitGraph(N);
 Graph=CreateGraph(Graph,E);
 total_DFS(Graph);
 total_BFS(Graph);
 return 0;
 }