碼迷,mamicode.com
首頁 > 編程語言 > 詳細

數據結構-最小生成樹-普里姆算法

時間:2019-06-19 10:49:22      閱讀:20      評論:0      收藏:0      [點我收藏+]

標簽:mamicode   code   開始   tail   https   輸入   ant   art   賦值   

 

轉自https://blog.csdn.net/ZGUIZ/article/details/54633115

首先仍然是預定義:

 1 #define OK 1
 2 #define ERROR 0
 3 #define Max_Int 32767
 4 #define MVNum 100
 5  
 6 typedef int Status;
 7 typedef char VerTexType;
 8 typedef int ArcType;
 9  
10 struct{
11     VerTexType adjvex; //前一個頂點
12     ArcType lowcost; //最近距離大小  初始化時為權值
13 }closedge[MVNum];
14  
15 typedef struct{//圖的結構體 存儲結構是鄰接矩陣
16     VerTexType vex[MVNum];  //頂點信息
17     ArcType arc[MVNum][MVNum]; //鄰接矩陣
18     int vexnum, arcnum; //頂點數 邊數
19 }AMGraph;

結構體數組closedge[]用于記錄與下標節點最小權值邊的值以及權值(即最小權值)。

創建圖:

int LocateVex(AMGraph *G,VerTexType v)
{ //找到下標
    int i;
    for (i = 0; i < G->vexnum; i++)
    {
        if (G->vex[i] == v)
            return i;
    }
    return -1;
}
 
Status CreateUDN(AMGraph *G)
{
    int i, j, k;
    VerTexType v1, v2;
    ArcType w;
    printf("輸入總節點數和總邊數:");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    fflush(stdin);
    printf("輸入各個節點的值:");
    for (i = 0; i < G->vexnum; i++)
        scanf("%c", &G->vex[i]);
    for (i = 0; i < G->vexnum;i++)
    for (j = 0; j < G->vexnum; j++)
    {
        G->arc[i][j] = Max_Int;
    }
    for (k = 0; k < G->arcnum; k++)
    {
        printf("輸入一條邊的兩個頂點以及該邊的權值:");
        scanf("%c %c %d", &v1, &v2, &w); //他這個 輸入的是頂點信息  通過LOCATEVEX函數找到對應的下標 再更新鄰接矩陣
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];
    }
    return OK;
}

查找下一個權值最小的邊上的另一個節點:

int Min(AMGraph G)
{
    int i;
    int min = Max_Int;
    int index = -1;
    for (i = 0; i < G.vexnum; i++)
    {
        if (min>closedge[i].lowcost&&closedge[i].lowcost!=0)
        {
            min = closedge[i].lowcost;
            index = i;
        }
    }
    return index;
}

開始時讓min為最大值,index用于記錄最小值的下標,開始時設為-1。將closedge[]數組中lowcost(最小權值)與min進行比較,若有比min小的,則將其值賦值給min,并用index記錄下標,重復比較,選出最小邊。返回index。

///////////////////////////////主
void
MinSpanTree_Prim(AMGraph G, VerTexType v)//從頂點V出發 按照普里姆算法構建最小生成樹 并輸出每條邊 和 總權值 { int i, j, k;
int sumlength=0;//總權值 VerTexType u0, v0; k
= LocateVex(&G, v);//對應的下標 for (j = 0; j < G.vexnum; j++) { if (j != k) { closedge[j].adjvex = v; //對其他頂點的初始化 closedge[j].lowcost = G.arc[k][j]; } } closedge[k].lowcost = 0;//初始化自身 for (i = 1; i < G.vexnum; i++) { k = Min(G); u0 = G.vex[k]; v0 = closedge[k].adjvex; printf("%c->%c\n", v0, u0);//找到了一個
sumlength+=在這里更新; closedge[k].lowcost
= 0;
for (j = 0; j < G.vexnum; j++) { //更新 if (closedge[j].lowcost>G.arc[k][j]) { closedge[j].adjvex = G.vex[k]; closedge[j].lowcost = G.arc[k][j]; } } }
cout<<sumlength<<endl; }

其中,v為開始的節點。先確定v的下標,并將closedge[]數組初始化:將其記錄的節點全部記錄為v節點,并記錄各個節點與其之間的權值。將closedge[]中v的權值記錄為0,表示已經在已經遍歷的數組中。

接下來用Min()函數確定最小權值的邊的另一個節點下標k,由于closedge[]數組中k下標的元素記錄了與其最短權值的邊的第一節點,故只需輸出closedge[k].adjvex和G.vex[k]。繼續查找一個頂點在遍歷數組中而且另一個頂點不再遍歷數組中的最短邊:在for()循環中,如果j下標的lowcost值大于圖中k和j節點的權值,表明其不是最小權值邊,則將closedge下標為j的元素中的節點值賦值為圖中k下標的節點,并將其lowcost改為k和j的權值。

重復上面操作,得到最小生成樹。

加入main():

int main(void)
{
    AMGraph G;
    CreateUDN(&G);
    MinSpanTree_Prim(G, 1);
    printf("\n");
    return 0;
}

 

技術圖片

 

數據結構-最小生成樹-普里姆算法

標簽:mamicode   code   開始   tail   https   輸入   ant   art   賦值   

原文地址:https://www.cnblogs.com/yundong333/p/11049871.html

(0)
(0)
   
舉報
評論 一句話評論(0
0條  
登錄后才能評論!
? 2014 mamicode.com 版權所有 京ICP備13008772號-2
迷上了代碼!
公式规律下期单双