BFS - 廣度優先搜尋 - 鄰接清單表示法

2017-07-25 21:40:22

writer：pprp

在DFS的基礎上加上了一個BFS函數

#include <iostream>
#include <queue>

using namespace std;

const int N = 9;

queue<int> qu;

int visited[N] = {0};    //新引入一個數組，用于标記是否通路過

struct node
{
    int vertex;
    node*next;
};

node head[N];

void BFS(int vertex)              // 寬度優先搜素
{
      node*point;
      qu.push(vertex);
      visited[vertex] = 1;
      cout<< vertex <<"->";
      while(!qu.empty())
      {
            vertex = qu.front();
            qu.pop();
            point = head[vertex].next;
            while(point!=NULL)
            {
                  if(visited[point->vertex] == 0)
                  {
                        qu.push(point->vertex);
                        visited[point->vertex] = 1;
                        cout <<point->vertex<<"->";
                  }
                  point = point->next;
            }
      }
}

void create(int val1,int val2)
{
    node*point;
    node*nnew = new node();
    nnew->vertex = val2;
    nnew->next = NULL;
    point = &head[val1];
    while(point->next!=NULL)
    {
        point = point->next;
    }
    point->next = nnew;
}


void print()
{
    node*point;
    for(int i = 0; i < N; i++)
    {
        point = head[i].next;
        cout << "Head["<<i<<"]";
        while(point!=NULL)
        {
            cout <<"-> "<<point->vertex;
            point = point->next;
        }
        cout << endl;
    }
}

int main()
{
    int node1,node2;
    
    for(int i = 0; i < N; i++)
    {
        head[i].vertex = i;
        head[i].next = NULL;
    }
    while(1)
    {
        cout <<"please enter the start point" << endl;

        cin >> node1;
        if(node1 == -1)
            break;
        cout <<"please enter the end point" << endl;
        cin >> node2;

        if(node1 == node2)
            cout <<"自身循環"<<endl;
        else if(node1>=N||node2>=N)
            cout <<"超出範圍"<<endl;
        else
            create(node1,node2);
    }

    cout << "鄰接表為：" << endl;
    print();
    

    
    cout <<"\n"<<endl;
    
    cout <<"BFS: "<<endl;
    
    BFS(1);

    return 0;
}      

代碼改變世界