//  date:2006-12-15 by:snowhill
#include  " iostream.h "
#define    elemtype int
#define    MAX_VERTEX_NUM   20          // 最大顶点数   
#define    MAX_EDGE_NUM   40            // 最大边数   
int    visited[MAX_VERTEX_NUM];        // 访问标志数组
struct  ArcNode{
     int  adjvex;
    ArcNode  * NextArc;
};
struct  VNode{
    elemtype data;
    ArcNode  * firstArc;
};
typedef VNode AdjList[MAX_VERTEX_NUM]; 
struct  ALGraph
{
    AdjList vertices;
     int  vexnum,arcnum;
};
ALGraph G;
    
void  CreateDG(ALGraph  & G)
{
     int  i,j,k;
    ArcNode  * p;
    cout << " 创建一个有向图: " << endl;
    cout << " 请输入顶点数: "  ;    cin >> G.vexnum; cout << endl;
    cout << " 请输入边数: " ;     cin >> G.arcnum; cout << endl;
    
     for (i = 1 ;i <= G.vexnum;i ++ )
    {
     G.vertices[i].data = i;
     G.vertices[i].firstArc = NULL;
     }
     for (k = 1 ;k <= G.arcnum;k ++ )
    {
    cout << " 请输入第 " << k << " 条边: " << endl;
    cin >> i >> j;
    p = new  ArcNode;
    p -> adjvex = j;
    p -> NextArc = G.vertices[i].firstArc;
    G.vertices[i].firstArc = p;
    }
}
void  disp(ALGraph G)
{
     int  i;
    ArcNode  * p;
    cout << " 建立的图为: " << endl;
     for (i = 1 ;i <= G.vexnum;i ++ )
        {
        p = G.vertices[i].firstArc;
         while (p != NULL)
            {
            cout << " ( " << i << " , " << p -> adjvex << " ) " ; 
            p = p -> NextArc;
            }
        cout << endl;
    }
    cout << " ******************************* " << endl;
}
void  bfs( int  v)
{
  ArcNode  * p;
   int  queue[MAX_VERTEX_NUM];
   int  front = 0 ,rear = 0 ,w;
   for ( int  i = 0 ;i <= MAX_VERTEX_NUM;i ++ )
    visited[i] = 0 ;
  cout << v;
  visited[v] = 1 ;
  rear = (rear + 1 ) % MAX_VERTEX_NUM;
  queue[rear] = v;
   while (front != rear)
    {
        front = (front + 1 ) % MAX_VERTEX_NUM;
        w = queue[front];
        p = G.vertices[w].firstArc;
         while (p != NULL)
            {
             if (visited[p -> adjvex] == 0 )
                {visited[p -> adjvex] = 1 ;
                 cout << p -> adjvex;
                 rear = (rear + 1 ) % MAX_VERTEX_NUM;
                 queue[rear] = p -> adjvex;
                 }
            p = p -> NextArc;
        }
    }
}
    
void  main()
{
  int  v;
 CreateDG(G);
 disp(G);
 cout << " 请输入广度优先遍历的顶点: " ;
 cin >> v;  cout << endl;
 cout << " 广度优先遍历为: " << endl;
 bfs(v);  cout << endl;
 }