广度优先搜索BFS 之图的构造及遍历

1. 由给定的顶点和边的信息构造图的邻接矩阵存储； 对该图进行深度优先搜索，输出搜索得到的结点序列；

3. 以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树。

/*5 6abcde0 1 100 3 201 2 301 4 402 3 502 4 60*/ #include<iostream>#include<cstdio>#include<queue>#include<cstring>usingnamespace std;#definemaxn 100#defineINF 999999#defineMAXVEX 100typedefstruct {    char vexs[MAXVEX];    double arcs[MAXVEX][MAXVEX];    int n,e;}mGraph; queue<char>qu;intflag[maxn]; voidcreateAdjMatrix(mGraph *G){    int i,j,k;    double w;    PRintf("请输入图的节点数和边数：/n");   scanf("%d%d",&G->n,&G->e);    getchar();    for(i=0;i<G->n;i++) flag[i]=0;    printf("请输入图的节点：/n");    for(k=0;k<G->n;k++)scanf("%c",&G->vexs[k]);    for(i=0;i<G->n;i++)        for(j=0;j<G->n;j++)            G->arcs[i][j]=INF;    printf("请输入图的边以及边的权：/n");    for(k=0;k<G->e;k++)    {       scanf("%d%d%lf",&i,&j,&w);        G->arcs[i][j]=w;        G->arcs[j][i]=w;    }} voidbfs(mGraph *G){    int num=0;    for(int i=0;i<G->n;i++) flag[i]=0;    for(int i=0; i<G->n; i++)        if(flag[i]==0)        {            flag[i]=1;            qu.push(G->vexs[i]);            while(!qu.empty())            {                char ss=qu.front();                qu.pop();                if(num==G->n-1)                    cout<<ss<<endl;                else                    cout<<ss<<"";                num++;                for(int j=0; j<G->n; j++)                    if(G->arcs[i][j]<INF&& flag[j]==0)                    {                           qu.push(G->vexs[j]); flag[j]=1;                    }            }        }} intmain(){    mGraph m;    createAdjMatrix(&m);    printf("遍历序列如下：/n");    bfs(&m);    return 0;}