该程序运用邻接矩阵创建图,运行后没有出现图的广度优先遍历的结果的打印。。。请大神帮忙看看我写的广度优先遍历算法哪里出现了问题,万分感激!
#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();
}