数据结构-图的遍历——广度优先搜索 （C++代码）

解题思路:
        首先要开一个二维数组储存邻接矩阵，一般的方法是开一个足够大的数组，例如这道题是n不大于50,不过这样做会造成空间不必要的浪费。因此手动分配空间会更为合理。一种方法是用malloc，对应销毁空间的函数是free，这种方法适用于C语言和c++。另一种方法是用new，对应销毁空间的方法是delete，注意malloc对应的是free，new对应的是delete，不能搞混。

        主要介绍一下malloc，一维数组开辟空间只需要，int* temp=(int*)malloc(n*sizeof(int))就可以开辟n长度的数组。二维及以上要多几步。例如这道题用于储存邻接矩阵的数组的开辟方法：

int** map=(int**)malloc(vertexNum*sizeof(int));

for(int i=0;i<vertexNum;i++)

map[i]=(int*)malloc(vertexNum*sizeof(int)); 

        第二步是广度优先搜索，需要一个队列和一个判断是否被访问过的bool类型的数组visited，队列每出一个点temp，就遍历temp的邻接点，没有访问过就入队，直到队列为空时就可以停止了。

参考代码:

#include<cstdio>

#include<queue>

#include<malloc.h>

using std::queue;

void initialize(int vertexNum,int** &map){

    map=(int**)malloc(vertexNum*sizeof(int));

    for(int i=0;i<vertexNum;i++)

        map[i]=(int*)malloc(vertexNum*sizeof(int)); 

    for(int i=0;i<vertexNum;i++)

        for(int j=0;j<vertexNum;j++)

            scanf("%d",&map[i][j]);

}

void BFS(int vertexNum,int** map){

    queue<int> Q;

    bool* visited=(bool*)malloc(vertexNum*sizeof(bool));

    for(int i=1;i<vertexNum;i++)

        visited[i]=false;

    visited[0]=true;

    Q.push(0);

    while(!Q.empty()){

        int temp=Q.front();

        printf("%d ",temp);

        Q.pop();

        for(int i=0;i<vertexNum;i++){

            if(map[temp][i]!=0&&visited[i]==false){

            Q.push(i);

            visited[i]=true;

        }

    }

}

}

int main(){

    int** map=NULL;

    int vertexNum;

    scanf("%d",&vertexNum);

    initialize(vertexNum,map);

    BFS(vertexNum,map);

    return 0;

}