인접 행렬을 매개 변수로 사용하는 Prim MST

C에서 Prim MST로 작업하고 있으며이 함수는 인접 행렬을 사용합니다. 주어진 무게는 물론 A[i][j]입니다.인접 행렬을 매개 변수로 사용하는 Prim MST

내가 지금까지 발견 한 최소 가장자리를 추적하는 선행 배열이 있다고 가정합니다. predecessor[u]=v {이 또한 최종 MST}

지금 현재 A[i][j] 행렬을 수정하고 가장자리 (인덱스) 또한 이전 배열에 존재하는 경우 즉 1 에 가중치를 변경하고 싶습니다. 그렇지 않으면이를 0으로 변경합니다.

어떻게하면됩니까? 여기 내 솔루션입니다 :

for (x....) 
    for (y...) 
     if (x!=y && (p[x]==y || p[y]==x)) 
     set to 1 
     else 
     set to 0

2012-07-24 ms. sakura

바로 보이는 ... 실제 질문은 무엇입니까? – Spudd86

나는 그 밖의 무엇을 확인해야 할 지 완전히 확신하지 못한다 : S 어떻게 그랬습니까? –

정확하게 당신이 한 방법 ... 또는 아마도 sdcwc에 의한 답과 같습니다. – Spudd86

귀하의 의사가 올바른지, 이것은 당신에게 프림의 알고리즘에 의해 발견 트리를 나타내는 0-1 매트릭스를 제공 할 것입니다. 그러나이 저장 방법은 O (n^2) 공간이 필요하고 O (n) 메모리에 트리를 저장할 수 있기 때문에 비용이 많이 듭니다.

다른 방법으로, O에서 제로로 매트릭스를 초기화 할 수 있습니다 (N^2) 다음 O (n)이 시간에 가장자리를 추가

for (x ...) 
    for (y ...) 
     A[x][y] = 0 

for (x ...) 
    if (p[x] != x) 
     A[x][p[x]] = A[p[x]][x] = 1

2012-07-24 19:26:04 sdcvvc

답변