圖形中節點的跟蹤級別以及每個節點的打印級別

Question

我想使用BFS算法遍歷圖並希望按其級別跟蹤節點。 這是我的代碼。

#include<iostream> 
#include<queue> 
#include<vector> 
#include<stdlib.h> 
using namespace std; 
int main() 
{ 
    int edges,a,b; 
    vector<int>nodes[1000]; 
    cout<<"Enter the no of edges"<<endl; 
    cin>>edges; 
    for(int i=0; i<edges; i++) 
    { 
     cin>>a>>b; 
     nodes[a].push_back(b); 
     nodes[b].push_back(a); 
    } 

    cout<<endl; 
    queue<int> que; 
//initially que is empty 
    bool visited[1000]; 
    int level[1000]; 
// mark all the vertices as not visited 
    for(int i=0; i<1000; i++) 
    { 
     visited[i]=false; 
    } 
    int start; 
    cout<<"\nEnter the starting node"<<endl; 
    cin>>start; 

//insert the starting node into the queue 
    que.push(start); 
    level[start]=1; 
//mark the starting node as visited 
    visited[start]=true; 


    cout<<"\nBFS Traversal\n"; 

    while(!que.empty()) 
    { 
     //Dequeue a vertex from que and print it 
     int front = que.front(); 
     cout<<front<<" "; 
     que.pop(); 
     // get all adjacent vertices of the dequeued vertex s 
     // If an adjacent vertex has not been visited, 
     //then mark it as visited 
     // and enqueue it 
     for(vector<int>::iterator it=nodes[front].begin(); 
       it!=nodes[front].end(); ++it) 
     { 

      if(visited[*it]==false) 
      { 
       visited[*it]=true; 
       que.push(*it); 
      } 
     } 
     // cout<<endl; 
    } 
    cout<<endl; 
    int Sz = sizeof(level)/sizeof(int); 
    /*for(int i=0;i<=edges;i++) 
    { 
     cout<<"Level of "<<i<<"is "<<level[10]<<endl; 
    }*/ 
    return 0; 
} 

[請注意在code.I結束的註釋部分嘗試了一些方法，但failed.I刪除了這些tracking.Please幫我更新代碼。]

Answer 1

您可以使用此功能找到樹中每個節點的級別。

複雜性是O（n），因爲我們正在訪問每個節點一次。

祝您好運

的

#define ll long long int 
ll level[100005],arr[100005]; 
vector <ll> adj[100005]; 

void bfs(ll s) 
{ 
    ll vis[100005]; 
    memset(vis,false,sizeof vis); 
    queue <ll> q; 
    q.push(s); 
    level[s] = 1; 
    vis[s] = true; 

    while(!q.empty()) 
    { 
     ll p = q.front(); 
     //cout<<p<<endl; 
     q.pop(); 

     vector <ll>::iterator it; 
     for(it=adj[p].begin();it!=adj[p].end();++it) 
     { 
       if(vis[*it] == false) 
       { 
        level[*it] = level[p] + 1; 
        q.push(*it); 
        vis[*it] = true; 
       } 
     } 
    } 
}