Is it possible to implement width-first search using recursive functions without using queues?

Question

Is it possible to implement width-first search for graph structures using recursive functions?

For depth-first exploration, you can implement it using a stack or recursive function.
On the other hand, in the case of depth-first search, we could have implemented it using a queue, but we are having trouble implementing it using a recursive function without using a queue.

For your information, I have listed the queue-based implementation below.I would appreciate it if you could give me a hint or an implementation for width-first search.
I think that they probably define functions that visit u such as bfs_visit(intu) and use them as recursive functions.However, unlike depth-first search, I don't know how to implement the logic that makes width-first.

Reference

You are trying to solve this problem with a width-first search with a recursive function.If you use a queue, use the source code below without any problems.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp

Implementing width-first search using queues

(Scroll as it is long)

#include<iostream>
# include <queue>
#define NIL-1
#define N110

using namespace std;

bool A[N][N];
intd[N];
intn;

void bfs(ints) {
  queue<int>q;
  for(inti=0;i<N;i++)d[i]=NIL;
  q.push(s);
  d[s] = 0;
  while(!q.empty()){
    intu = q.front(); q.pop();
    for(intv=0;v<n;v++){
      if(A[u][v]&d[v]==NIL){
        q.push(v);
        d[v] = d[u]+1;
      }
    }
  }
}

int main() {

  cin>>n;
  for(inti=0;i<n;i++){
    for(int j=0;j<n;j++){
      A[i][j]=false;
    }
  }

  for(inti=0;i<n;i++){
    intu,k,v;
    cin>>u>>k;
    u--;
    for(int j=0;j<k;j++){
      cin>>v;
      v--;
      A[u][v]=true;
    }
  }

  bfs(0);

  for(inti=0;i<n;i++){
    cout<<i+1<<"<d[i]<endl;
  }
}

c++ c algorithm graph-theory

2022-09-30 14:42

3 Answers

A simple loop can be easily rewritten to recursive processing, so it's not impossible.Apart from whether it's natural or easy to understand.

void fn(int start, int end){
    for(inti=start;i<end;++i){
        cout<<i<<endl;
    }
}

void fr(inti, intend){
    if(i>=end)return;
    cout<<i<<endl;
    fr(i+1,end);
}

fn(0,10) and fr(0,10) behave the same way (if you ignore the depth of stack consumption).

The subject is not to use a queue, so here I wrote that vector keeps a list of vertices that can be reached at a distance of n.

If you use the data expression used in your code as much as possible, it will look like this.

#include<iostream>
# include <vector>
#define NIL-1
#define N110

using namespace std;

bool A[N][N];
intd[N];
intn;

