图的广度优先遍历问题求教

该程序运用邻接矩阵创建图,运行后没有出现图的广度优先遍历的结果的打印。。。请大神帮忙看看我写的广度优先遍历算法哪里出现了问题,万分感激!

        #include "stdafx.h"
        #include <iostream.h>
        #include <conio.h>
        #include <stdio.h>
        #include <queue>
        using namespace std;

        void EnQueue_Sq( queue<int> &Q , int v )
        {
        Q.push( v );
        }
        int DeQueue_SQ( queue<int> &Q )
        {
        int i = Q.front();
        Q.pop();
        return i;
        }
        //1、邻接矩阵
        #define VexType char
        #define EdgeType int
        #define INFINITY INT_MAX     // 最大值∞
        #define Max_Vertex_Num  10   // 最大顶点个数
        bool visited[ Max_Vertex_Num ];//辅助数组--遍历使用
        struct MGraph{
        VexType vexs[ Max_Vertex_Num ];    //顶点数组
        EdgeType edges[ Max_Vertex_Num ][ Max_Vertex_Num ];//邻接矩阵
        int vexnum;      //当前顶点数
        int edgenum;     //当前边数
        //GraphKind  kind;//图的种类标志,本练习假定图为无向带权图(即 无向网)
        };

        void DSF_MG( const MGraph &G , int v );
        void BFS_MG( const MGraph &G , int v );
        /////////////////////////////算法实现/////////////////////////////////////
        //一、邻接矩阵操作的实现
        //1、 创建图
        void CreateGraph_MG( MGraph &G )//构造一个具有n个顶点,e条边的无向网(注意:输入必须准确,算法中没有判断非法输入!)
        {
        cout<<"请分别输入顶点数目和边的数目:";
        cin>>G.vexnum>>G.edgenum;
        int n = G.vexnum;
        int e = G.edgenum;
        int i , j;
        for (i = 0 ; i < n ; i ++ )
        {
            cout<<"请输入第"<<i<<"个顶点的信息:";
            cin>>G.vexs[ i ];
        }
        //初始化邻接矩阵
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
            {
            G.edges[i][j] = INFINITY;
            }
        for ( i = 0 ; i < e ; i ++ )
        {
            int beginNode , endNode;
            cout<<"请输入第"<<i<<"条边的第一个顶点的编号(从0开始):";
            cin>>beginNode;
            cout<<"请输入第"<<i<<"条边的第二个顶点的编号(从0开始):";
            cin>>endNode;
            cout<<"请输入第"<<i<<"条边的权值(注意为非0值):";
            cin>>G.edges[beginNode][endNode];
            G.edges[endNode][beginNode] = G.edges[beginNode][endNode];
        }
        //输出图的信息
        cout<<"输入完毕!"<<endl;
        cout<<"顶点数组:[";
        for (i = 0 ; i < n ; i ++ )
        {
            cout<<G.vexs[ i ]<<" ";
        }
        cout<<"]"<<endl;
        cout<<"邻接矩阵:"<<endl;
        for ( i = 0 ; i < n ; i ++ )
        {
            for ( j = 0 ; j < n ; j ++ )
            {
            if( G.edges[ i ][ j ] != INFINITY )
                printf( "%5d" , G.edges[i][j] );
            else
                printf( "%5c" , '-');
            //cout<<G.edges[i][j]<<"  ";
            }
            //cout<<endl;
            printf( "\n" );
        }
        }
        //2、求邻接结点及其度
        void Dsp_ArjNodes_MG( const MGraph &G , int v )//输出第v个顶点的所有邻接点信息以及该结点的度(注意i不在取值范围内应提示错误信息)
        {
        if(v>=G.vexnum) cout<<"ERROR"<<endl;
        int count = 0;
        for(int i=0;i<G.vexnum;i++)
        {
            if(G.edges[v-1][i]!=INFINITY){
                cout<<"临界结点有"<<i<<endl;
            count++;
            }
        }
        cout<<"该点的度为"<<count<<endl;



        }
        //3、找邻接点
        int FirstAdjVex( const MGraph &G , int v )//找到顶点v(v为顶点的index)的第一个邻接点并返回该邻接点的index,如果不存在邻接点,则返回-1
        {
            int j,p=-1,found=1;
            for(j=0;((j<G.vexnum)&&(found==1));j++)
                if(G.edges[v][j]!=INFINITY)
                {
                    p=j;
                    found=0;
                }
            return p;

        }
        //4、找下一个邻接点
        int NextAdjVex( const MGraph &G , int v , int w )//v是G的某个顶点,w是v的一个邻接点,返回v(相对于w)的下一个邻接点(邻接点的index),如果w已经是最后一个邻接点,则返回-1
        {
            int j,p=-1,found=1;
            for(j=w+1;((j<G.vexnum)&&(found==1));j++)
                if(G.edges[v][j]!=INFINITY)
                {
                    p=j;
                    found=0;
                }
                return p;

        }

        //5、广度优先遍历(主调)--例子
        void BFSTraverse_MG( const MGraph &G )//广度优先遍历图
        {
        int v;
                for (v=0; v<G.vexnum; ++v)
            visited[v] = false;  //初始化访问标志
        //开始遍历过程:
                for ( v=0;  v<G.vexnum;  ++v )
            if ( !visited[v])
                BFS_MG( G , v );
        }

        //6、以v为起点广度优先遍历(核心函数)
        void BFS_MG( const MGraph &G , int v )//以v为起点进行广度优先遍历
        {
        queue<int> Q;//定义完队列Q(不需要执行InitQueue_SQ)
        EnQueue_Sq(Q, v);  // v入队列 
        visited[v] = true;  
        cout<<G.vexs[v]<<"  ";
        while(!Q.empty ())  {
            int s = DeQueue_SQ( Q );// 队头元素出队
            for(int w=FirstAdjVex(G,s);w!=INFINITY;w=NextAdjVex(G,s,w)) 
            if ( !visited[w] )  {
                visited[w]=true; 
                cout<<G.vexs[w]<<"  ";
                EnQueue_Sq(Q, w); // 访问的顶点w入队列
            } // if 

        }//while

        }

        void main()
        {
            MGraph MG;
            CreateGraph_MG( MG );
            // 打印顶点a的所有邻接点
            Dsp_ArjNodes_MG( MG ,3);
            cout<<"输出广度优先遍历结果:"<<endl;
            BFSTraverse_MG( MG );
            getch();
        }

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!