c++広さ優先検索
11788 ワード
#include
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[verMax];//
int que[queMax];
int front=-1;
int rear=-1;
int visit[verMax];// //
int enque(int v)
{
if(rear>=queMax)//
return -1;
else
{
rear++;//
que[rear]=v;//
return 1;
}
}
//
int deque()
{
if(front==rear)//
return -1;
else
{
front++;
return que[front];
}
}
//
void BFS(int v)
{
graph point;
enque(v);//
visit[v]=1;//
cout<<"["<"]==>";
while(front!=rear)
{
v=deque();
point=head[v].next;
while(point!=NULL)//
{
if(visit[point->vertex]==0)
{
enque(point->vertex);//
visit[point->vertex]=1;//
cout<<"["<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[v1]);
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<<"["<vertex<<"] ";
point=point->next;
}
cout<<endl;
}
//
void main()
{
int node[20][2]={
{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)
{
head[i].vertex=i;
head[i].next=NULL;
}
for(i=0;i)
visit[i]=0;
for(i=0;i<20;i++)
create_graph(node[i][0],node[i][1]);
cout<<"======Graph======"<<endl;
for(i=1;i)
{
cout<<"Vertex["<"]: ";
print_graph(&head[i]);
}
//
cout<<"Bradth-First-Search:"<"&BEGIN==>";
BFS(4);
cout<<"END&"<<endl;
}