使用STL在C ++中实现图形和BFS [英] Implementing graph and BFS in C++ using STL

问题描述

以下是我写的代码。

  #include< iostream> 
 #include< vector> 
 #include< list> 
 #include< queue> 
 
使用namespace std; 
 
 const int V = 5; 
 vector< list< int> >一个（V）; 
 
 int BFS（int s）
 {
 int visited [V] = {0}; 
队列< int> Q; 
 visited [s] = 1; 
 Q.push（s）; 
 while（！Q.empty（））
 {
 int x = Q.front（）; 
 vector< list< int> > :: iterator it1 = a.begin（）+ x; 
 list< int> IT2 = * IT1; 
 list< int> :: iterator iter = it2.begin（）; 
 while（iter！= it2.end（））
 {
 if（visited [* iter] == 0）
 {
 visited [* iter] = 1; 
 Q.push（* iter）; 
} 
 visited [x] = 2; 
 Q.pop（）; 
 iter ++; 
} 
} 
返回0; 
} 
 
 void addEdge（int i，int j）
 {
 a [i] .push_back（j）; 
 a [j] .push_back（i）; 
} 
 
 int main（）{
 vector< list< int> > :: iterator it1 = a.begin（）; 
 addEdge（0,1）; 
 addEdge（0,2）; 
 addEdge（2,1）; （it1！= a.end（））
 {
 list< int> 
 IT2 = * IT1; 
 list< int> :: iterator iter = it2.begin（）; （iter！= it2.end（））
 {
 cout<< * iter<<; 
 iter ++; 
} 
 cout<< endl; 
 it1 ++; 
} 
 cout <<< BFS（0）; 
返回0; 
} 
  

执行BFS（0）时，编译器给我一个运行时错误。由于我对迭代器没有太多经验，我认为错误来自BFS函数中的迭代器语句。请帮我解决我在代码中遇到的问题。

谢谢！

解决方案

你的流行逻辑是错误的。它应该是这样的：

  int BFS（int s）
 {
 int visited [V] = {0}; 
队列< int> Q; 
 visited [s] = 1; 
 Q.push（s）; 
 while（！Q.empty（））
 {
 int x = Q.front（）; 
 Q.pop（）; //在这里弹出我们现在有x 
 
 vector< list< int> > :: iterator it1 = a.begin（）+ x; 
 list< int> IT2 = * IT1; 
 list< int> :: iterator iter = it2.begin（）; 
 while（iter！= it2.end（））
 {
 if（visited [* iter] == 0）
 {
 visited [* iter] = 1; 
 Q.push（* iter）; 
} 
 ++ iter; 
} 
 
 visited [x] = 2; //设置在这里访问。 
} 
返回0; 
 
 
 
 
 
 $ b 
计算我给你的最终价值，因为我想你想要一些东西除零总是返回。但是，这是你问题的关键。 
 
 
 
祝您好运。
 
Following is the code I have written.
#include <iostream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

const int V=5;
vector<list<int> > a(V);

int BFS(int s)
{
    int visited[V]={0};
    queue<int> Q;
    visited[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int x=Q.front();
        vector<list<int> >::iterator it1=a.begin()+x;
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            if(visited[*iter]==0)
            {
                visited[*iter]=1;
                Q.push(*iter);
            }
            visited[x]=2;
            Q.pop();
            iter++;
        }
    }
    return 0;
}

void addEdge(int i, int j)
{
    a[i].push_back(j);
    a[j].push_back(i);
}

int main() {
    vector<list<int> >::iterator it1=a.begin();
    addEdge(0,1);
    addEdge(0,2);
    addEdge(2,1);
    while(it1!=a.end())
    {
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            cout<<*iter<<" ";
            iter++;
        }
        cout<<endl;
        it1++;
    }
    cout<<BFS(0);
    return 0;
}
The compiler gives me a runtime error when BFS(0) is executed. Since I do not have much experience with iterators, I think the error comes from the iterator statements in the BFS function. Please help me resolve the issues in my code.

Thank you!
解决方案
Your pop-logic is wrong. It should look like this:
int BFS(int s)
{
    int visited[V]={0};
    queue<int> Q;
    visited[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop(); // pop here. we have x now

        vector<list<int> >::iterator it1=a.begin()+x;
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            if(visited[*iter]==0)
            {
                visited[*iter]=1;
                Q.push(*iter);
            }
            ++iter;
        }

        visited[x]=2; // set visited here.
    }
    return 0;
}
Calculation of the final value I leave to you, as I imagine you want something besides zero always being returned. However, that was the crux of your problem. 

Best of luck.

                        
这篇关于使用STL在C ++中实现图形和BFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！