l7_5.cpp

《数据结构（C++描述）》-李根强-源代码

//用邻接矩阵实现无向图的广度优先搜索遍历
#include<iostream.h>
const  int  n=8;                    // 图中顶点数  
const  int  e=10;
typedef int elemtype;                    // 图中边数
struct    graph
{  
elemtype       v[n+1];                  // 存放顶点信息v1,v2,….vn，不使用v[0]存储空间
int    arcs[n+1][n+1];             // 邻接矩阵
};

graph  g;
int visited[n+1];
void  creatadj( )
{ int i,j,k ;
  cout<<"请输入顶点信息"<<endl;
  for  (k=1; k<=n; k++)
  cin>>g.v[k];                            //输入顶点信息   
for (i=1; i<=n;  i++ )
  for (j=1; j<=n; j++)
   g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{    cout<<"请输入一条边";
	cin>>i>>j;                             //输入一条边(i,j)           
    cout<<endl;
	g.arcs[i][j]=1;
    g.arcs[j][i]=1;
}
}
void  bfs( int i)       //从顶点I出发遍历
{ int  q[n+1] ;         //Q为队列
  int  f,r,j ;           // f,r分别为队列头，尾指针
  f=r=0 ;             //设置空队列
 cout<<g.v[i]<<"  " ;        // 输出访问顶点
 visited[i]=1 ;         //全局数组标记置1表示已经访问
 r++; q[r]=i ;          //入队列
 while (f<r)
  { f++; i=q[f] ;       //出队列
for (j=1; j<=n; j++)
 if ((g.arcs[i][j]==1)&&(!visited[j]))
  {  cout<<g.v[j]<<"  " ;
     visited[j]=1 ;
     r++; q[r]=j ;
}
 }
}
void main( )
{  int i,j;
    for(i=1;i<=n;i++)
		visited[i]=0;
	creatadj( );
	for(i=1;i<=n;i++)
	{for(j=1;j<=n;j++)
			cout<<g.arcs[i][j]<<"  ";
	cout<<endl;
	}
	cout<<"请输入开始访问的顶点";
	cin>>i;
	cout<<endl;
	cout<<"从"<<i<<"出发的广度优先搜索遍历序列为"<<endl;
	bfs(i);
    cout<<endl;
}