부스트

Question

나는 세 개의 벡터와 부스트를 사용하여 그래프를 구현하기 위해 노력하고있어를 사용하여 벡터와 그래프를 구현 :

std::vector<std::string> vertex_array; 
std::vector<Edge> edge_array; 
std::vector<int> weight_array; 

Edge는 다음과 같이 정의된다

typedef std::pair<std::string, std::string> Edge; 

내 그래프는 다음과 같이 정의된다 :

typedef adjacency_list<vecS, vecS, undirectedS> Graph; 

배열은 모두 입력 파일에서 가져온 데이터로 채워져 있으므로 배열의 첫 번째 요소는 꼭짓점 벡터는 "A"와 같을 것입니다. 가장자리 벡터의 첫 번째 요소는 (B, C)와 같을 것이고 무게 벡터의 첫 번째 요소는 가장자리 벡터의 첫 번째 가장자리의 가중치가 될 것입니다. 이 경우.

문제는 C++에 익숙하지 않고 그래프와 그래프를 새로 추가하는 것입니다. 부스트 웹 사이트의 예제 코드를 살펴 보았지만 벡터 대신 배열을 사용합니다. 나는이 예제 코드를 시도했다 :

Graph g(edge_array, edge_array + sizeof(edge_array)/sizeof(Edge), num_vertices); 

나는 num_vertices 변수를 가지고 있지만 여전히 오류가 발생한다.

아무도 Dijkstra의 부스트 버전을 사용할 수있는 가장자리, 정점 및 가중치 벡터가있는 그래프를 만드는 방법을 알고 있습니까?

죄송합니다.이 질문이 실제로 모호하거나 초보라면, 나는 진지하게 부스트를 사용하고 그래프를 구현하는 것에 대해 아무것도 모릅니다. docs에서

Answer 1

: 유형의 그래프가 정점 목록 그래프 및 Incidence Graph의 모델이 아니면 안된다

.

adjacency_list 그래프를 사용 an example too을있다.

그 샘플에서 vecS와 listS 교체

는, 동일한 응답은 (비록 이러한 변화의 정신에 대한 모든 코드를 확인하지 않은)이 줄에서

---

typedef adjacency_list<vecS, vecS, undirectedS> Graph; 

반환이 가장자리에 아무런 weight 속성이없는 것 같습니다. Dijkstra가 정보없이 최적의 경로를 선택하는 것은 혼란 스러울 것입니다. 문서를 한눈에 볼 때 외부 weight지도를 제공 할 수 있다고 생각합니다. 참고 :

모든 가장자리 가중치가 1 일 때 Dijkstra 알고리즘 대신 너비 우선 검색을 사용하십시오.