void rbfs(constector<int>&curr){
    vector<int>next;
    for(inti=0;i<curr.size();++i){
        intu=curr[i];
        for(intv=0;v<n;++v){
            if(A[u][v]&d[v]==NIL){
                next.push_back(v);
                d[v] = d[u]+1;
            }
        }
    }
    if(!next.empty(){
        rbfs(next);
    }
}

int main() {
    cin>>n;
    for(inti=0;i<n;++i){
        for(int j=0;j<n;++j){
            A[i][j]=false;
        }
    }

    for(inti=0;i<n;++i){
        intu,k,v;
        cin>>u>>k;
        u--;
        for(int j=0;j<k;++j){
            cin>>v;
            v--;
            A[u][v]=true;
        }
    }

    for(inti=0;i<N;++i)d[i]=NIL;
    constints = 0;
    d[s] = 0;
    vector<int>start;
    start.push_back(s);
    rbfs(start);

    for(inti=0;i<n;++i){
        cout<<i+1<<"<d[i]<endl;
    }
}

(If you have a parameter that represents the depth of the recursive, it is supposed to be a distance, but here we try to write it closer to the original structure.Other minor corrections are my hobby, so it has nothing to do with the essence.)

However, this part:

for(intv=0;v<n;++v){
            if(A[u][v]&d[v]==NIL){
                next.push_back(v);
                d[v] = d[u]+1;
            }
        }

It's not efficient to lick all the vertices in the graph to find the vertex v that you can reach from the vertex u.Expressing directed graphs in the V×V→Bool matrix may be useful for theoretical handling, but it is not suitable for this kind of exploration problem.

Data structures close to the original input data can be faster.

#include<iostream>
# include <vector>
#define NIL-1
#define N110

using namespace std;

vector<vector<int>>Arcs;
intd[N];
intn;

void rbfs2(constector<int>&curr){
    vector<int>next;
    for(inti=0;i<curr.size();++i){
        intu=curr[i];
        for(int j=0;j<Arcs[u].size();++j){
            intv=Arcs[u][j];
            if(d[v]==NIL){
                next.push_back(v);
                d[v] = d[u]+1;
            }
        }
    }
    if(!next.empty(){
        rbfs2(next);
    }
}

int main() {
    cin>>n;
    Arcs.resize(n);

    for(inti=0;i<n;++i){
        intu,k,v;
        cin>>u>>k;
        for(int j=0;j<k;++j){
            cin>>v;
            Arcs [u-1].push_back(v-1);
        }
    }

    for(inti=0;i<N;++i)d[i]=NIL;
    constints = 0;
    d[s] = 0;
    vector<int>start;
    start.push_back(s);
    rbfs2 (start);

    for(inti=0;i<n;++i){
        cout<<i+1<<"<d[i]<endl;
    }
}

I've just checked the operation briefly, but if you notice anything, please let me know.

2022-09-30 14:42

It can be solved by stack and recursive functions, even if it is not a queue.The problem itself is not difficult.

Because functions are implemented in a stack mechanism, recursive functions replace the stack.However, loops are often compared with recursive functions.(Without a trailing recursive optimization mechanism) Recursive functions use loops because they stack overflow when the nest is deep.The recursive function is suitable for exploring tree structures.

#include<iostream>
# include <stack>
#define NIL-1
#define N110

using namespace std;

bool A[N+1][N+1];
intd[N+1];
intn;

stack<int>s1;
stack<int>s2;

void bfs(int depth, stack<int>si, stack<int>so){
  if(si.empty()) return;
  while(!si.empty()){
    intu=si.top();
    si.pop();
    for(intv=1;v<=n;v++){
      if(A[u][v]&d[v]==NIL){
        so.push(v);
        d[v] = depth;
      }
    }
  }
  bfs(depth+1,so,si);
}

int main() {

  cin>>n;
  for(inti=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      A[i][j]=false;
    }
  }

  for(inti=1;i<=n;i++){
    intu,k,v;
    cin>>u>>k;
    for(int j=1;j<=k;j++){
      cin>>v;
      A[u][v]=true;
    }
  }

  for(inti=1;i<=N;i++)d[i]=NIL;
  s1.push(1);
  d[1] = 0;
  bfs(1,s1,s2);

  for(inti=1;i<=n;i++){
    cout<<i<"<d[i]<endl;
  }
}

2022-09-30 14:42

The width-first search requires finding the sibling of the node you are currently visiting, but you cannot see the sibling node directly from one node, so you will need some auxiliary data structure to rewrite with a recursive function.This will be a queue considering efficiency.

However, if efficiency is acceptable:In other words, you can add the depth of the node you are interested in as a parameter for the DFS function and increase it by one for each loop.In other words, when you decide on a certain depth, you decide whether you can get there by the depth step.This is not strictly a width-first search, but it does the equivalent.

By the way, after implementing this as it is, it became TLE, so I try not to waste node search with the code below.

// True if a new node is found
boole dfs(intu, intlv, int depth) {
  // make no useless search for
  if(d[u]>=0&d[u]<lv)return false;
  if(lv==depth){
    if(d[u]==NIL){
      d[u] = depth;
      return true;
    }
    return false;
  }
  else{
    booolr=false;
    for (int v=0; v<n;v++)
      if(A[u][v])r | = dfs(v,lv+1,depth);
    return;
  }
}

Replace the bfs(0); portion of the main function with the following:

 for (inti=0;i<N;i++)d[i]=NIL;
int depth = 0;
while(dfs(0,0, depth)) depth++;

The efficiency is inferior to that of using a queue because you will visit a shallow node many times.

2022-09-30 14:42

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656