무차별 그래프에 설정된 최대 독립적 독립 정점에 대해 메모리를 보존하면서도 효율적인 알고리즘을 찾고 싶습니다.메모리 보수적 인 최대 정점 집합
전통적인 알고리즘은 보조 데이터 구조 (원본 그래프의 복사본)를 사용하여이를 구현합니다. 메모리 할당이 실시간 구현을 위해 느리고 일부 메모리 경계가 있기 때문에 이러한 병렬 구조는 피하고 싶습니다. MIS의 노드를 부울 레이블로 표시하기 만하면됩니다. 가능합니까? 나는 최대 독립하지만 최대 독립적 인 설정을하지 않으
참고.
P. 이 문제는 언어 독립적이지만 C++ 및 STL로 코딩하고 있음을 알고 있습니다.
데이터 구조가 무엇인지 정확히 모른 채 이러한 종류의 질문에 대답하는 것은 어렵습니다. 가까운 자리에있는 그래프 작업에 대한 일반적인 트릭은 그렇지 않으면 포인터에서 0이되고 그래프 구조를 되돌릴 수있는 변경을하는 두 비트를 훔치고 있지만 어떻게 적용할지는 모르겠습니다.
작성한 내용을 읽은 것에서는 탐색하지 않고 그래프의 노드를 반복 할 수있는 방법이없는 것으로 보입니다. DFS와 같이 스택을 어떻게 표현하고 있습니까?
다음은 각 노드 i에 대해 부울 레이블 (i) 만있는 경우 솔루션입니다. 시간은 O (| V | + | E |)입니다. 여기서 | V | 노드의 수와 | E | 입력 그래프의 가장자리 수입니다.
For all nodes v
set label(v)=false;
For all nodes v
if (all neighbors w of v have label(w)=false)
set label(v)=true
(V)가 true = 레이블이 노드의 V는 최대 독립적 인 집합입니다. 어떤 레이블이 붙여진 노드 v도 레이블이 붙은 이웃을 가질 수 없기 때문에 그것들은 독립적입니다. 레이블이 활성화되어 있고 이미 레이블이 붙은 다른 이웃 노드가 레이블을 붙이지 않은 경우 레이블이 지정되지 않은 노드 만 남겨두기 때문에 최대 집합입니다.
최적화 노트 : 노드가 1 ... n으로 번호가 매겨지면 다른 w는 레이블 (w) = true를 가질 수 없으므로 이웃 w = 1..v-1 만 확인하면됩니다.
내가 스크래치를 사용 vector 또는 요소, 또는 모서리 또는면으로 사용되는 정점을 표시하는 데 사용 deque<bool> ... 사실
std::deque<bool> used(vertex.size(), false);
for (size_t e = 0; e < edge.size(); ++e)
{
used[edge[e].v1] = true;
used[edge[e].v2] = true;
}
이제 사용 ==가 사용 된 모든 정점을 나타냅니다. 당신이 원한다면 다른 사람들은 붕괴 될 수 있습니다.
일부 연구 끝에 MIS 알고리즘의 아주 간단한 버전을 발견했지만 보조 데이터 구조 (방문한 노드 세트)를 다시 사용합니다. std :: set를 사용하여 RB 트리로 구현하면 도움이 될 수 있습니다. 내부 메모리에서 그래프 G = (V, E)의 최대 독립 세트 S를 계산하기 위해 다음과 같은 간단한 알고리즘을 사용할 수 있습니다. 임의의 순서로 정점을 처리합니다. vertex v ∈ V를 방문했을 때 S에 해당 이웃이 없으면 S에 추가하십시오. 알고리즘은 Karp, 1985 – linello