06-图1 列出连通集-白红宇

06-图1 列出连通集

阅读量：5081 次

发布时间：2019-06-13

本文共 2976 字，大约阅读时间需要 9 分钟。

给定一个有

输入格式:

输入第1行给出2个整数

输出格式:

按照"{

输入样例:

8 60 70 12 04 12 43 5

输出样例:

{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }

1 #include
     
        2 #include
      
         3 #define Max 10  4   5 bool Visited[Max];         //全局数组，记录每个结点是否被遍历   6   7 struct GNode{  8     int Data[Max][Max];  9     int Nv; 10     int Ne; 11 }; 12 typedef struct GNode *Graph; 13  14 //建立邻接矩阵存储的空图  15 Graph BuildGraph(int N, int E){ 16     Graph G = (Graph)malloc(sizeof(struct GNode)); 17     for(int i=0; i
       
        Data[i][j] = 0;             //0表示没有边，1表示有边 20         } 21     } 22     G->Nv = N; 23     G->Ne = E; 24     return G; 25 } 26  27 //读入图的边  28 void ReadEdge(Graph G, int E){ 29     int e1, e2; 30     for(int i=0; i
        
         Data[e1][e2] = 1; 33         G->Data[e2][e1] = 1; 34     } 35 } 36  37 //初始化Visited[]为全false  38 void InitVisited( ){ 39     for(int i=0; i
         
          Nv; j++){       49         if(G->Data[V][j]==1 && Visited[j]==false){   //选出与V相连且未被访问过的结点  50             DFS(G, j);                               //递归地进行深度优先遍历  51         } 52     } 53 } 54   55 struct QNode{ 56     int *data; 57     int front, rear; 58     int maxsize; 59 }; 60 typedef struct QNode *Queue; 61  62 //判断队列是否空函数  63 bool IsEmpty(Queue Q){ 64     return (Q->rear == Q->front); 65 } 66  67 //建立一个空队列  68 Queue BuildQ(int N){ 69     Queue Q = (Queue)malloc(sizeof(struct QNode)); 70     Q->data = (int*)malloc(sizeof(int)*N); 71     Q->front = Q->rear = 0; 72     Q->maxsize = N; 73     return Q; 74 } 75  76 //入队函数  77 void AddQ(Queue Q, int X){ 78     Q->rear = (Q->rear + 1)%Q->maxsize ; 79     Q->data[Q->rear] = X; 80 } 81  82 //出队函数  83 int  DeleteQ(Queue Q){ 84     Q->front = (Q->front + 1)%Q->maxsize; 85     return Q->data[Q->front]; 86 } 87  88 //广度优先遍历  89 void BFS(Graph G, int V){ 90     Queue Q = BuildQ(G->Nv); 91     printf("%d ", V);           //访问V  92     Visited[V] = true;          //将Visited[V]置为已被访问过  93     AddQ(Q, V);                 //将V入队  94     while(!IsEmpty(Q)){         //当队列不空  95         int W = DeleteQ(Q);              //取出队头元素  96         for(int i=0; i
          
           Nv; i++){ 97 if(!Visited[i] && G->Data[W][i]==1){ //选出与队头元素相连且未被访问过的元素 98 printf("%d ", i); 99 Visited[i] = true;100 AddQ(Q, i);101 }102 }103 }104 }105 106 int main(){107 int N, E;108 scanf("%d %d", &N, &E); 109 Graph G = BuildGraph(N, E); //建立邻接矩阵储存的图 110 ReadEdge(G, E); //读入图的边 111 InitVisited();112 for(int i=0; i
           
            Nv; i++){ 113 if(Visited[i]==false){114 printf("{ ");115 DFS(G, i);116 printf("}\n");117 }118 } 119 InitVisited(); //每次遍历前要将Visited[]初始化 120 for(int i=0; i
            
             Nv; i++){ 121 if(Visited[i]==false){122 printf("{ ");123 BFS(G, i); 124 printf("}\n");125 }126 }127 return 0;128 }