Prim 's Algorithm with Matrices

Question

저는 Prim의 알고리즘을 C++과 행렬로 구현하려고합니다.

int node[] = {11, 11, 0, 11, 11, 11, 11, 11}; 
int nodeCon[8]; 

void generatePrims() { 
    int cNode = 3; 

    for (int i = 1; i <= 8; i++) { 

     if (graph[cNode][i] != 0){ 

      if (node[i] > graph[cNode][i]) { 
       node[i] = graph[cNode][i]; 
       nodeCon[i] = cNode; 
       } 
      } 
     } 
}; 

cNode가 시작 노드 :

여기 내 문제입니다.

graph[][]은 연결을 유지하는 2 차원 행렬입니다.

nodeCon[]

는 (다른 노드에 연결된다)에 연결하기위한 MST

node[]=는 nodeCon 대한 비용 값을 유지를 보유 할 배열이다.

내 질문은 어떻게 다음 호프로 계속할 것인가? 최소 연결을 찾았고 루프가 어떻게 보이는지 값 cNode= minConnection을 설정한다고 가정 해 봅시다. 내가 모든 노드를 검사했다는 것을 어떻게 알았습니까? 사전에

덕분에이 같은

Answer 1

뭔가 : 주목할 가치 또한

int node[]={11,11,0,11,11,11,11,11}; 
int used[]={0,0,0,0,0,0,0,0,0,0}; 
int nodeCon[8]; 

void generatePrims(){ 
    int cNode = 3; 
    int next, min_now; 
    for(int i=0; i<8; ++i) { 
     used[cNode] = 1; 
     min_now = MAX_INT; 
     for(int i=1;i<=8;i++){ 
     if(!used[i]){ 
      if(node[i] > graph[cNode][i]){ 
       node[i] = graph[cNode][i]; 
       nodeCon[i]= cNode; 
      } 
      if(node[i] < min_now) { 
       min_now = node[i]; 
       next = i; 
      } 
     } 
     } 
     cNode = next; 
    } 
}; 

:이 빠른 경우 대신 사용하지 않는 정점의 목록을 사용합니다 '사용'배열이 될 것입니다.

Answer 2

나는 (내가 충분한 평판이 없기 때문에) 이전 답변에 대해 언급 할 수 없으므로 다른 답변을 통해 답변을 드리겠습니다. Piotr 솔루션은 거의 정확하지만 Prim의 알고리즘은 현재 노드 이상을 고려합니다. 예는 여기 Prim's Algorithm에서 볼 수 있습니다. 이것이 본질적으로 의미하는 것은 가장 최근 노드뿐만 아니라 방문한 노드의 경로를 확인해야한다는 것입니다.

이것은 마지막으로 방문한 노드의 경로를 확인하는 것과는 대조적으로 방문한 노드와 "각 노드"가 포함 된 벡터를 저장해야한다는 것을 의미합니다.

Answer 3

다음 사이트에는 알고리즘이 구현되었으며 junit 테스트 클래스가 있습니다. 그래서 그것은 당신이 찾고있는 것이어야합니다. 단위 테스트 클래스에는 물론 실제 행렬이 있습니다. 구현 클래스에는 코드가 있습니다. 이 도움이된다면

http://www.geekviewpoint.com/java/graph/mst