#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MaxSize 50

//邻接矩阵
void BFS(MGraph G,int v,int *visited){

    int queue[MaxSize],front = -1,rear = -1;    //空间:O(n)
    queue[++rear] = v;
    visited[v] = 1;
    printf("%d",G.vex[v]);
    while(front != rear){    //当队列不为空时
        v = queue[+//找不是联通的点//找不是联通的点//找不是联通的点//找不是联通的点+front];    //取队头,将v出队
        for(int i = 0;i < G.vexnum;i++){    //时间:O(|v|)
            if(G.edge[v][i]!=0 && visited[i]==0){
                queue[++rear] = v;
                visited[i] = 1;
                printf("%c",G.vex[i]);
            }    
        }
    }
}        //时间:O(|v|)
         //空间:O(n)

void BFSTravelers(MGraph G){
    int visited[MaxSize];            //空间:O(n)
    //int *visited = (int*)malloc(sizeof(G.vexnum));
    //这里也可以直接动态申请
    for(int i=0;i < G.vexnum;i++){    //时间:O(|v|)
        visited[i] = 0;    //初始化
    }
    for(int i = 0;i < G.vexnum;i++){    //时间:O(|v|)
        if(visited[i] == 0){
            BFS(G,i,visited);        //时间:O(|v|)
                                     //空间:O(n)
        }
    }        //时间:O(|v|^2)
             //空间:O(2n)~O(n)

}            //时间:O(|v|^2)
             //空间:O(2n)~O(n)


//邻接表

void BFS(AdGraph G,int v,int *visited){
    int queue[MaxSize],front = -1,rear = -1    //空间:O(n)
    queue[++rear] = v;
    visited[v] = 1;
    printf("%c",G.vertices[p->adjvex].value);
    while(front != rear){     //当队列不为空
        v = queue[++front];    //取队头,将v出队
        ArcNode *p = G.vertices[v].first;
        while(p != NULL){                //时间:O(|E|)
            queue[++rear] = p->adjvex;
            visited[p->adjvex] = i;
            printf("%c",G.vertices[p->adjvex].value);
        }
        p = p->next;
    }
}            //空间:O(n)
             //时间:O(E)

void BFSTraveler(AdGraph G){
    int visited[MaxSize];        //空间:O(n)
    for(int i = 0;i < G.vexnum;i++){    //时间:O(|v|)
        visited[i] = 0;    //初始化
    }
    for(int i = 0;i < G.vexnum;i++){  //为了找不联通的点O(|v|)
        if(visited[i] == 0){    //从未被访问过
                             //找到了:1.不连通的点
                             //       2.从未被访问过
                             //就开始进行 广度优先BFS 遍历
                             //将与v连通的点全部遍历
                             //然后再找不连通的点
            BFS(G,i,visited);    //时间:O(|E|)
        }
    }        //时间:O(|v|+|E|)
             //空间:O(2n) ~ O(n)

}            //时间:O(|v|+|E|)
             //空间:O(2n) ~ O(n)

//总结:
//1.邻接矩阵:1.空间复杂度:O(n)
//          2.时间复杂度:O(|V|^2)
//2.邻接表:1.空间复杂度:O(n)
//         2.时间复杂度:O(|v|+|E|)

更多推荐