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