广度优先搜索

广度优先搜索

//  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;
 }

posted on 2006-12-17 11:32 snowhill 阅读(791) 评论(0)  编辑 收藏 引用 所属分类: data structure


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2006年12月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

公告

又一年...........

留言簿(3)

随笔分类(13)

文章分类(131)

文章档案(124)

c++

java

linux

oracle

常用软件

其他

网络配置

系统安全

音乐

搜索

最新评论

阅读排行榜