广度优先搜索
#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;
}