06-图1 列出连通集

一时失言乱红尘 2022-08-21 11:48 136阅读 0赞

给定一个有NNN个顶点和EEE条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1N-1N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

### 输入格式: ###

输入第1行给出2个整数NNN(0<N≤100<N\\le 100<N≤10)和EEE，分别是图的顶点数和边数。随后EEE行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

### 输出格式: ###

按照"\{ v1v\_1v1v2v\_2v2 ... vkv\_kvk \}"的格式，每行输出一个连通集。先输出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 }

主要注意的是用深度优先搜索时，用队列来装遍历点的周边相连节点，不过队列的这个可以改进一下。。。

#include <stdio.h>
        #include <stdlib.h>
    
        #define MaxVertexNum 10
        int Visited[MaxVertexNum];  //用来装连通集状态的数组，来表示是否访问过，可以避免出现输出两个连通集一样的情况
    
        typedef struct MGraph{
            int Vertices[MaxVertexNum];
            int Edges[MaxVertexNum][MaxVertexNum];
            int n, e;   //连通图的顶点和边数
        } MGraph;
    
        typedef struct QNode{
            int Data[MaxVertexNum];
            int rear;   //结尾下标
            int front;  //指向0下标
        } QNode, *Queue;
    
        void Reset_tmp(MGraph *G);
        void Reset_Visited();
        int Check_Visited(MGraph *G);
    
        Queue Create_Queue();
        void Add_Queue(Queue Q, int item);
        int Delete_Queue(Queue Q);
        int IsEmpty_Queue(Queue Q);
    
        void Create_MGraph(MGraph *G);  //建邻接矩阵
        void DFS(MGraph *G, int i);
        void BFS(MGraph *G);
        int FirstAdjV(MGraph *G, int V);
        int NextAdjV(MGraph *G, int V, int W);
    
        int main(int argc, char const *argv[])
        {
            // freopen("test.txt", "r", stdin);
            for (int i = 0; i < MaxVertexNum; i++)
                Visited[i] = 0;
            MGraph G;
            Create_MGraph(&G);
            for (int i = 0; i < G.n; i++){
                if (Visited[i] == 0){
                    printf("{ ");
                    DFS(&G, i);
                    printf("}\n");
                }
            }
            Reset_Visited();
            BFS(&G);
            return 0;
        }
    
        Queue Create_Queue()
        {
            Queue Q = (Queue)malloc(sizeof(QNode));
            Q->rear = Q->front = 0;
            return Q;
        }
    
        void Add_Queue(Queue Q, int item)
        {
            if((Q->rear+1) % MaxVertexNum == Q->front){
                printf("Queue is full\n");
                return;
            }
            Q->rear = (Q->rear+1) % MaxVertexNum;
            Q->Data[Q->rear] = item;
        }
    
        int Delete_Queue(Queue Q)
        {
            if(IsEmpty_Queue(Q)){
                printf("Queue is empty\n");
                return -1;
            }
            Q->front = (Q->front+1) % MaxVertexNum;
            return Q->Data[Q->front];
        }
    
        int IsEmpty_Queue(Queue Q)
        {
            if(Q->rear == Q->front)
                return 1;
            else
                return 0;
        }
    
        int Check_Visited(MGraph *G)
        {
            for (int i = 0; i < G->n; i++){
                if (!Visited[i])
                    return 1;
            }
            return 0;
        }
    
        void Reset_Visited()
        {
            for (int i = 0; i < MaxVertexNum; i++)
                Visited[i] = 0;
        }
        
        void Create_MGraph(MGraph *G)
        {
    
            scanf("%d %d", &(G->n), &(G->e));
            for (int i = 0; i < G->n; i++){
                for (int j = 0; j < G->n; j++)
                    G->Edges[i][j] = 0;
            }
            int i, j;
            for (int k = 0; k < G->e; k++){
                scanf("%d %d", &i, &j);
                G->Edges[i][j] = 1;
                G->Edges[j][i] = 1;
            }
        }
    
        void DFS(MGraph *G, int i)
        {
            Visited[i] = 1;
            printf("%d ", i);
            for (int j = 0; j < G->n; j++){
                if(G->Edges[i][j] == 1 && Visited[j] == 0)
                    DFS(G, j);
            }
        }
    
        void BFS(MGraph *G)
        {
            int V, W;
            Queue Q = Create_Queue();
            for (int i = 0; i < G->n; i++){
                if (Visited[i] == 0){
                    printf("{ ");
                    Visited[i] = 1;
                    printf("%d ", i);
                    Add_Queue(Q, i);
                    while(!IsEmpty_Queue(Q)){
                        V = Delete_Queue(Q);
                        for(W = FirstAdjV(G, V); W < G->n; W = NextAdjV(G, V, W)){
                            if(!Visited[W]){
                                //只要此相连有边的节点没被访问过，则如队列
                                Visited[W] = 1;
                                printf("%d ", W);
                                Add_Queue(Q, W);
                            }
                            //如果照完了一遍邻接矩阵都没有相连的没被访问的节点了，就跳出循环
                            else
                                break;
                        }
                    }
                    printf("}");
                    if (Check_Visited(G))
                        printf("\n");
                }
            }
        }
        //无论是FirstAdjV还是NextAdjV都是寻找此时弹出的队列节点的周边相连有边的节点
        int FirstAdjV(MGraph *G, int V)
        {
            for (int i = 0; i < G->n; i++){
                if (G->Edges[V][i] == 1 && Visited[i] == 0)
                    return i;
            }
        }
    
        int NextAdjV(MGraph *G, int V, int W)//不考虑W反而过了
        {
            for (int i = 0; i < G->n; i++){
                if (G->Edges[V][i] == 1 && Visited[i] == 0)
                    return i;
            }
        }

