數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)-最小生成樹

連通圖的?生成樹定義: 所謂?一個連通圖的?生成樹是?一個極?小的連通?子圖,它含有圖中全部的n個頂點(diǎn),但只?足以構(gòu)成?一顆樹的n-1條邊.
定義解讀: 滿?足以下3個條件則為連通圖的?生成樹:

    1. 圖是連通圖;
    1. 圖中包含了了N個頂點(diǎn);
    1. 圖中邊的數(shù)量量等于N-1條邊.

今天學(xué)習(xí)最小生成樹的兩種算法:普里姆【Prim】算法和克魯斯卡爾【Kruskal】算法

一宦芦、Prim算法

算法思路:

    1. 定義2個數(shù)組; adjvex ?用來保存相關(guān)頂點(diǎn)下標(biāo); lowcost 保存頂點(diǎn)之間的權(quán)值
    1. 初始化2個數(shù)組, 從v0開始尋找最?小?生成樹, 默認(rèn)v0是最?小?生成樹上第?一個頂點(diǎn)
    1. 循環(huán)lowcost 數(shù)組,根據(jù)權(quán)值,找到頂點(diǎn) k;
    1. 更更新lowcost 數(shù)組
    1. 循環(huán)所有頂點(diǎn),找到與頂點(diǎn)k 有關(guān)系的頂點(diǎn). 并更更新lowcost 數(shù)組與adjvex 數(shù)組
      代碼實(shí)現(xiàn):
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */

