클래식 Prim 알고리즘 제목 및 코드

1435 단어 알고리즘 테마
Prim 알고리즘은 최소 생성 트리를 해결하는 고전적인 알고리즘(특히 조밀도 효율이 높음)으로 현재 이런 간단한 최소 생성 문제에 대해 완전한 코드를 제공한다.
n과 m를 입력하면 n개의 노드, m개의 변을 대표하고 그 다음에 m줄의 입력을 의미한다. 줄마다 x, y,z가 있고 x에서 y까지의 거리 는 z이다.문제: 각 점을 연결할 수 있는 가장 짧은 경로는 얼마입니까?
테스트 예:/*10 121 4 11 5 11 6 14 8 14 3 13 5 15 7 13 7 16 2 17 2 17 10 12 9 1*/
AC 코드를 직접 제공합니다.
#include
#include
const int maxn=100;
int n,m;
int map[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int path[maxn];
int prim()
{
    memset(dis,0x3f,sizeof(dis));           //         
    memset(vis,0,sizeof(vis)); 
    int ans=0;
    dis[1]=0;
    while(1)
    {
        int k=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]map[k][j])
            {
                dis[j]=map[k][j];
                path[j]=k;
            }

        }
    }
    return ans;
}
void print(int x)
{
    if(x==-1) return ;
    print(path[x]);
    printf("%d->",x);
}
int main()
{
    int x,y,z;
    memset(map,0x3f,sizeof(map));
    memset(path,-1,sizeof(path));
    scanf("%d%d",&n,&m);
    for(int i=0;i

/*
10 12
1 4 1
1 5 1
1 6 1
4 8 1
4 3 1
3 5 1
5 7 1
3 7 1
6 2 1
7 2 1
7 10 1
2 9 1
*/

좋은 웹페이지 즐겨찾기