最小生成ツリー概念、最小生成ツリーサイド権の和——モジュラス付き擬似コード、実現コード、例

56598 ワード

PAT甲級

記事の目次

概念

1.1定義

1.2性質

最小生成ツリーを解く

.プリムアルゴリズム

2.1.1アルゴリズム思想

2.1.2アナログコード

.2.1.3コード

2.3.3.1隣接行列

2.3.3.2隣接表

2.1.4注意点

2.1.5例

.kruskyalアルゴリズム

.2.1基本思想

.2.2テンプレートの疑似コード

.2.3実現コード

2.2.4注意

.2.5例

1概念
1.1定義
最小生成ツリー:与えられた無方向図G(V,E)の中で1つのツリーTを求めて、この木に図Gのすべての頂点を持たせ、すべての辺は図Gの中の辺から来て、ツリー全体の境界権の和が最小となる.
1.2性質

1最小生成ツリーはツリーであるので、その辺の数は頂点ツリーの一つを減らします.そして、ツリー内には必ずリングがありません.

は、所与の図G(V,E)に対して、その最小生成ツリーが一意でなくてもよいが、その辺権の和が一定で一意である.

3最小生成ツリーは、図上に生成されないので、そのルートノードは、このツリー上の任意の結点とすることができる.

2最小生成ツリーを解く
2.1 primアルゴリズム(プリムアルゴリズム)
2.1.1アルゴリズム思想

は、図G(V,E)のセットSに対して、アクセスされた頂点を格納し、次に、n回以下の2つのステップを実行する.

1は、セットV−Sの中から、セットSに最も近い頂点(uと表記)を選択するたびに、uにアクセスし、セットSに加入するとともに、このセットSに一番近い辺を最小生成ツリーに追加する.

は、頂点uをセットSとセットV-Sとの接続のインターフェースとして、uから到達できる未アクセスの頂点vとセットSの最短距離

を最適化する.
2.1.2テンプレートの疑似コード

// G         ；  d      S     
Prim(G, d[]){
       ;
    for (  n )
    {
        u =  d[u]             ;
         u    ;
        for ( u          v)
        {
            if(v    && u      v   S     d[v]  ){
                 G[u][v]   v   S     d[v];
            }
        }
    }
}

2.1.3コード
2.1.3隣接マトリックス

const int MAXV = 1000;
const int INF = 0x3fffffff;
int G[MAXV][MAXV];// 
int n;//    
bool vis[MAXV] = {false};//         
int d[MAXV];//     S     

int prim(){//  0     ，              
    fill(d, d + MAXV, INF);
    d[0] = 0;//  0      S    0，   INF
    int ans = 0;//            
    for (int i = 0; i < n; ++i)
    {
        int u = -1, min = INF;
        for (int j = 0; j < n; ++j)
        {
            if(vis[j] == false && d[j] < min){
                u = j;
                min = d[j];
            }
        }
        //     INF d[u]，         S   
         if(u == -1) return -1;
         vis[u] = true;
         ans += d[u];//    S             
    
        for (int v = 0; v < n; ++v)
        {
            //v    && u   v &&  u       v   S  
            if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v]){
                d[v] = G[u][v];
            }
        }
    }

    return ans;
}

2.3.3.2隣接表

struct node
{
    int v;
    int dis;
};

const int MAXV = 1000;
const int INF = 0x3fffffff;
vector<node> G[MAXV];// 
int n;//    
bool vis[MAXV] = {false};//         
int d[MAXV];//     S     

int prim(){//  0     ，              
    fill(d, d + MAXV, INF);
    d[0] = 0;//  0      S    0，   INF
    int ans = 0;//            
    for (int i = 0; i < n; ++i)
    {
        int u = -1, min = INF;
        for (int j = 0; j < n; ++j)
        {
            if(vis[j] == false && d[j] < min){
                u = j;
                min = d[j];
            }
        }
        //     INF d[u]，         S   
         if(u == -1) return -1;
         vis[u] = true;
         ans += d[u];//    S             
    
        for (int j = 0; j < G[u].size(); ++j)
        {
            int dis = G[u][j].dis;
            int v = G[u][j].v;
            //v     &&  u       v   S  
            if(vis[v] == false && dis < d[v]){
                d[v] = dis;
            }
        }
    }

    return ans;
}

2.1.4注意点

上に書かれたアルゴリズム時間の複雑さはO(V 2)である.

隣接表の書き方は、積み上げによって最適化され、時間の複雑さをO(VlogV+E)

に低減することができる.

は、頂点がより少ないエッジが多い場合には、primアルゴリズム

を使用する.
2.1.5例
入力:6 10/6頂点、10辺.以下の10の行為10条辺0 1 4/辺0->1と1->0の辺権は4で、下同0 1 0 5 2 1 2 6 1 5 3 3 5 5 3 3 4 5 5 5 5 5 5 5 3出力:15/最小生成樹辺権

#include 
#include 
#include 

using std::vector;
using std::fill;

struct node
{
    int v;
    int dis;
    node(int _v, int _dis): v(_v), dis(_dis){}
};

const int MAXV = 1000;
const int INF = 0x3fffffff;
vector<node> G[MAXV];// 
int n;//    
bool vis[MAXV] = {false};//         
int d[MAXV];//     S     

