그래프 이론 - 스위칭 트리 멤버

Question

C++로 그래프를 정의하는 방법을 결정할 수 없습니다.

는 지금, 나는 2 차원 배열이 있습니다

A - B,D 
B - A 
C - D 
D - A,C 

을하지만 난 그래프의 일부 "회원"으로 전환하고자 할 때 내 문제는 온다 (예를 들어, D 및 A). 난 내가 (내가 수동으로 그래프에서 알 수있다) 같은 것을 필요로 알고

A - C,D 
B - D 
C - A 
D - A,B 

하지만 난 실제로 모르는, 변경할 수 있습니다 알고리즘을 작성하는 방법 2D 배열의 순서는 1D 배열의 순서를 바꾸는 것만 큼 간단하지 않기 때문입니다.

Answer 1

데이터에서 그래프를 나타내는 두 가지 일반적인 방법이 있습니다. 첫 번째와 두 번째는 정점 인 쌍의 집합입니다. 쌍이 존재하면, 에지가 두 쌍의 정점 btween 존재 :

std::set<std::pair<int, int> > setMyGraph; 

번째 인접성 매트릭스로서 알려진 데이터 구조를 사용한다. 행렬은 행과 열에있는 정점을 나열하고 정점 x와 정점 y 사이에 모서리가 있으면 위치 (x, y)에 참을 보유합니다. 그렇지 않으면 false를 유지합니다.

vector<vector<bool> > vMyGraph; 

Answer 2

그래프를 표현할 방법을 찾고 있다면 일을 끝내기 위해 boost :: graph를 고려해보십시오.

사용자가 하나의 정점을 다른 정점으로 드래그하여 병합 할 때 약간의 유사성이 있습니다. 내가하는 방식과 아마 같은 것을해야 할 것입니다. 가장자리를 추적하고 임시로 설명을 저장하고 그래프에 첨부 된 데이터를 저장하고 정점 중 하나를 삭제하십시오. 아마도 두 가지 모두를 수행해야합니다), 그래프의 재구성되어야하는 부분을 재구성합니다 ... 그러나 이제는 다릅니다.

Answer 3

포인터 대신 색인을 사용하여 이웃을 참조하는 경우 A와 D를 바꾸고 가장자리를 변경하지 않고 그대로 둘 수 있습니다. 즉,

0 (D) - 1, 3 
1 (B) - 0 
2 (C) - 3 
3 (A) - 0, 1 

편집에

0 (A) - 1, 3 
1 (B) - 0 
2 (C) - 3 
3 (D) - 0, 1 

에서 2 차원 배열을 변경 당신이 포인터를 사용하거나, 그래프는 노드 값을 포함하는 각의 순서 (A에서 설명하지 여부 , B, C 또는 D) 및 이웃 노드에 대한 참조를 포함 할 수 있습니다. 이러한 참조는 노드 배열에 대한 인덱스 (예제에서와 같이)이거나 이웃 노드에 대한 포인터 일 수 있습니다. 네이버의 표현이 무엇이든간에 값을으로 바꾸고 이웃 참조를 변경하지 않고 그대로 둘 수 있습니다.