DataStruct/MST_kruskal.cpp at master · githubdlj/DataStruct · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/********************************************************************
	Time:	  2015/11/09
	Filename: MST_kruskal
	Author:	  dinglj

	Purpose:  最小生成树,kruskal，无向网
              邻接矩阵实现
              时间复杂度：邻接矩阵， 邻接表O(n ^ 2) + O(eloge), 所以适合稀疏图
*********************************************************************/
#define INF     65536
#define MAXSIZE 20

//////////////////////////////////////////////////////////////////////
//  邻接矩阵结构

typedef struct
{
    int      no;
    char    info;
}VertexType;

typedef struct
{
    int weight;
}EdgeType;

typedef struct
{
    VertexType  v[MAXSIZE];
    EdgeType    e[MAXSIZE][MAXSIZE];

    int vertexNum;
    int edgeNum;
}MGraph;

//////////////////////////////////////////////////////////////////////
/********************************************************************
	Method:    MST_kruskal
	Parameter:
	Returns:

	Purpose:   采用邻接矩阵更方便，邻接表效率更高

*********************************************************************/
typedef struct
{
    int vex1, vex2;
    int weight;
}Edge;

Edge mstedge[MAXSIZE];        //  辅助存储结构，保存最小生成树

//  将邻接矩阵的边保存到数组edge中
void storeEdge(MGraph G, Edge edge[])
{
    int edgeNo = 0;
    for (int i = 0; i < G.edgeNum; ++i)
    {
        for (int j = i; j < G.edgeNum; ++j)     //  注意j的下标从i + 1开始，避免存储相同边
        {
            if (G.e[i][j].weight != INF && G.e[i][j].weight != 0)
            {
                edge[edgeNo].vex1 = i;
                edge[edgeNo].vex2 = j;
                edge[edgeNo].weight = G.e[i][j].weight;

                edgeNo++;
            }
        }
    }
}

//  对边进行冒泡排序，
void sortEdge(Edge edge[], int edgeNum)
{
    for (int i = 0; i < edgeNum; ++i)
    {
    //    for (int j = edgeNum - 1; j > i; j--)       //  尾部冒泡
        for (int j = 1; j < edgeNum - i; ++j)       //  头部冒泡
        {
            if (edge[j - 1].weight > edge[j].weight)
            {
                Edge temp = edge[j - 1];
                edge[j - 1] = edge[j];
                edge[j] = temp;
            }
        }
    }
}

//  MST_kruskal
void MST_kruskal(MGraph G)
{
    int vSet[MAXSIZE];  //  辅助结构，vSet[i] == vSet[j] 表示i,j属于同一个连通分量
    for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
    {
        vSet[vertexNo] = vertexNo;      //  初始时，所有的顶点均属于不同的连通分量
    }

    //    处理边
    Edge *edge = (Edge*)malloc(G.edgeNum * sizeof(Edge));      //  辅助存储结构，存储所有边
    storeEdge(G, edge);
    sortEdge(edge, G.edgeNum);

    //  找n - 1条边
    int edgeNo = 0;
    int index = 0;
    while (index < G.vertexNum - 1)
    {
        int s1 = vSet[edge[edgeNo].vex1];
        int s2 = vSet[edge[edgeNo].vex2];

        if (s1 != s2)   //  该边的顶点不属于同一个连通分量
        {
            mstedge[index] = edge[edgeNo];  //  将该边保存到最小生成树

            //  将s2所属的连通分量加入到s1所属的连通分量
            for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
            {
                if (s2 == vSet[vertexNo])
                {
                    vSet[vertexNo] = s1;
                }
            }
            index++;
        }

        edgeNo++;
    }

    free(edge);
}