广度优先搜索
算法过程：1.将根节点放入队列中2.从队列中取出第一个元素，将队列中的第一个元素弹出3.将所取得元素的全部节点加入队列中4.判断队列是否为空 a. 若是，则结束 b.若不是，则跳到第二步#include <iostream>using namespace std;
const int verMax=9;
const int queMax=10; // >=9皆可
struct node//声明图形顶点结构
{
int vertex;
struct node *next;
};
typedef struct node *graph;
struct node head;//声明顶点结构数组
int que;
int front=-1;
int rear=-1;
int visit;//查找记录//队列的存入
int enque(int v)
{
if(rear>=queMax)//队列已满
return -1;
else
{
rear++;//对了尾端指针后移
que=v;//将值存入队列中
return 1;
}
}
//队列的取出
int deque()
{
if(front==rear)//队列已空
return -1;
else
{
front++;
return que;
}
}
//广度优先搜索法
void BFS(int v)
{
graph point;
enque(v);//存入队列
visit=1;//已查找
cout<<"["<<v<<"]==>";
while(front!=rear)
{
v=deque();
point=head.next;
while(point!=NULL)//读入邻接列表所有顶点
{
if(visit==0)
{
enque(point->vertex);//存入队列
visit=1;//已查找过的顶点
cout<<"["<<point->vertex<<"]==>";
}
point=point->next;
}
}
}
//建立邻接顶点至邻接列表内
void create_graph(int v1,int v2)
{
graph point,New;
New=(graph)malloc(sizeof(struct node));
if(New!=NULL)
{
New->vertex=v2;//邻近顶点
New->next=NULL;
point=&(head);
while(point->next!=NULL)
point=point->next;
point->next=New;//串连在列表尾端
}
}
//输出邻接列表内数据
void print_graph(struct node *head)
{
graph point;
point=head->next;//设置point为首节点
while(point!=NULL)
{
cout<<"["<<point->vertex<<"] ";
point=point->next;
}
cout<<endl;
}
//主程序
void main()
{
int node={
{1,2},{2,1},{1,3},{3,1},{2,4},{4,2},{2,5},{5,2},{3,6},{6,3},
{3,7},{7,3},{4,8},{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},{8,7}};
int i;
for(i=0;i<verMax;i++)
{
head.vertex=i;
head.next=NULL;
}
for(i=0;i<verMax;i++)
visit=0;
for(i=0;i<20;i++)
create_graph(node,node);
cout<<"======Graph======"<<endl;
for(i=1;i<verMax;i++)
{
cout<<"Vertex["<<i<<"]: ";
print_graph(&head);
}
//广度优先搜索
cout<<"Bradth-First-Search:"<<endl<<"&BEGIN==>";
BFS(4);
cout<<"END&"<<endl;
}
页:
[1]