Breadth First Search

题目描述
Breadth-first search (BFS) is a strategy for searching in a graph. You are given a graph with N nodes, a starting node S and an ending node T. You are required to answer whether there exists a path from S to T.

输入描述
The first line of a test case is an integer N (N<=100), S and T (0<=S,T<N).
The next N lines, each line contains N binary numbers. If the i-th row and j-th column is 1, node i is connected with node j.
Otherwise, there is no edge between i and j.

输出描述
Output “yes” if there exists a path from S to T. Otherwise, output “no”.

样例输入
5 0 3

1 1 0 0 0

1 1 0 0 1

0 0 1 0 0

0 0 0 1 1

0 1 0 1 1

样例输出
yes

ZHC的答案

//广度优先
#include<iostream>
using namespace std;
#include<ctime>

int main(){
//    double startTime1 = clock(); //1计时开始
    int num, start, end ;    //元素个数，起点，终点
    cin >> num >> start >> end ;
    int a[num][num];
    for(int i = 0 ; i <num ; ++i){ //记录邻接矩阵
        for(int j = 0 ; j<num ; ++j){
            cin>>a[i][j] ;
        }
    }

    int able[num];
    for(int i = 0 ; i < num ; ++i){
        if( a[start][i]==1 )  able[i]=1;
        else  able[i] = 0 ;
    }

    int add = 1 ;
    while(add==1 ){//当有新增可达点时循环继续,最多n-1次
        add = 0 ;
        for(int i = 0 ; i < num ; ++i){ //逐点遍历，n次
          if(able[i]==1 && i!=start){ //未遍历的点进行遍历，总和最多为n-2
                for(int j = 0 ; j < num ; ++j){ // n次
                    if(a[i][j] ==1 && able[j]== 0){ 
                        able[j] =1 ;
                        add = 1 ;//确认有新增可达点j
                      }
                    if(able[end]>=1) break;
                    }
                able[i]+=1; //记录为已遍历过的点
                }
            if(able[end]>=1) break; 
            }
        if(able[end]>=1) break;
        }

    if(able[end] >= 1) cout<<"yes" ;
    else cout<<"no" ;
//    double endTime1 = clock();//1计时结束
//   cout <<endl<< "The run time is: " <<(double)(endTime1 - startTime1)/CLOCKS_PER_SEC << "s" << std::endl;

    return 0 ;
}

Yizuodi的答案

#include <iostream>
#include <stack>
using namespace std;

class Queue
{
public:
    stack<int> a, b;

    void push(int number)
    {
        a.push(number);
    }

    int pop()
    {
        if (!b.empty())
        {
            int tmp = b.top();
            b.pop();
            return tmp;
        }
        else if (!a.empty())
        {
            while (!a.empty())
            {
                b.push(a.top());
                a.pop();
            }
            int tmp = b.top();
            b.pop();
            return tmp;
        }
        else
        {
            return -1;
        }
    }

    int count() const
    {
        return a.size() + b.size();
    }
};

int main()
{
    Queue Q;
    stack<int> V;
    int num, begin, end;
    int code = 0;
    cin >> num >> begin >> end;

    int matrix[num][num]; //邻接矩阵
    int visited[num];
    for (int i = 0; i < num; ++i)
        for (int j = 0; j < num; ++j)
            cin >> matrix[i][j];

    Q.push(begin);

    while (Q.count() != 0)
    {
        int id = Q.pop();
        if (matrix[id][end])
        {
            code = 1;
            break;
        }
        for (int i = 0; i < num; i++)
        {
            if ((matrix[id][i] == 1) && (visited[i] != 1))
            {
                Q.push(i);
                visited[i] = 1;
            }
        }
    }
    if (code)
    {
        cout << "yes";
    }
    else
    {
        cout << "no";
    }
}

ZHC的答案2

//广度优先队列升级版
#include<iostream>
using namespace std;
class Queue{
private:
    int data[100];//记录新增可达点
    int front;//记录队首位置
    int rear; //记录队尾的后一个空位置
    int count;
public:
    int able[20] = {0};   /*记录所有可达点, able[i]==0时表示i不可达，
able[i]==1时表示i为新增的可达点，able[i]>1时表示i为已遍历过的可达点*/
      Queue(){
        rear = 0 ;
        front = 0;
        count = 0 ;
    }
    void push(int t){ //队尾入队
        data[rear]=t;//rear记录队尾的后一个空位置
        ++rear;
        if(rear==100) rear = 0  ;
           ++count;
    }
    int size()const {
       return count ;
    }
      bool empty(){
        if(count==0)  return true ;
        else return false ;
    }
    int getfront(){
        return data[front];
    }
    void pop(){ //队首出队
        if( count > 0)  ++front ;
        if(front==100) front = 0  ;
        --count;
    }
};
int main(){
    int num, start, end ;    //点的个数，起点，终点
    cin >> num >> start >> end ;
    int a[num][num];
    for(int i = 0 ; i <num ; ++i){ //记录邻接矩阵
        for(int j = 0 ; j<num ; ++j){
            cin>>a[i][j] ;
        }
    }
    Queue  A; //用队列储存新增可达点
    A.push(start);
    while(!A.empty()){//当有新增可达点时循环继续
        int k=A.size();
        for(int i = 0 ; i < k ; ++i){ //对可达点进行遍历
            int t=A.getfront();
            A.pop(); //遍历过的可达点出队
            A.able[t]+=1;//并记录为已遍历
            for(int j = 0 ; j < num ; ++j){ 
                if(a[t][j] ==1 && A.able[j]== 0){ 
                    A.able[j] =1 ;
                    A.push(j);//确认有新增可达点j并入队
                }
                if(A.able[end]>=1) break;
            }
            if(A.able[end]>=1) break;
        }
        if(A.able[end]>=1) break; 
    }
    
    if(A.able[end] >= 1) cout<<"yes" ;
    else cout<<"no" ;
    return 0 ;
}