작은 생 성 트 리 의 Kruskal 구현

2020 단어 알고리즘도 론
보통 작은 생 성 트 리 는 Prim 알고리즘 을 사용 하여 이 루어 집 니 다. Prim 알고리즘 이 느슨 해 지 는 동시에 최소 생 성 트 리 에서 임의의 두 점 사이 의 최 장 변 을 구 할 수 있 기 때 문 입 니 다.하지만 Kruskal 알고리즘 을 이용 해 느슨 함 과 동시에 구 할 수 는 없 었 다.
    그래서 우 리 는 Kruskal 에서 가장 짧 은 길 을 구 한 후에 모든 정점 bfs 에 대해 한 번 에 나무 위의 임의의 두 점 의 가장 긴 변 을 얻어 야 한다.그 다음 에 나무 에 없 는 가장 작은 값 을 찾 는 대신 이전 처럼 매 거 할 수 있 기 를 바 랍 니 다.
    두 가지 방법의 시간 잡 도 는 같 지만 Kruskal 의 실현 코드 는 매우 길 어 지지 만 Kruskal 의 실현 은 Prim 이 처리 하기 어 려 운 중 변 을 처리 할 수 있다.
코드 구현 은 Uva 10462 를 예 로 들 면:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define mem(a,b) memset((a),(b),sizeof(a))

const int MAXV=100+3;
const int MAXE=200+3;

struct Edge
{
    int from,to,cost;
    Edge(int f=0,int t=0,int c=0):from(f),to(t),cost(c){}
    bool operator > G[MAXV];//     

void init()//   
{
    for(int i=1;i<=E;++i)
        used[i]=false;
    for(int i=1;i<=V;++i)
    {
        par[i]=i;
        high[i]=0;
        G[i].clear();
    }
}

int findfather(int x)
{
    return par[x]=par[x]==x?x:findfather(par[x]);
}

bool unite(int a,int b)
{
    int fa=findfather(a),fb=findfather(b);
    if(fa==fb)
        return false;
    if(high[fa]>high[fb])
        par[fb]=fa;
    else
    {
        par[fa]=fb;
        if(high[fa]==high[fb])
            ++high[fb];
    }
    return true;
}

void bfs(int s)
{
    mem(vis,0);
    vis[s]=true;
    the_max[s][s]=0;
    queue que;
    que.push(s);
    while(!que.empty())
    {
        int u=que.front(); que.pop();
        for(int i=0;i
CSS3 이미지 투영
css3에서 변형 함수(같은 원소에 대한)와 원소는 자신의 속성을 바꾸어 애니메이션 효과를 얻는다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage