폭 넓은 검색을 구현하는 방법은 무엇입니까?

Question

BFS를 C++로 구현하려고했는데 함수는 다음과 같이 작동해야합니다. 그래프로 &을 매개 변수로 가져온 다음 두 벡터를 만들고 그 중 하나는 매개 변수 정점에 인접한 정점을 저장하는 데 사용됩니다. 그 중 하나가 방문되지 않은 경우 인접성을 가져 와서 벡터에 추가 한 다음 정점을 VISITED로 표시하고 인쇄해야합니다. 나는이 코드를 썼지 만 어떤 것도 출력했다. 참고 : 다른 함수가 그래프와 같은 데이터 구조 &이 작동하고, 문제가 BFS 함수에 있음을 확인했습니다. 여러분 중 일부가 문제를 해결하는 데 도움이되기를 바랍니다.

#include <iostream> 
#include <vector> 
#include <queue> 

using namespace std; 

enum Mark {VISITED, UNVISITED}; 

struct Vertex { 

    char name; 
    Mark mark; 
}; 

struct Edge{ 

    Vertex v1; 
    Vertex v2; 
    Edge(Vertex vertex1, Vertex vertex2): v1(vertex1), v2(vertex2){}; 
}; 

struct Graph{ 

vector<Vertex>vertices; 
vector<Edge>edges; 

vector<pair<Vertex, Edge>> adjacent(char u){ 

    vector<pair<Vertex, Edge>>res; 

    for(Edge e : edges){ 
     if(e.v1.name == u){ 
      res.push_back(make_pair(e.v2, e)); 
     }else if(e.v2.name == u){ 
      res.push_back(make_pair(e.v1, e)); 
     } 
    } 
    return res; 
} 

vector<Vertex> getAdj(char u){ 

    vector<Vertex>result; 

    for(Edge e: edges){ 
     if(e.v1.name == u){ 
      result.push_back(e.v2); 
     }else if(e.v2.name == u){ 
      result.push_back(e.v1); 
    } 
} 
    return result; 
} 
}; 

void BFS(Graph g, Vertex u){ 

    vector<Vertex>vec = g.getAdj(u.name); 

    for(Vertex v : vec){ 
     if(v.mark == UNVISITED){ 
      vector<Vertex>q = g.getAdj(v.name); 
      for(int i=0; i<q.size(); i++){ 
       vec.push_back(q[i]); 
      } 
      v.mark = VISITED; 
      vec.pop_back(); 
      cout << v.name << " "; 
    } 
    } 
} 





int main(int argc, const char * argv[]) { 

    Graph g; 

    Vertex v1, v2, v3, v4, v5, v6; 

    v1.name = 'A'; 
    v2.name = 'B'; 
    v3.name = 'C'; 
    v4.name = 'D'; 
    v5.name = 'E'; 
    v6.name = 'Z'; 

    g.edges.push_back(Edge(v1, v2)); 
    g.edges.push_back(Edge(v1, v3)); 
    g.edges.push_back(Edge(v2, v3)); 
    g.edges.push_back(Edge(v2, v4)); 
    g.edges.push_back(Edge(v3, v4)); 
    g.edges.push_back(Edge(v3, v5)); 
    g.edges.push_back(Edge(v4, v5)); 
    g.edges.push_back(Edge(v4, v6)); 
    g.edges.push_back(Edge(v5, v6)); 

    BFS(g, v1); 

    cout << endl; 

    } 

Answer 1

Vertex을 완전히 초기화하지 않았습니다. 이름을 알려주지 만 초기 mark 태그는 사용하지 않습니다.

당신은 당신의 기본이를 추가 할 수 있습니다

enum Mark {VISITED, UNVISITED}; 

struct Vertex { 

    char name; 
    Mark mark = UNVISITED; 
}; 

(나는 또한 생성자를 만들 것입니다 :

v1.mark = UNVISITED; 
    v2.mark = UNVISITED; 
    v3.mark = UNVISITED; 
    v4.mark = UNVISITED; 
    v5.mark = UNVISITED; 
    v6.mark = UNVISITED; 

당신은이 같은 (enum class로 교체하는 것이 더있을 수 있습니다)을 할 수있다 네가 그렇게하는 것을 잊지 않고 있는지 확인하기 위해 이름을 초기화하는 것).

UPDATE :이

당신의 BFS 몇 가지 문제가 있습니다 이 - 당신이 당신의 내부 루프 내부 vec에 요소를 추가하고 있기 때문에, 외부 루프가 제대로 작동하지 않습니다 (나는 그것이 있다고 생각 iterator와 관련이 있고 벡터의 크기를 항상 변경하기 때문에 발생합니다.) 정규 for 루프를 사용하여 문제를 해결했습니다.

• 원거리 for-loop를 사용하더라도 벡터에서 "왼쪽에서 오른쪽으로"이동합니다. 그리고 당신은 pop_back()을 사용하여 벡터의 끝에서 제거합니다 (따라서 벡터의 가장 오른쪽에 있음). 나는 이것이 당신이 원하는 것이라고 생각하지 않습니다.

• 방문한 적이없고 방문하지 않은 eacher Vertex를 표시하여 올바른 아이디어를 얻었습니다. 그러나 BFS 함수에있는 을 vec에만 업데이트하고 있습니다. 그러나 그들은 getADj 메서드의 복사본 일뿐입니다. 즉, 이미 방문한 정점이있을 때마다 vec에 새 이웃을 추가 할 때마다 그 값을 알 수 없습니다. 효과적으로 방문한 적이없는 새로운 Vertex을 추가하고 있습니다.

다른 문제가있을 수 있지만 이미 손에 쥐고있는 것이 좋습니다.

코드에서 문제를 발견하는 데 도움이되도록 'valgrind'와 같은 디버거 및/또는 도구를 사용하는 것이 좋습니다.