首页 > 代码库 > 最短路径之Kurskal

最短路径之Kurskal

2024-07-14 20:10:21   215人阅读

个人观点，较prime算法，Kurskal算法更加的简单，这里我们只需要每一次去需找权值最小的那条边就好，在这里我们先可以利用sort进行快排，得到权值最小的map[i] 。 得到该条边的两个节点map[i].u 和map[i].v，这时候你需要判断能不能用这条边，因为最小生成树是不能形成回路，所以用到了 并查集的方法，可以快速的判断这两个点是否满足条件。如果不存在关系那么那么就把这条边加入，反之，舍弃该边，直到e-1边为止。
（该代码未印证过~~）
#include
#include
#include
using namespace std ;

#define INT_MAX 1000000
#define MAXN 100

int father[MAXN] ;

typedef struct node
{
 

   int u , v;
    int w;

}Kruskal ;

int cmp(Kruskal x , Kruskal y)
{
    return x.w< y.w ;

}
//该函数是用来寻找父亲节点的 ，在后面的用处就是判断两个节点是否存在关系
//如果存在那么这两个点不能加进来，加进来会形成回路 。
find (int x)
{
    while(x !=father[x])
      x = father[x] ;
    return x;

}

int main()
{
   Kruskal  map[MAXN] ;

    int e , n;
    int i , j;
    int result =0 ,cot = 0 ;

    scanf("%d",&e) ;

    for(i = 1 ;i <= e ;i++)
      father[i] = i ;
    
    for(i = 1 ;i <= e ; i++)
      scanf("%d%d%d", &map[i].u , &map[i].v ,&map[i].w ) ;
    sort(map + 1, map + e + 1 ,cmp ) ;

    int u , v;

    for(i = 1 ;i <= e ;i++){
    
      u = map[i].u ;
      v = map[i].v ;

      if(find(u) != find(v))
      {
         father[u] = v ;
         result += map[i].w ;
         cot++ ;
      }
      if(cot == e-1)
         break ;      
    }

    return 0;
}


联系
我们