▼

쿠팡플레이

한화

대한민국

경희대

라이관린

한화생명

김시원

에이태큼스

젠트리피케이션

엔비디아 실적 발표

로그인 회원가입|아이디

비번찾기

개발자포럼 입니다.

C언어로 Prim 알고리즘 구현하였는데 질문좀 드려도 될까요..?8

오늘도달리고내일도달리고모레도달리면숨참
등록일 2013-06-10 22:12
조회수 1340

#include "stdafx.h"
#include

const double INF=1e10;

struct Edge {
        int v1, v2;
};

void Prim(const int n,  double W[10][10], Edge F[]);

void main()
{
        const int n=10;
        double W[10][10]={
                {0, 32, INF, 17, INF, INF, INF, INF, INF, INF},
                {32, 0, INF, INF, 45, INF, INF, INF, INF, INF},
                {INF, INF, 0, 18, INF, INF, 5, INF, INF, INF},
                {17, INF, 18, 0, 10, INF, INF, 3, INF, INF},
                {INF, 45, INF, 10, 0, 28, INF, INF, 25, INF},
                {INF, INF, INF, INF, 28, 0, INF, INF, INF, 6},
                {INF, INF, 5, INF, INF, INF, 0, 59, INF, INF},
                {INF, INF, INF, 3, INF, INF, 59, 0, 4, INF},
                {INF, INF, INF, INF, 25, INF, INF, 4, 0, 12},
                {INF, INF, INF, INF, INF, 6, INF, INF, 12, 0}
        };
        Edge mst[100];
        int i;

        Prim(10, W, mst);

        for (i=2;i<=mst[0].v1+1;i++)<br />                 printf("%d<-->%dn", mst[i].v1, mst[i].v2);

}

void Prim(const int n, double W[10][10], Edge F[])
{

        int i, k, vnear;
        double min;
        Edge e;                        //edge
        int *nearest=new int[n];
        double *distance=new double[n];

        F[0].v1=0;

        for (i=2;i         {
                nearest[i]=1;  //초기에는 Y에 노드가 v1하나
                distance[i]=W[1][i]; //v1,vi의 가중치로 초기화
        }

        for (k=2;k         {

                min=INF;
                for (i=2;i                 {
                        if (0<=distance[i] && distance[i]<min)<br />                         {
                                min=distance[i];
                                vnear=i;
                        }
                }
                e.v1=vnear;
                e.v2=nearest[vnear];
                F[k]=e;
                F[0].v1++;
                distance[vnear]=-1;
                for (i=2;i                 {
                        if (W[i][vnear]                         {
                                distance[i]=W[i][vnear];
                                nearest[i]=vnear;
                        }
                }
        }

        //delete [] nearest;
        //delete [] distance;
}

이렇게 구현하였는데 출력하였을때 제가 손으로 풀었던 것과는 다르게 출력되네요 ㅠㅠ
어디가 틀렸는지 조언좀 부탁드리겠습니다!

파워링크 등록안내



		목록보기

0 오늘도달리고내일도달리고모레도달리면숨참

는 표시가 안되네요;

2013-06-10 점아이콘

댓글주소복사

코드를 봐도 모르겠네요. 기대치가 뭐였고 실제출력이 아케 나왔는지 알려주시는게 다른분들에게 도움이 되지 않을까요?

2013-06-10 점아이콘

댓글주소복사

0 감각

prim이 길찾기 알고리즘이던가요?

각 스텝별 결과를 찍어내보세요

2013-06-10 점아이콘

댓글주소복사

0 오늘도달리고내일도달리고모레도달리면숨참

1 <--> 4
4 <--> 8
8 <--> 9
4 <--> 5
9 <--> 10
10 <--> 6
4 <--> 3
3 <--> 7
1 <--> 2

----------------------이렇게가 제가 예상하는 출력인데 실제출력은 아래처럼 나오네요..

4 <--> 1
3 <--> 4
7 <--> 3
8 <--> 7
9 <--> 8
5 <--> 9
2 <--> 3
6 <--> 2

2013-06-10 점아이콘

댓글주소복사

0 앞길이구만리

이러면 첫스텝부터 틀린거 아닌가요?

2013-06-10 점아이콘

댓글주소복사

0 잇카쿠

Prim 알고리즘이 뭔가요?

2013-06-11 점아이콘

댓글주소복사

0 끅끅끅

for문과 if 문 지워진 부분이 너무 많네요;

대충 감으로 보자면..
여기서 값입력이 잘못되서
for (i=2;i {
nearest[i]=1; //초기에는 Y에 노드가 v1하나
distance[i]=W[1][i]; //v1,vi의 가중치로 초기화
}

여기서 비교가 제대로 되지 않은 문제 같습니다..
for (i=2;i {
if (0<=distance[i] && distance[i] {

W[1][i]; 에서 i값이 2부터 변할 때 값이 어떻게 나오는지 보시면 어디를 수정하셔야 할지 대강 감이 오실 겁니다.

이건 별개인데.. 실행수를 체크하시느라 F[0]에 값을 추가하시고 f[1]은 구분자로 비워두신 듯 한데... 차라리 전역 변수 하나를 선언해서 사용하시는 게 나을 것 같습니다... 하나의 배열에 일괄성 없는 데이터가 들어가면서 헷갈리신 것 같은 소심한 주장을....ㅎㅎ;

2013-06-11 점아이콘

댓글주소복사

0 오늘도달리고내일도달리고모레도달리면숨참

감사합니다ㅎㅎ 복사붙이기 했는데 짤린부분이 많았네요 ㅠㅠ
어느정도 해결하게되었습니다! 답변 감사합니다 ^^

2013-06-11 점아이콘

댓글주소복사

알림 욕설, 상처 줄 수 있는 악플은 삼가주세요.
로그인 후 코멘트를 작성하실 수 있습니다.

짤방 사진		익명요구 다른의견


	△ 이전글▽ 다음글	목록보기