나는 일정한, 순서가없고, 가중치가없는, 희박한 그래프를 구현하려고합니다 (즉, 가장자리는 움직이지 않습니다). 그러나, 저는 정점의 순서가 바뀌는 정점 교환 작업을 많이 할 것입니다.C++로 그래프를 구현하는 가장 좋은 방법은 무엇입니까?
0: 1 2 3
1: 0 2
2: 0 1
3: 0
스왑 0, 3 :
0: 3
1: 3 2
2: 3 1
3: 1 2 0
C++에서 가장 구현이 무엇
예는 한 가지 방법은 + 인접성리스트 구조 unordered_sets의 벡터를 사용하는 것입니다?
여러 가지 구현이 있으며 정점 당 여러 매개 변수를 지정할 수 있습니다. 더 많은 조사가 학생을위한 운동으로 남아 있습니다.
Boost Graph Library을 살펴보십시오. 그것은 아마도 당신의 필요에 따라 작동 할 것입니다. 그러나 그렇지 않다면, 당신이 자신의 것을 굴리기 시작하기 전에 문서가 주제에 관해 배울 수있는 좋은 출발점이 될 것입니다.
편집 : 희소 그래프로 작업 할 예정이라면 먼저 adjacency list 버전을 먼저 살펴보고 싶을 것입니다. 템플릿 인수를 통해 구현하는 데 사용되는 기본 데이터 구조를 변경하여 부스트 adjacency_list 그래프의 성능 특성을 조정할 수 있습니다.
편집 : 설명하는 정점 스와핑과 관련하여 가장 쉬운 방법은 정점이 제자리에 머무를 수있는 정점 유형을 설정하는 것이지만 아마도 정점을 다른 곳으로 쉽게 스왑 할 수 있습니다. Bundled Properties 메커니즘은 이것을 구현하는 한 가지 방법입니다.
아마도 그래프일까요? : P –
그래프가 얼마나 희박해질 지 또 다른 요소가 있습니다. – bames53
그래프의 프로그래밍 표현에 대해 조금 배우고 Google이 C++로하는 방법을 배우십시오. 당신의 질문은 IMO의 좋은 질문으로 충분할 정도로 구체적입니다. 그러나이 정보는 당신 스스로 혼란스러워하지 않습니다. – djechlin