int prim(){//  0     ，              
    fill(d, d + MAXV, INF);
    d[0] = 0;//  0      S    0，   INF
    int ans = 0;//            
    for (int i = 0; i < n; ++i)
    {
        int u = -1, min = INF;
        for (int j = 0; j < n; ++j)
        {
            if(vis[j] == false && d[j] < min){
                u = j;
                min = d[j];
            }
        }
        //     INF d[u]，         S   
        if(u == -1) return -1;
        vis[u] = true;
        ans += d[u];//    S             

        for (int j = 0; j < G[u].size(); ++j)
        {
            int dis = G[u][j].dis;
            int v = G[u][j].v;
            //v     &&  u       v   S  
            if(vis[v] == false && dis < d[v]){
                d[v] = dis;
            }
        }
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    int m, u, v, w;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back(node(v,w));
        G[v].push_back(node(u,w));
    }

    int ans = prim();
    printf("%d
", ans);
    return 0;
}
/*
6 10
0 1 4
0 4 1
0 5 2
1 2 6
1 5 3
2 3 6
2 5 5
3 4 4
3 5 5
4 5 3
*/

2.2 kruskyalアルゴリズム(クルースカルアルゴリズム)
2.2.1基本思想

は初期状態のとき、図中のすべての辺に隠れていて、図中の各頂点は一つの連結ブロックをなしている.その後、次のステップを実行します.

ペアはすべての辺に対して、小さい時から大きな順に並べ替えられます.

は辺権によって小さい時から大きい時まですべての辺をテストして、もし現在のテスト辺の接続した2つの頂点が同一の接続ブロックの中にないならば、このテストを現在の最小生成ツリーに参加します.そうでなければ、捨てます.

3は、最小生成ツリーにおける辺数が頂点ツリーマイナス1に等しいか、またはテストが終了した時点で終了するまで、ステップ2を実行する.そして、終了時に、最小生成ツリーのエッジ数が総頂点ツリーより1未満であれば、この図は接続されていないことを説明する.

は、簡単に言います.図中の最小辺権の辺を選択するたびに、辺の両端の頂点が異なる連結ブロックにある場合、この辺を最小生成ツリーに追加します.

2.2.2モデルの疑似コード

1辺の定義は、辺の2つの断線点が異なる連結ブロックにあるかどうかを判断する必要があるので、辺の2つのエンドポイント番号は必ず必要である.アルゴリズムはサイド権に関連していますので、サイド権も必要です.

struct edge
{
    int u, v;//        
    int cost;//  
};

順序付け関数は、配列Eを、小さいときから大きな順に並べ替えさせます.

bool cmp(edge a, edge b){
    return a.cost < b.cost; 
}

疑似コード

int krukal(){
                ans、           Num_Edge;
               ;
    for(          ){
        if(               ){
                        ;
            ans +=       ;
                      Num_Edge 1;
               Num_Edge      1     ;
        }
    }
    return ans;
}

2.2.3実現コード

const int MAXV = 120;//     
const int MAXE = 1000;//    
int father[MAXV];//     

struct edge
{
    int u, v;//        
    int cost;//  
}E[MAXE];



int findFather(int x){
    int a = x;
    while(x != father[x]){
        x = father[x];
    }

    while(a != father[a]){
        int z = a;
        a = father[a];
        father[z] = x;
    }

    return x;
}


bool cmp(edge a, edge b){
    return a.cost < b.cost; 
}

int krukal(int n, int m){
    int ans = 0, Num_Edge = 0;//ans:      ；Num_Edge：        
    for (int i = 1; i <= n; ++i)//       1~n
    {
        father[i] = i;//      
    }
    sort(E, E + m, cmp);//          

    for (int i = 0; i < m; ++i)//     
    {
        int faU = findFather(E[i].u); //                  
        int faV = findFather(E[i].v);
        if(faU != faV){//         
            father[faU] = faV;//    （           ）
            ans += E[i].cost;//            
            Num_Edge++;//        1
            if(Num_Edge == n - 1){//       -1 ，    
                break;
            }
        }
    }
        if(Num_Edge != n - 1){//     ，  -1
            return -1;
        }else{//            
            return ans;
        }
}

2.2.4注意
*時間の複雑さは主に辺を並べ替えることにあります.時間の複雑さはO(ElogE)です.

は、頂点に適合しており、辺数が少ない場合(疎図)

2.2.5例
入力:6 10/6個の頂点、10本の辺、下は10本の無向辺0 1 4/0番の頂点と1番の頂点の無向辺の辺権が4 0 4 1 0 1 0 5 2 1 1 5 3 2 5 5 5 3 5 5 5 5 4 5 3 3 3 3 3 3 3に従って出力します.11/最小生成樹の辺権の和

#include 
#include 

using std::sort;

const int MAXV = 110;
const int MAXE = 10000;
int father[MAXV];

struct edge
{
    int u, v;
    int cost;
}E[MAXE];

bool cmp(edge a, edge b){
    return a.cost < b.cost;
}

int findFather(int x){
    int a = x;
    while(x != father[x]){
        x = father[x];
    }

    while(a != father[a]){
        int z = a;
        a = father[a];
        father[z] = x;
    }

    return x;
}


int kruskal(int n, int m){
    int ans = 0, Num_Edge = 0;
    for (int i = 0; i < n; ++i)
    {
        father[i] = i;
    }

    sort(E, E + m, cmp);
    for (int i = 0; i < m; ++i)
    {
        int faU = findFather(E[i].u);
        int faV = findFather(E[i].v);
        if(faU != faV){
            father[faU] = faV;
            ans += E[i].cost;
            Num_Edge++;
            if(Num_Edge == n - 1){
                break;
            }
        }
    }
    if(Num_Edge != n - 1){
        return -1;
    }else {
        return ans;
    }
}

int main(int argc, char const *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);
    }
    int ans = kruskal(n, m);
    printf("%d
", ans);
    return 0;
}

/*
6 10
0 1 4
0 4 1
0 5 2
1 2 1
1 5 3
2 3 6
2 5 5
3 4 5
3 5 4
4 5 3
*/

IKEANalyzer中国語分詞器を利用してBayesアルゴリズムをシミュレートして迷惑メールのフィルタリングの実現(ソース付き)

ポリシーモード-Java