typedef struct
{
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;


/*9.1 創(chuàng)建鄰接矩陣*/
void CreateMGraph(MGraph *G)/* 構(gòu)件圖 */
{
    int i, j;
    
    /* printf("請輸入邊數(shù)和頂點(diǎn)數(shù):"); */
    G->numEdges=15;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=10;
    G->arc[0][5]=11;
    G->arc[1][2]=18;
    G->arc[1][8]=12;
    G->arc[1][6]=16;
    G->arc[2][8]=8;
    G->arc[2][3]=22;
    G->arc[3][8]=21;
    G->arc[3][6]=24;
    G->arc[3][7]=16;
    G->arc[3][4]=20;
    G->arc[4][7]=7;
    G->arc[4][5]=26;
    G->arc[5][6]=17;
    G->arc[6][7]=19;
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/* Prim算法生成最小生成樹 */
void MiniSpanTree_Prim(MGraph G)
{
    int min, i, j, k;
    int sum = 0;
    /* 保存相關(guān)頂點(diǎn)下標(biāo) */
    int adjvex[MAXVEX];
    /* 保存相關(guān)頂點(diǎn)間邊的權(quán)值 */
    int lowcost[MAXVEX];
    
    /* 初始化第一個權(quán)值為0轴脐,即v0加入生成樹 */
    /* lowcost的值為0抡砂,在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹 */
    lowcost[0] = 0;
    
    /* 初始化第一個頂點(diǎn)下標(biāo)為0 */
    adjvex[0] = 0;
    
    //1. 初始化
    for(i = 1; i < G.numVertexes; i++)    /* 循環(huán)除下標(biāo)為0外的全部頂點(diǎn) */
    {
        lowcost[i] = G.arc[0][i];    /* 將v0頂點(diǎn)與之有邊的權(quán)值存入數(shù)組 */
        adjvex[i] = 0;                    /* 初始化都為v0的下標(biāo) */
    }
    
    //2. 循環(huán)除了下標(biāo)為0以外的全部頂點(diǎn), 找到lowcost數(shù)組中最小的頂點(diǎn)k
    for(i = 1; i < G.numVertexes; i++)
    {
        /* 初始化最小權(quán)值為∞, */
        /* 通常設(shè)置為不可能的大數(shù)字如32767恬涧、65535等 */
        min = INFINITYC;
        
        j = 1;k = 0;
        while(j < G.numVertexes)    /* 循環(huán)全部頂點(diǎn) */
        {
            /* 如果權(quán)值不為0且權(quán)值小于min */
            if(lowcost[j]!=0 && lowcost[j] < min)
            {
                /* 則讓當(dāng)前權(quán)值成為最小值,更新min */
                min = lowcost[j];
                /* 將當(dāng)前最小值的下標(biāo)存入k */
                k = j;
            }
            j++;
        }
        
        /* 打印當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊 */
        printf("(V%d, V%d)=%d\n", adjvex[k], k ,G.arc[adjvex[k]][k]);
        sum+=G.arc[adjvex[k]][k];
        
        /* 3.將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0,表示此頂點(diǎn)已經(jīng)完成任務(wù) */
        lowcost[k] = 0;
        
        /* 循環(huán)所有頂點(diǎn),找到與頂點(diǎn)k 相連接的頂點(diǎn)
         1. 與頂點(diǎn)k 之間連接;
         2. 該結(jié)點(diǎn)沒有被加入到生成樹;
         3. 頂點(diǎn)k 與 頂點(diǎn)j 之間的權(quán)值 < 頂點(diǎn)j 與其他頂點(diǎn)的權(quán)值,則更新lowcost 數(shù)組;
         
         */
        for(j = 1; j < G.numVertexes; j++)
        {
            /* 如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)未被加入生成樹權(quán)值 */
            if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
            {
                /* 將較小的權(quán)值存入lowcost相應(yīng)位置 */
                lowcost[j] = G.arc[k][j];
                /* 將下標(biāo)為k的頂點(diǎn)存入adjvex */
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

二注益、Kruskal算法

算法思路:

    1. 將鄰接矩陣 轉(zhuǎn)化成 邊表數(shù)組;
    1. 對邊表數(shù)組根據(jù)權(quán)值按照從?小到?大的順序排序;
    1. 遍歷所有的邊, 通過parent 數(shù)組找到邊的連接信息; 避免閉環(huán)問題;
    1. 如果不不存在閉環(huán)問題,則加?入到最?小?生成樹中. 并且修改parent 數(shù)組;
      代碼實(shí)現(xiàn):
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;
typedef struct
{
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/* 對邊集數(shù)組Edge結(jié)構(gòu)的定義 */
typedef struct
{
    int begin;
    int end;
    int weight;
}Edge ;

/*9.1 創(chuàng)建鄰接矩陣*/
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    /* printf("請輸入邊數(shù)和頂點(diǎn)數(shù):"); */
    G->numEdges=15;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=10;
    G->arc[0][5]=11;
    G->arc[1][2]=18;
    G->arc[1][8]=12;
    G->arc[1][6]=16;
    G->arc[2][8]=8;
    G->arc[2][3]=22;
    G->arc[3][8]=21;
    G->arc[3][6]=24;
    G->arc[3][7]=16;
    G->arc[3][4]=20;
    G->arc[4][7]=7;
    G->arc[4][5]=26;
    G->arc[5][6]=17;
    G->arc[6][7]=19;
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}


/* 交換權(quán)值以及頭和尾 */
void Swapn(Edge *edges,int i, int j)
{
    int tempValue;
    
    //交換edges[i].begin 和 edges[j].begin 的值
    tempValue = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = tempValue;
    
    //交換edges[i].end 和 edges[j].end 的值
    tempValue = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = tempValue;
    
    //交換edges[i].weight 和 edges[j].weight 的值
    tempValue = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = tempValue;
}

/* 對權(quán)值進(jìn)行排序 */
void sort(Edge edges[],MGraph *G)
{
    //對權(quán)值進(jìn)行排序(從小到大)
    int i, j;
    for ( i = 0; i < G->numEdges; i++)
    {
        for ( j = i + 1; j < G->numEdges; j++)
        {
            if (edges[i].weight > edges[j].weight)
            {
                Swapn(edges, i, j);
            }
        }
    }
    
    printf("邊集數(shù)組根據(jù)權(quán)值排序之后的為:\n");
    for (i = 0; i < G->numEdges; i++)
    {
        printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
    }
    
}

/* 查找連線頂點(diǎn)的尾部下標(biāo) */
//根據(jù)頂點(diǎn)f以及parent 數(shù)組,可以找到當(dāng)前頂點(diǎn)的尾部下標(biāo); 幫助我們判斷2點(diǎn)之間是否存在閉環(huán)問題;
int Find(int *parent, int f)
{
    while ( parent[f] > 0)
    {
        f = parent[f];
    }
    return f;
}

/* 生成最小生成樹 */
void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, n, m;
    int sum = 0;
    int k = 0;
    /* 定義一數(shù)組用來判斷邊與邊是否形成環(huán)路
     用來記錄頂點(diǎn)間的連接關(guān)系. 通過它來防止最小生成樹產(chǎn)生閉環(huán);*/
    
    int parent[MAXVEX];
    /* 定義邊集數(shù)組,edge的結(jié)構(gòu)為begin,end,weight,均為整型 */
    Edge edges[MAXEDGE];
    
    /*1. 用來構(gòu)建邊集數(shù)組*/
    for ( i = 0; i < G.numVertexes-1; i++)
    {
        for (j = i + 1; j < G.numVertexes; j++)
        {
            //如果當(dāng)前路徑權(quán)值 != ∞
            if (G.arc[i][j]<INFINITYC)
            {
                //將路徑對應(yīng)的begin,end,weight 存儲到edges 邊集數(shù)組中.
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                
                //邊集數(shù)組計算器k++;
                k++;
            }
        }
    }
    
    //2. 對邊集數(shù)組排序
    sort(edges, &G);
    
    
    //3.初始化parent 數(shù)組為0. 9個頂點(diǎn);
    // for (i = 0; i < G.numVertexes; i++)
    for (i = 0; i < MAXVEX; i++)
        parent[i] = 0;
    
    //4. 計算最小生成樹
    printf("打印最小生成樹:\n");
    /* 循環(huán)每一條邊 G.numEdges 有15條邊*/
    for (i = 0; i < G.numEdges; i++)
    {
        //獲取begin,end 在parent 數(shù)組中的信息;
        //如果n = m ,將begin 和 end 連接,就會產(chǎn)生閉合的環(huán).
        n = Find(parent,edges[i].begin);
        m = Find(parent,edges[i].end);
        //printf("n = %d,m = %d\n",n,m);
        
        /* 假如n與m不等,說明此邊沒有與現(xiàn)有的生成樹形成環(huán)路 */
        if (n != m)
        {
            /* 將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為起點(diǎn)的parent中溯捆。 */
            /* 表示此頂點(diǎn)已經(jīng)在生成樹集合中 */
            parent[n] = m;
            
            /*打印最小生成樹路徑*/
            printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
            sum += edges[i].weight;
        }
    }
    
    printf("sum = %d\n",sum);
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末丑搔,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子提揍,更是在濱河造成了極大的恐慌啤月,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件劳跃,死亡現(xiàn)場離奇詭異谎仲,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)刨仑,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門郑诺,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人贸人,你說我怎么就攤上這事间景。” “怎么了艺智?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵倘要,是天一觀的道長。 經(jīng)常有香客問我十拣,道長封拧,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任夭问,我火速辦了婚禮泽西,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘缰趋。我一直安慰自己捧杉,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布秘血。 她就那樣靜靜地躺著味抖,像睡著了一般。 火紅的嫁衣襯著肌膚如雪灰粮。 梳的紋絲不亂的頭發(fā)上仔涩,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機(jī)與錄音粘舟,去河邊找鬼熔脂。 笑死佩研,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的霞揉。 我是一名探鬼主播旬薯,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼适秩!你這毒婦竟也來了袍暴?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤隶症,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后岗宣,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蚂会,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年耗式,在試婚紗的時候發(fā)現(xiàn)自己被綠了胁住。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡刊咳,死狀恐怖彪见,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情娱挨,我是刑警寧澤余指,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站跷坝,受9級特大地震影響酵镜,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜柴钻,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一淮韭、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧贴届,春花似錦靠粪、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至绍些,卻和暖如春捞慌,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背柬批。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工啸澡, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留袖订,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓嗅虏,卻偏偏與公主長得像洛姑,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子皮服,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評論 2 361