修改后的：

<span style="font-size:12px;">#include <stdio.h>
        #include <stdlib.h>
    
        #define MaxVertexNum 10
    
        int visited[MaxVertexNum];
    
        typedef struct MGraph{
            int VertaxNum;
            int LineNum;
            int Edges[MaxVertexNum][MaxVertexNum];
        }*Graph;
        void DFS(struct MGraph *Graph, int i);
    
        typedef struct Queue{
            int rear;
            int front;
            int Data[100];
        }*QNode;
        void BFS(struct MGraph *Graph);
        void Reset_Visited();
        int Check_Visited(struct MGraph *Graph);
    
        int main(){
            int i;
            int j;
            for(i=0;i<MaxVertexNum;i++){
                visited[i] = 0;
            }
            Graph G;
            scanf("%d %d",&(G->VertaxNum),&(G->LineNum));
            for(i=0;i<G->VertaxNum;i++){
                for(j=0;j<G->VertaxNum;j++)
                    G->Edges[i][j] = 0;
            }
            int x,y;
            for(i=0;i<G->LineNum;i++){
                scanf("%d %d",&x,&y);
                G->Edges[x][y] = 1;
                G->Edges[y][x] = 1;
            }
    
            for(i=0;i<G->VertaxNum;i++){
                for(j=0;j<G->VertaxNum;j++)
                    if(j == (G->VertaxNum - 1))
                        printf("%d \n",G->Edges[i][j]);
                    else
                        printf("%d",G->Edges[i][j]);
            }
    
            for(i=0;i<G->VertaxNum;i++){
                if(visited[i] == 0){
                    printf("{");
                    DFS(G,i);
                    printf("}\n");
                }
            }
    
            Reset_Visited();
    
            BFS(G);
        }
    
        void DFS(struct MGraph *Graph, int i){
            visited[i] = 1;
            printf("%d ",i);
            int j;
            for(j=0;j<Graph->VertaxNum;j++)
                if(Graph->Edges[i][j] && visited[j] == 0)
                    DFS(Graph,j);
        }
    //。。。深度优先搜索
        void BFS(struct MGraph *Graph){
            QNode Q = (QNode)malloc(sizeof(QNode));
            Q->rear = Q->front = 0;
            int i;
            for(i=0;i<Graph->VertaxNum;i++){
                if(visited[i] == 0){
                    printf("{ ");
                    visited[i] = 1;
                    printf("%d ", i);
                    Q->Data[Q->rear] = i;
                    Q->rear = Q->rear + 1;
                    while((Q->rear) - (Q->front)){
                        int node;
                        node = Q->Data[Q->front];
                        Q->front = Q->front + 1;
                        int j;
                        for (j = 0; j < Graph->VertaxNum; j++){
                            if (Graph->Edges[node][j] && visited[j] == 0){
                                visited[j] = 1;
                                printf("%d ", j);
                                Q->Data[Q->rear] = j;
                                Q->rear += 1;
                            }
                        }
                    }
                    printf("}");
                    if (Check_Visited(Graph))
                        printf("\n");
                }
            }
        }
    
        void Reset_Visited(){
            int i;
            for (i = 0; i < MaxVertexNum; i++)
                visited[i] = 0;
        }
    
        int Check_Visited(struct MGraph *Graph)
        {
            int i;
            for (i = 0; i < Graph->VertaxNum; i++){
                if (!visited[i])
                    return 1;
            }
            return 0;
        }
    </span>