PTA 資料結構與算法 7-6 列出連通集

如有不對，不吝賜教

直接進入正題：

給定一個有N個頂點和E條邊的無向圖，請用DFS和BFS分别列出其所有的連通集。假設頂點從0到N−1編号。進行搜尋時，假設我們總是從編号最小的頂點出發，按編号遞增的順序通路鄰接點。

輸入格式:

輸入第1行給出2個整數N(0<N≤10)和E，分别是圖的頂點數和邊數。随後E行，每行給出一條邊的兩個端點。每行中的數字之間用1空格分隔。

輸出格式:

按照"{ 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 }

這就是十分基本的搜尋問題，BFS和DFS的差別在于：前者是一層一層的搜尋，而後者則是一條路走到底，撞了南牆才回頭

下面給代碼：

#include<stdio.h>

int count=0;   //記錄目前通路節點個數
int edge[10][10];
int queue[10];    //BFS時的隊列
int head,tail;    //隊列的頭尾

void DFS(int *visit,int i,int N);
void BFS(int *visit,int N);

int main(void)
{
    int N,E;
    int i,j;
    int V1,V2;
    scanf("%d %d",&N,&E);

    int visit[N];

    for(i=0;i<N;i++){
      for(j=0;j<N;j++)
        if(i==j)
          edge[i][j]=1;
        else
          edge[i][j]=0;
      visit[i]=0;   //表示還沒有找到過
    }

    for(i=0;i<E;i++){
      scanf("%d %d",&V1,&V2);
      edge[V1][V2]=edge[V2][V1]=1;
    }

    i=0;
    visit[0]=1;
    while(count!=N){
      count++;
      printf("{ %d ",i);
      DFS(visit,i,N);
      printf("}\n");
      while(visit[i]&&i<N)
        i++;       //找到序号最小的且沒有通路過的節點
      if(i!=N)
      visit[i]=1;   // 防越界
    }

    for(i=0;i<N;i++)
      visit[i]=0;       //初始化
    count=0;

    i=0;
    while(count!=N){
      head=0;
      tail=1;
      queue[0]=i;    //初始化隊列
      visit[i]=1;
      count++;
      printf("{ ");
      BFS(visit,N);
      printf("}\n");
      while(visit[i]&&i<N)
        i++;
    }

    return 0;
}

void DFS(int *visit,int i,int N)  //通路與否 從第幾個節點開始
{                                             //頂點個數
     if(count==N)
       return ;
     int j=0;

     while(j<N){
       while((j<N&&visit[j])||i==j)
         j++;   //找到除了i的第一個沒通路過的頂點
       if(j<N&&edge[i][j]){
         printf("%d ",j);
         visit[j]=1;
         count++;
         DFS(visit,j,N);   //從j開始繼續找
       }       // i j之間有連接配接
       j++;
     }

     return ;
}

void BFS(int *visit,int N)
{
    int i;

    do{
      i=0;
      while(i<N){
        while(i<N&&visit[i])
          i++;        // 找到編号最小的 還沒有通路過的頂點
        if(i<N&&edge[queue[head]][i]){
          queue[tail]=i;
          tail++;
          count++;          //扔到隊列中去
          visit[i]=1;
        }
        i++;
      }
      head++;
    }while(head+1<=tail);

    for(i=0;i<tail;i++)
      printf("%d ",queue[i]);

    return ;
}

           

注意BFS要用隊列來輔助，這樣就可以把某個節點的下一層節點全給找出來

還有就是DFS的搜尋資料太大的時候會造成堆棧溢出

結果：